Continuous parallel cyclic BCH decoding architecture
AssigneeAltera Corporation
InventorMartin Langhammer
Life of this patent
Estimating the term…
Abstract
Circuitry for, in p parallel streams, searching a codeword having n symbols for roots of a cyclic code polynomial having a number of terms includes a plurality of multipliers, a source of constants derived from roots of the polynomial, and at least one counter that supplies an index. For each received symbol of the codeword, the multipliers multiply respective terms of the polynomial for a previous received symbol by constants from the source of constants, the counter advances to select respective products of the constants and the respective terms for the previous received symbol.
Claims33
Circuitry for, in p parallel streams, searching a received codeword having n received symbols for roots of a cyclic code polynomial having a number of terms, where n and p are positive integers greater than 1 that have differing values that are not integer multiples of one another, said circuitry comprising:
- a plurality of multipliers;
- a source of constants derived from roots of said polynomial, said source of constants comprising a respective register corresponding to each respective term of said polynomial;
- and
- at least one counter that supplies an index;
- wherein for each of said n received symbols of said received codeword:
- said multipliers multiply respective terms of said polynomial for a previous received symbol by constants from said source of constants;
- and
- said counter advances to select respective products of said constants and said respective terms for said previous received symbol by providing an index into each said respective register to select a constant from said source of constants for multiplication by said respective term of said polynomial.
Circuitry for, in p parallel streams, searching a received codeword having n received symbols for roots of a cyclic code polynomial having a number of terms, where n and p are positive integers greater than 1 that have differing values that are not integer multiples of one another, said circuitry comprising:
- a plurality of multipliers equal in number to a product of said number of terms in said polynomial and a term number at most equal to p;
- a source of constants derived from roots of said polynomial;
- and
- at least one counter that supplies an index;
- wherein:
- for each of said n received symbols of said received codeword, said multipliers multiply respective terms of said polynomial for a previous received symbol by constants from said source of constants, each of said plurality of multipliers multiplying one term of said polynomial by one of said constants, such that for each of said polynomial terms, there are a term number of products;
- said circuitry further comprises, for each of said p parallel streams, a respective selector for each term of said polynomial;
- and
- said at least one counter controls said respective selectors to select one of said term number of products by selecting respective products of said constants and said respective terms for said previous received symbol.
A method of configuring a programmable device as circuitry for, in p parallel streams, searching a received codeword having n received symbols for roots of a cyclic code polynomial having a number of terms, where n and p are positive integers greater than 1 that have differing values that are not integer multiples of one another, said method comprising:
- configuring said programmable device with a plurality of multipliers;
- configuring, in said programmable device, a source of constants derived from roots of said polynomial, said source of constants comprising a respective register corresponding to each respective term of said polynomial;
- and
- configuring logic of said programmable device as at least one counter that supplies an index;
- wherein for each of said n received symbols of said received codeword:
- said multipliers multiply respective terms of said polynomial for a previous received symbol by constants from said source of constants;
- and
- said counter advances to select respective products of said constants and said respective terms for said previous received symbol by providing an index into each said respective register to select a constant from said source of constants for multiplication by said respective term of said polynomial.
A method of claim configuring a programmable device as circuitry for, in p parallel streams, searching a received codeword having n received symbols for roots of a cyclic code polynomial having a number of terms, where n and p are positive integers greater than 1 that have differing values that are not integer multiples of one another, said method comprising:
- configuring said programmable device with a plurality of multipliers comprises configuring said plurality of multipliers to be equal in number to a product of said number of terms in said polynomial and a term number at most equal to p;
- configuring, in said programmable device, a source of constants derived from roots of said polynomial;
- and
- configuring logic of said programmable device as at least one counter that supplies an index;
- wherein:
- for each of said n received symbols of said received codeword, each of said plurality of multipliers is configured to multiply one term of said polynomial by one of said constants, such that for each of said polynomial terms, there are a term number of products;
- said method further comprising:
- for each of said p parallel streams, configuring logic of said programmable device as a respective selector for each term of said polynomial;
- wherein:
- said configuring logic of said programmable device as at least one counter comprises configuring said at least one counter to control said respective selectors to select one of said term number of products by selecting respective products of said constants and said respective terms for said previous received symbol.
A non-transitory machine-readable data storage medium encoded with non-transitory machine-executable instructions for configuring a programmable device as circuitry for, in p parallel streams, searching a received codeword having n received symbols for roots of a cyclic code polynomial having a number of terms, where n and p are positive integers greater than 1 that have differing values that are not integer multiples of one another, said instructions comprising:
- instructions to configure said programmable device with a plurality of multipliers;
- instructions to configure, in said programmable device, a source of constants derived from roots of said polynomial, said source of constants comprising a respective register corresponding to each respective term of said polynomial;
- and
- instructions to configure logic of said programmable device as at least one counter that supplies an index;
- wherein for each of said n received symbols of said received codeword:
- said multipliers multiply respective terms of said polynomial for a previous received symbol by constants from said source of constants;
- and
- said counter advances to select respective products of said constants and said respective terms for said previous received symbol by providing an index into each said respective register to select a constant from said source of constants for multiplication by said respective term of said polynomial.
A non-transitory machine-readable data storage medium encoded with non-transitory machine-executable instructions for configuring a programmable device as circuitry for, in p parallel streams, searching a received codeword having n received symbols for roots of a cyclic code polynomial having a number of terms, where n and p are positive integers greater than 1 that have differing values that are not integer multiples of one another, said instructions comprising:
- instructions to configure said programmable device with a plurality of multipliers equal in number to a product of said number of terms in said polynomial and a term number at most equal to p;
- instructions to configure, in said programmable device, a source of constants derived from roots of said polynomial;
- instructions to configure logic of said programmable device as at least one counter that supplies an index;
- wherein for each of said n received symbols of said received codeword, each of said plurality of multipliers is configured to multiply one term of said polynomial by one of said constants, such that for each of said polynomial terms, there are a term number of products;
- said instructions further comprising:
- instructions to configure, for each of said p parallel streams, logic of said programmable device as a respective selector for each term of said polynomial;
- wherein:
- said instructions to configure logic of said programmable device as at least one counter comprise instructions to configure said at least one counter to control said respective selectors to select one of said term number of products by selecting respective products of said constants and said respective terms for said previous received symbol.
Dependencies are inferred from the claim text.