Methods and Apparatus in Alternate Finite Field Based Coders and Decoders

• US 20120170738A1
• Filed: 12/29/2010
• Published: 07/05/2012
• Est. Priority Date: 12/29/2010
• Status: Active Grant

• Current Assignee: Peter Lablans
• Original Assignee: Peter Lablans
• Inventors: Lablans, Peter
• Granted Patent: US 8,577,026 B2
• Time in Patent Office: Days
• 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≧

3, each symbol being represented by a signal, comprising;

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

a device implementing an addition over an alternate finite field GF(n); and

an output that provides a second plurality of symbols.

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 a multiplication over the alternate finite field GF(n).

4. The apparatus of claim 1, further comprising an n-state shift register with at least two n-state shift register elements.

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

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

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

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

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

10. The apparatus of claim 1, further comprising a corresponding apparatus to decode the second sequence into the first sequence.

11. The apparatus of claim 1, wherein the second sequence includes at least one check symbol.

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

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

1.

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

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

16. The apparatus of claim 1, wherein the apparatus is part of the group consisting of a communication system and a data storage system.

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

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

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

a device implementing a single truth table that is a truth table of an addition over an alternate finite field GF(n) modified by at least one n-state inverter defined by a multiplication over the alternate finite field GF(n) with n≧

4; and

an output that provides a second sequence of symbols.

19. The apparatus of claim 18, 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.

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

3, each symbol being represented by a signal, comprising;

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

the processor processing the plurality of signals representing the sequence of n-state symbols by an implementation of a single truth table, wherein the single truth table is a truth table of an addition over an alternate finite field or a truth table of an addition over the alternate finite field that is modified in accordance with at least one inverter defined by a multiplication over the alternate finite field;

providing a plurality of signals representing a decoded sequence of symbols on an output; and

wherein

the sequence of n-state symbols was generated by an encoder in the group consisting of a scrambler, 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 Linear Feedback Shift Register based encoder, a streaming cipher encoder, a block coder, a Feistel-like network based encoder, an Elliptic Curve Coding encoder, a symbol statistical distribution modifying encoder, a Galois Field arithmetic based encoder and an Advanced Encryption Standard (AES) encoder.