|
A recursive algorithm for decoding some subsets of first-order Reed–Muller codes
A. S. Logachev
Abstract:
We give a recursive algorithm for decoding a binary code that is determined as the subset of words of a first-order Reed–Muller code given by linear Boolean functions in $n$ variables of fixed weight $r$ (the number of real variables). We show that the complexity of decoding these subsets of coded words can be estimated by the number $(r+1)\cdot2^n$ of operations of the type of the addition of two numbers, which improves the estimate $(2r+1)\cdot2^n$ already known. This algorithm for the case of decoding the subsets of even [odd] weight $r$ has complexity $n\cdot 2^{n-1}$.
Received: 12.03.1991
Citation:
A. S. Logachev, “A recursive algorithm for decoding some subsets of first-order Reed–Muller codes”, Diskr. Mat., 4:2 (1992), 130–135; Discrete Math. Appl., 3:1 (1993), 83–88
Linking options:
https://www.mathnet.ru/eng/dm739 https://www.mathnet.ru/eng/dm/v4/i2/p130
|
Statistics & downloads: |
Abstract page: | 274 | Full-text PDF : | 110 | First page: | 2 |
|