Methods and Apparatus in Alternate Finite Field Based Coders and Decoders

• US 20110064214A1
• Filed: 11/23/2010
• Published: 03/17/2011
• Est. Priority Date: 09/09/2003
• Status: Abandoned Application

• Current Assignee: Ternarylogic LLC
• Original Assignee: Ternarylogic LLC
• Inventors: Lablans, Peter
• Application Number:
  US12/952,482
• Publication Number:
  US 20110064214A1
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes

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-21. -21. (canceled)

22. An apparatus to generate from a first sequence of n-state symbols with n>

2 a second sequence of n-state symbols, an n-state symbol being represented by a signal, comprising;

an input, enabled to receive a signal representing an n-state symbol in the first sequence of n-state symbols;

a addressable memory device, including a first input enabled to receive a signal representing a first n-state symbol and a second input enabled to receive a signal representing a second n-state symbol, the addressable memory device storing at least a single n-state n by n non-commutative truth table not being a modulo-n subtraction and wherein the first n-state symbol is equal to or is associated with the n-state symbol in the first sequence;

an output of the addressable memory device, enabled to provide a signal representing an n-state symbol based on the first and second n-state symbol that is generated in accordance with the single n-state n by n truth table; and

an output, enabled to provide a signal representing an n-state symbol in the second sequence of n-state symbols.

23. The apparatus of claim 22, wherein the single n-state n by n non-commutative truth table represents an arithmetical operation over a finite field GF(n).

24. The apparatus of claim 22, wherein the finite field GF(n) is GF(n=u^p) with u≧

2 and p≧

2.

25. The apparatus of claim 22, wherein the single n-state n by n non-commutative truth table is a truth table of an addition over finite field GF(n) modified in accordance with an n-state inverter.

26. The apparatus of claim 22, wherein the apparatus performs an arithmetical calculation over a finite field GF(n).

27. The apparatus of claim 22, wherein the second sequence of n-state symbols contains a check symbol derived from the first sequence of n-state symbols.

28. The apparatus of claim 22, wherein the apparatus is a Reed-Solomon coder.

29. The apparatus of claim 22, further comprising a corresponding apparatus to re-create from the second sequence of n-state symbols the first sequence of n-state symbols.

30. The apparatus of claim 22, further comprising a Linear Feedback Shift Register (LFSR).

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

32. The apparatus of claim 22, wherein the apparatus is a Cyclic Redundancy Check (CRC) coder.

33. The apparatus of claim 22, wherein the apparatus is part of a communication device.

34. The apparatus of claim 22, wherein the apparatus is part of a data storage device.

35. An apparatus to generate an output signal representing an n-state symbol with n>

2 in accordance with a calculation over a finite field GF(n), comprising;

an addressable memory device including a first input enabled to receive a signal representing a first n-state symbol and a second input enabled to receive a signal representing a second n-state symbol, the addressable memory device storing at least a single n-state n by n non-commutative truth table which is a truth table of an addition over the finite field GF(n) modified in accordance with a multiplication over the finite field GF(n) and is not a modulo-n subtraction;

an output of the addressable memory device, enabled to provide the output signal representing the n-state symbol with n>

2 in accordance with the calculation over the finite field GF(n).

36. The apparatus of claim 35, wherein the apparatus is a Reed-Solomon coder.

37. The apparatus of claim 35, wherein the apparatus is part of a communication device.

38. The apparatus of claim 35, wherein the apparatus is part of a storage device.

39. A device to process one or more n-state symbols with n>

2 and each n-state symbol being represented as a plurality of binary signals to generate an output signal representing an n-state symbol, comprising;

an input to receive a signal representing the one or more n-state symbols;

an addressable memory device including a first input enabled to receive a signal representing a first n-state symbol and a second input enabled to receive a signal representing a second n-state symbol, the addressable memory device storing at least a single n-state n by n truth table representing an arithmetical operation over a Galois Field GF(n=u^p) with u≧

2 and p>

6; and

an output of the addressable memory device, enabled to provide the output signal representing the n-state symbol in accordance with a calculation over the finite field GF(n=u^p).

40. The device of claim 39, wherein the single n-state n by n truth table is a non-commutative truth table.

41. The device of claim 39, wherein the device is a communication device.

42. The device of claim 39, wherein the device is a data storage device.