TY - JOUR

T1 - List decoding of biorthogonal codes and the Hadamard transform with linear complexity

AU - Dumer, Ilya

AU - Kabatiansky, Grigory

AU - Tavernier, Cédric

N1 - Funding Information:
Manuscript received July 2, 2007. Current version published September 17, 2008. The work of I. Dumer was supported in part by the National Science Foundation under Grants CCF0622242 and CCF0635339. The work of G. Ka-batiansky was supported in part by the Russian Foundation for Fundamental Research under Grants 06-01-00226 and 08-07-92495. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Nice, France, June 2007.

PY - 2008

Y1 - 2008

N2 - Let a biorthogonal Reed-Muller code RM (1, m) of length n = 2m be used on a memoryless channel with an input alphabet ± and a real-valued output ℝ. Given any nonzero received vector y in the Euclidean space ℝn and some parameter ε ∈ (0, 1), our goal is to perform list decoding of the code RM (1, m) and retrieve all codewords located within the angle arccos ε from y. For an arbitrarily small ε, we design an algorithm that outputs this list of codewords with the linear complexity order of n ⌈ln2 ε⌉ bit operations. Without loss of generality, let vector y be also scaled to the Euclidean length √n of the transmitted vectors. Then an equivalent task is to retrieve all coefficients of the Hadamard transform of vector y whose absolute values exceed nε. Thus, this decoding algorithm retrieves all nε-significant coefficients of the Hadamard transform with the linear complexity n⌈ln2ε⌉ instead of the complexity n ln2 n of the full Hadamard transform.

AB - Let a biorthogonal Reed-Muller code RM (1, m) of length n = 2m be used on a memoryless channel with an input alphabet ± and a real-valued output ℝ. Given any nonzero received vector y in the Euclidean space ℝn and some parameter ε ∈ (0, 1), our goal is to perform list decoding of the code RM (1, m) and retrieve all codewords located within the angle arccos ε from y. For an arbitrarily small ε, we design an algorithm that outputs this list of codewords with the linear complexity order of n ⌈ln2 ε⌉ bit operations. Without loss of generality, let vector y be also scaled to the Euclidean length √n of the transmitted vectors. Then an equivalent task is to retrieve all coefficients of the Hadamard transform of vector y whose absolute values exceed nε. Thus, this decoding algorithm retrieves all nε-significant coefficients of the Hadamard transform with the linear complexity n⌈ln2ε⌉ instead of the complexity n ln2 n of the full Hadamard transform.

KW - Algorithm design and analysis

KW - Biorthogonal codes

KW - Complexity theory

KW - Decoding

KW - Error correction codes

KW - Hadamard transform

KW - Maximum likelihood decoding

KW - Soft-decision list decoding

KW - Transforms

KW - Vectors

UR - http://www.scopus.com/inward/record.url?scp=54749121003&partnerID=8YFLogxK

U2 - 10.1109/TIT.2008.929014

DO - 10.1109/TIT.2008.929014

M3 - Article

AN - SCOPUS:54749121003

VL - 54

SP - 4488

EP - 4492

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 10

ER -