Methods and apparatus for decoding data
AssigneeHewlett-Packard Company
InventorsJonathan Jedwab, James Andrew Davis, Kenneth Graham Paterson
Life of this patent
Estimating the term…
Abstract
In a coded orthogonal frequency division multiplex (COFDM) system n-bit data words are encoded as 2m-symbol code words, each symbol having 2j possible values (e.g. j=3 for octary). An efficient decoder for these code words is provided by applying j iterations of the fast Hadamard transform, the input vector for the second and subsequent iterations being derived from the result of the immediately preceding iteration.
Claims16
A method of identifying a code word within a predetermined set of code words, the code words including symbols each having pj different possible values where p is a prime and j is an integer greater than 1, said method comprising:
- deriving a plurality of constituents, constituent1 to constituentk of said code word with respect to an input word, each constituent identifying an element of a predetermined subset of a predetermined linear code;
- and
- combining said k constituents to identify said code word according to a relationship
- (pb(k)*constituentk+pb(k−1)*constituentk−1+ . . . +pb(2)*constituent2+pb(1)*constituent1)mod pj
- where each b(x) is an integer, x is an integer from 1 to k, j>b(k)>b(k−1)> . . . >b(2)>b(1)>0, * indicates symbol-wise multiplication, + indicates symbol-wise addition and mod indicates symbol-wise modular reduction.
A method of identifying a code word within a predetermined set of code words, the code words including symbols each having 2j different possible values where j is an integer greater than 1, comprising the steps of
- receiving an input word;
- deriving the result of the input word reduction modulo 21;
- deriving a first constituent, constituent1, by applying a Hadamard transform operation, or equivalent thereof, in respect of the result of said reduction modulo 21;
- setting a modifier equal to constituent1;
- for each successive value of a counter x from 2 to j:
- deriving the result of symbol-wise subtraction of the current value of the modifier from the input word reduction modulo 2x;
- deriving another constituent, constituentx, by applying a Hadamard transform operation, or equivalent thereof, to the result of said symbol-wise subtraction of the current value of the modifier from the input word modulo 2x;
- setting the modifier equal to the symbol-wise sum modulo 2j of the preceding modifier and the product of 2x−1 times constituentx;
- and
- identifying the code word as having the final value of said modifier.
Apparatus for identifying a code word within a predetermined set of code words, the code words including symbols each having pj different possible values where p is a prime and j is an integer greater than 1, comprising:
- a decoder for deriving in respect of an input word a plurality of constituents, constituent1 to constituentk, of said code word, each constituent identifying an element of a predetermined subset of a predetermined linear code;
- and
- a combiner for combining said k constituents to identify said code word according to a relationship
- (pb(k)*constituentk+pb(k−1)*constituentk−1+ . . . +pb(2)*constituent2+pb(1)*constituent1)mod pj
- where each b(x) is an integer, x is an integer from 1 to k, j>b(k)>b(k−1)> . . .>b(2)>b(1)>0, * indicates symbol-wise multiplication, + indicates symbol-wise addition and mod indicates symbol-wise modular reduction.
Dependencies are inferred from the claim text.