Methods and apparatus in alternate finite field based coders and decoders

• US 8,577,026 B2
• Filed: 12/29/2010
• Issued: 11/05/2013
• Est. Priority Date: 12/29/2010
• Status: Expired due to Fees

• Current Assignee: Ternarylogic LLC
• Original Assignee: Ternarylogic LLC
• Inventors: Lablans, Peter
• Primary Examiner(s): BROWN, CHRISTOPHER J
• Application Number:
  US12/980,504
• Publication Number:
  US 20120170738A1
• Time in Patent Office: 1,042 Days
• Field of Search: 380/28
• US Class Current: 380/28
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/159 Remainder calculation, e.g. for encoding and syndrome calculation
• CPC Class Codes: H03M 13/2732 Convolutional interleaver; Interleavers using shift-registers or delay lines like, e.g. Ramsey type interleaver
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

Methods and apparatus for coding and decoding n-state symbols with n≧2 and n>2 and n>3 and n>4 are provided wherein at least one implementation of an addition over an alternate finite field GF(n) and an inverter defined by a multiplication over the alternate finite field GF(n) are provided. Encoders and decoders implementing a single n-state truth table that is a truth table of an addition over an alternate finite field GF(n) modified in accordance with at least one inverter defined by a multiplication over the alternate finite field GF(n) are also provided. Encoders include scramblers, Linear Feedback Shift Register (LFSR) based encoders, sequence generator based encoders, block coders, streaming cipher encoders, transposition encoders, hopping rule encoders, Feistel network based encoders, check symbol based encoders, Hamming coder, error correcting encoders, encipherment encoders, Elliptic Curve Coding encoders and all corresponding decoders. Systems applying encoders and decoders also are provided.

Claims

1. An apparatus for encoding a first plurality of n-state symbols with n equal to or greater than 3, each symbol being represented by a signal, comprising:

an input of a device enabled to receive the first plurality of n-state symbols;

the device enabled for processing the first plurality of n-state symbols by implementing an addition and a multiplication over an alternate finite field GF(n), wherein the alternate finite field GF(n) is a finite field defined by the addition, the multiplication, and a zero element of the finite field;

wherein the zero element of the alternate finite field GF(n) is a neutral element of the addition and is not 0;

wherein

the apparatus is part of a communication system or a data storage system and an output enabled to provide a second plurality of symbols as a result of the processing.

2. The apparatus of claim 1, wherein n>

4.

3. The apparatus of claim 1, further comprising:

an implementation of at least one n-state inverter defined by the multiplication over the alternate finite field GF(n).

4. The apparatus of claim 1, wherein the second plurality of n-state symbols is applied in symbol error correction.

5. The apparatus of claim 1, wherein the device is part of a Feistel-like network.

6. The apparatus of claim 1, wherein the apparatus is an Advanced Encryption Standard (AES) encoder.

7. The apparatus of claim 1, wherein the apparatus is an Elliptic Curve Coding encoder.

8. The apparatus of claim 1, wherein the apparatus modifies a statistical distribution of symbols in the first plurality of symbols compared to the second plurality of symbols.

9. The apparatus of claim 1, further comprising a corresponding apparatus to decode the second plurality of symbols into the first plurality of symbols.

10. The apparatus of claim 1, wherein the second plurality of symbols includes at least one check symbol.

11. The apparatus of claim 1, wherein n is a prime number.

12. The apparatus of claim 1, wherein n=2^m with m>

1.

13. The apparatus of claim 1, wherein the apparatus is a transposition encoder.

14. The apparatus of claim 1, wherein the apparatus performs a Galois arithmetical operation for encoding.

15. The apparatus of claim 1, wherein an n-state symbol is represented by a plurality of binary signals.

16. An apparatus for encoding a first sequence of n-state symbols, each n-state symbol being represented by a signal, comprising:

an input of a device enabled to receive the first sequence of n-state symbols;

the device enabled for processing the first plurality of n-state symbols by implementing a single truth table that is a truth table of a modified addition over an alternate finite field GF(n), wherein the alternate finite field GF(n) is a finite field defined by the addition, a multiplication and a neutral element of the addition;

wherein the neutral element of the addition is not 0 and the modified addition over the alternate finite field GF(n) is the addition over the alternate finite field GF(n) that is modified by at least one n-state inverter defined by the multiplication over the alternate finite field GF(n) wherein n is an integer greater than 4; and

wherein

the apparatus is part of a communication system or a data storage system; and

an output that provides a second sequence of symbols as a result of the processing.

17. The apparatus of claim 16, wherein the apparatus is one of the group consisting of:

a scrambler, a convolutional coder, a Reed-Solomon coder, a Hamming coder, a check-symbol based error correcting coder, a transposition coders, a hopping rule coder, a Linear Feedback Shift Register based coder, a Feistel-like network based coder, an Elliptic Curve Coding coder, a symbol statistical distribution modifying coder, a Galois Field arithmetic based coder, a sequence generator based encoder, a streaming coder, a block coder and an Advanced Encryption Standard (AES) coder.

18. A method for decoding a sequence of encoded n-state symbols with n>

4, each n-state symbol in the sequence of encoded n-state symbols being represented by a signal, comprising;

providing a plurality of signals representing the encoded sequence of n-state symbols to an input of a processor;

wherein

the encoded sequence of n-state symbols was generated using an encoder in the group consisting of a convolutional encoder, a Reed-Solomon encoder, a Hamming coder, a check-symbol based error correcting encoder, a transposition encoder, a hopping rule encoder, a streaming cipher encoder, a block coder, a Feistel-like network based encodes an Elliptic Curve Coding encoder, a symbol statistical distribution modifying encoder, a Galois Field arithmetic based encoder and an Advanced Encryption Standard (AES) encoder;

the processor processing the plurality of signals representing the encoded sequence of n-state symbols by an implementation of an addition and a multiplication over an alternate finite field, wherein the addition and the multiplication over the alternate finite field define the alternate finite field;

wherein a zero element of the alternate finite field is a neutral element of the addition over the alternate finite field and is not 0; and

an output providing a plurality of signals representing a decoded sequence of n-state symbols on an output as a result of the processing.