Parvaresh-Vardy (PV) code[1]

Description

Also called a correlated RS code. 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

Zoo code information

Internal code ID: parvaresh_vardy

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: parvaresh_vardy

Cite as:
“Parvaresh-Vardy (PV) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/parvaresh_vardy
BibTeX:
@incollection{eczoo_parvaresh_vardy, title={Parvaresh-Vardy (PV) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/parvaresh_vardy} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/parvaresh_vardy

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/q-ary_digits/rs/parvaresh_vardy.yml.