# Parvaresh-Vardy (PV) code[1]

Also known as Correlated RS code.

## Description

An IRS code with additional algebraic relations (a.k.a. correlations) between the codeword polynomials \(\{f^{(j)}\}_{j=1}^{t}\). These relations yielded a list decoder that achieves list-decoding capacity.

## Decoding

PV codes can be list-decoded up to \(1-(t k/n)^{1/(t+1)}\) fraction of errors. This result improves over the Guruswami-Sudan algorithm for ordinary RS codes, which list-decodes up to \(1-\sqrt{k/n}\) fraction of errors.

## Parent

- Interleaved RS (IRS) code — PV codes are IRS codes with specific algebraic relations between the codeword polynomials that allow for efficient list decoding.

## Cousin

- Folded RS (FRS) code — The specific relations imposed on the polynomials of PV codes allow for them to be expressed in a similar way as FRS codes, but with more redundancy. Folded RS codes can be list-decoded up to a higher fraction of errors.

## References

- [1]
- F. Parvaresh and A. Vardy, “Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) DOI

## Page edit log

- Victor V. Albert (2022-07-14) — most recent

## Cite as:

“Parvaresh-Vardy (PV) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/parvaresh_vardy