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

Ilya Dumer, Grigory Kabatiansky, Cédric Tavernier

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)4488-4492
Number of pages5
JournalIEEE Transactions on Information Theory
Issue number10
Publication statusPublished - 2008
Externally publishedYes


  • Algorithm design and analysis
  • Biorthogonal codes
  • Complexity theory
  • Decoding
  • Error correction codes
  • Hadamard transform
  • Maximum likelihood decoding
  • Soft-decision list decoding
  • Transforms
  • Vectors


Dive into the research topics of 'List decoding of biorthogonal codes and the Hadamard transform with linear complexity'. Together they form a unique fingerprint.

Cite this