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) 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