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

Let a biorthogonal Reed-Muller code RM (1, m) of length n = [2.sup.m] be used on a memoryless channel with an input alphabet [+ or -] 1 and a real-valued output R. Given any nonzero received vector y in the Euclidean space [R.sup.n] and some parameter [epsilon] [member of] (0, 1), our goal is to perform list decoding of the code RM (1, m) and retrieve all codewords located within the angle arccos [member of] from y. For an arbitrarily small [epsilon], we design an algorithm that outputs this list of codewords with the linear complexity order of n [[ln.sup.2] [epsilon]] bit operations. Without loss of generality, let vector y be also scaled to the Euclidean length [square root of 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[epsilon]. Thus, this decoding algorithm retrieves all n[epsilon]-significant coefficients of the Hadamard transform with the linear complexity n [[ln.sup.2] [epsilon]] instead of the complexity n [ln.sup.2] n of the full Hadamard transform. Index Terms--Biorthogonal codes, Hadamard transform, soft-decision list decoding.