Back to results
US 7,117,424 B2Granted
Block coding method having increased flexibility in choice of code length or minimum code distance
AssigneeLucent Technologies Inc.
InventorsGanapathy Subramanian Sundaram, Kartik Swaminathan Venkatram
Life of this patent
Estimating the term…
Abstract
In a method of block coding, each character of the codeword may be thought of as a sum of characters of the message word, computed such that each message-word character that contributes to the sum is weighted by a respective weight coefficient. In the method described here, the weight coefficients are derived from a division polynomial of an elliptic curve.
Claims10
A method for encoding data, comprising:
- receiving from a communication medium and storing in a storage medium at least one message word;
- and
- applying a transformation to the message word, thereby to produce a codeword, wherein the transformation comprises a linear mapping to a codeword derived from a division polynomial ψ of an elliptic curve defined by a polynomial E, ψ and E have coefficients taken from a finite field, ψ and E generate a mathematical ideal I, the mapping is from message words to a quotient ring comprising bivariate polynomials modulo I, and wherein:
- a) there is a correspondence that identifies each message word and each codeword with a unique polynomial having coefficients taken from the finite alphabet, said polynomials being referred to respectively as message polynomials and codeword polynomials;
- b) the message word is selected from a finite set of said message polynomials;
- c) the transformation is carried out such that each message word is mapped to a member of a finite set of codewords, said finite set being referred to as a code;
- d) the polynomials that correspond to the code constitute a finite set of polynomials in two variables, said polynomials being referred to as codeword polynomials;
- e) an addition and a multiplication operation are defined on the code such that any pair of codeword polynomials can be added or multiplied together as polynomials;
- f) the result of adding together or multiplying together any pair of codeword polynomials is also a codeword polynomial;
- and
- g) the multiplication operation is based on taking remainders after dividing by the polynomial E and after dividing by the polynomial ψ.
8 more elements
A method, comprising:
- receiving a block-coded communication;
- recovering at least one received word from the communication;
- and
- testing the received word for membership in a code consisting of a finite set of codewords, thereby to check for error in the received word, wherein:
- a) there is a correspondence that identifies each codeword with a unique polynomial having coefficients taken from a finite alphabet, said polynomials being referred to as codeword polynomials;
- b) the codeword polynomials constitute a finite set of polynomials in two variables;
- c) an addition and a multiplication operation are defined on the code such that any pair of codeword polynomials can be added or multiplied together as polynomials;
- d) the result of adding together or multiplying together any pair of codeword polynomials is also a codeword polynomial;
- and
- e) the multiplication operation is based on taking remainders after dividing by polynomials E and ψ having coefficients in the alphabet, wherein ψ is a division polynomial of an elliptic curve defined by E, E and ψ generate a mathematical ideal I, and the codeword polynomials belong to a quotient ring modulo I.
7 more elements
Dependencies are inferred from the claim text.