Parvaresh-Vardy (PV) code[1]
Alternative names: 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.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.
Member of code lists
Primary Hierarchy
Parents
PV codes are IRS codes with specific algebraic relations between the codeword polynomials that allow for efficient list decoding.
Parvaresh-Vardy (PV) code
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) 285 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