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

Ilya Dumer, Grigory Kabatiansky, Cédric Tavernier

Результат исследований: Вклад в журналСтатьярецензирование

5 Цитирования (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.

Язык оригиналаАнглийский
Страницы (с-по)4488-4492
Число страниц5
ЖурналIEEE Transactions on Information Theory
Номер выпуска10
СостояниеОпубликовано - 2008
Опубликовано для внешнего пользованияДа


Подробные сведения о темах исследования «List decoding of biorthogonal codes and the Hadamard transform with linear complexity». Вместе они формируют уникальный семантический отпечаток (fingerprint).