Method and apparatus for using finite state machines to perform channel modulation and error correction and entropy coding

• US 5,475,388 A
• Filed: 10/22/1993
• Issued: 12/12/1995
• Est. Priority Date: 08/17/1992
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Gormish, Michael J., Allen, James D.
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/142,504
• Time in Patent Office: 781 Days
• Field of Search: 341/58, 341/59, 341/65, 341/67, 341/72, 341/107, 341/106, 341/51, 341/94
• US Class Current: 341/107
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G11B 20/1426 conversion to or from block codes or representations thereof
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/31 combining coding for error detection or correction and efficient use of the spectrum without error detection or correction H03M5/14 , H03M5/145
• CPC Class Codes: H03M 5/145 Conversion to or from block codes or representations thereof
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code

Abstract

The present invention provides an encoding and decoding apparatus used for the compression and expansion of data. A state machine is provided having a plurality of states. Each state has at least one transition pair. Each element of the transition pair comprises zero or more bits representative of the compact code to be output and the identification of the next state to proceed to. The transition pair reflects an output for a yes and no response associated with the probability of the data to be compacted and whether the data falls within that probability.

Claims

1. A method for performing channel modulation and compression on an input bit stream having a plurality of input bits, said method comprising the steps of:

locating a transition in at least one transition pair in one of a plurality of states in a transition machine according to a portion of said plurality of input bits, wherein each of said plurality of states in said transition machine has at least one transition pair, and wherein each transition in said at least one transition pair is associated with an output bit stream that is output when said each transition is selected, and further wherein each of the output bit streams comprises a channel coded and compressed representation of input bits; and

outputting the output bit stream associated with said transition and transitioning to a next state, wherein a variable number of bits is output from the transition machine for each portion of said plurality of input bits, wherein a plurality of output bits are generated in response to the input bit stream, such that the input bit stream is channel coded and compressed by use of a single transition machine.

2. The method defined in claim 1 wherein the bit stream for each of the transitions adheres to a channel constraint.

3. The method defined in claim 2 wherein the bit stream output for each of the transitions represents a run length limited coded version of the plurality of input bits.

4. The method defined in claim 1 wherein each portion of the plurality of input bits comprises one bit.

5. The method defined in claim 1 wherein each of the output bit streams comprises a compressed representation of the portion of said plurality of input bits, such that the input bit stream is compressed and channel coded.

6. The method defined in claim 1 further comprising the steps of:

receiving a probability for the portion of said plurality of input bits;

receiving an indication for said portion of the plurality of input bits, wherein the indication indicates whether said portion of plurality of input bits is within one of a plurality of possible first states, wherein the transition is located according to probability and the indication.

7. The method defined in claim 6 wherein the indication comprises a binary decision pair.

8. The method defined in claim 6 wherein the indication comprises a yes/no indicative.

9. The method defined in claim 6 wherein the probability comprises a probability estimate.

10. A method for performing channel modulation and compression on an input bit stream having a plurality of input bits, said method comprising the steps of:

receiving one of said plurality of input bits;

locating a transition in at least one transition pair in one of a plurality of states in a transition machine according to said one of said plurality of input bits, wherein each of said plurality of states in the transition machine have at least one transition pair and each of the transitions in said at least one transition pair is associated with an output bit stream, wherein each output bit stream comprises a compressed and channel coded representation of input bits; and

outputting the output bit stream associated with said transition, wherein a variable number of bits is output from the transition machine for each portion of said plurality of input bits, wherein a plurality of output bits are generated in response to the input bit stream, such that the input bit stream is compressed and channel coded by use of a single transition machine.

11. The method defined in claim 10 wherein the bit stream for each of the transitions adheres to a channel constraint.

12. The method defined in claim 10 wherein the bit stream output for each of the transitions represents a run length limited coded version of the plurality of input bits.

13. The method defined in claim 10 further comprising the step of transitioning to a next state after outputting the bit stream, wherein the next state is indicated by the transition.

14. The method defined in claim 10 further comprising the steps of:

receiving a probability for said one of said plurality of input bits;

receiving an indication for said one of the plurality of input bits, wherein the first indication indicates whether said one of plurality of input bits is within one of a plurality of possible first states, wherein the transition is located according to probability and the indication.

15. The method defined in claim 14 wherein the indication comprises a binary decision pair.

16. The method defined in claim 14 wherein the indication comprises a yes/no indicative.

17. The method defined in claim 14 wherein the probability comprises a probability estimate.

18. A method for performing channel modulation and compression on an input bit stream having a plurality of input bits, said method comprising the steps of:

receiving a first threshold value for one of the plurality of inputs;

receiving a first indication for said one of the plurality of inputs, wherein said first indication indicates whether said one of the plurality of inputs is within one of the plurality of possible first states;

selecting one of a plurality of sets of transitions in one of a plurality of transition states according to the first threshold value, wherein each transition in the plurality of sets of transitions is associated with an output and a next state within the plurality of transition states, and further wherein each output comprises a channel modulated and compressed representation of a portion of said plurality of input bits;

selecting a transition in said one of a plurality of sets of transitions according to said first indication; and

outputting the output associated with the transition, wherein a variable number of bits is output from the transition machine for each of said plurality of input bits, such that the input bit stream is channel coded and compressed by use of a single transition machine.

19. The method defined in claim 18 further comprising the step of transitioning to the next state associated with the transition, such that a transition within the next state is selected using a second threshold value and a second indication corresponding to an input immediately following said one of the plurality of inputs.

20. A method for performing error correction coding and channel coding on an input bit stream having a plurality of input bits, said method comprising the steps of:

receiving a portion of said plurality of input bits;

locating a transition in at least one transition pair in one of a plurality of states in a transition machine according to said portion of said plurality of input bits, wherein each of said plurality of states in the transition machine has at least one transition pair and each of the transitions in said at least one transition pair is associated with an output bit stream, and further wherein each output bit stream comprises a channel coded and error correction coded representation of the portion of said plurality of input bits; and

outputting the output bit stream associated with said transition and transitioning to the next state, wherein a plurality of output bits are generated in response to the input bit stream, such that the input bit stream is error correction coded and channel coded by use of a single transition machine.

21. The method defined in claim 20 wherein each portion of the plurality of input bits comprises one bit.

22. The method defined in claim 20 wherein the error correction coding is a convolutional code.

23. The method defined in claim 20 wherein the error correction coding is a trellis code.

24. The method defined in claim 20 further comprising the step of transitioning to a next state after outputting the bit stream, wherein the next state is indicated by the transition.

25. The method defined in claim 20 further comprising the steps of:

receiving a probability for the portion of said plurality of input bits;

receiving an indication for said portion of the plurality of input bits, wherein the indication indicates whether said portion of plurality of input bits is within one of a plurality of possible first states, wherein the transition is located according to probability and the indication.

26. The method defined in claim 25 wherein the indication comprises a binary decision pair.

27. The method defined in claim 25 wherein the indication comprises a yes/no indicative.

28. The method defined in claim 25 wherein the probability comprises a probability estimate.

29. A method for performing error correction and compression on an input bit stream having a plurality of input bits, said method comprising the steps of:

receiving one of said plurality of input bits;

locating a transition in at least one transition pair in one of a plurality of states in a transition machine according to said one of said plurality of input bits, wherein each of said plurality of states in the transition machine has at least one transition pair and each of the transitions in said at least one transition pair is associated with an output bit stream, wherein each output bit stream comprises a compressed and error correction coded representation of one of said plurality of input bits; and

outputting the output bit stream associated with said transition, wherein a variable number of bits is output from the transition machine for each portion of said plurality of input bits, wherein a plurality of output bits are generated in response to the input bit stream, such that the input bit stream is compressed and error correction coded by use of a single transition machine.

30. The method defined in claim 29 wherein the error correction coding is a convolutional code.

31. The method defined in claim 29 wherein the error correction coding is a trellis code.

32. The method defined in claim 29 further comprising the step of transitioning to a next state after outputting the bit stream, wherein the next state is indicated by the transition.

33. The method defined in claim 29 further comprising the steps of:

receiving a probability for said one of said plurality of input bits;

receiving an indication for said one of the plurality of input bits, wherein the indication indicates whether said one of plurality of input bits is within one of a plurality of possible first states, wherein the transition is located according to probability and the indication.

34. The method defined in claim 33 wherein the indication comprises a binary decision pair.

35. The method defined in claim 33 wherein the indication comprises a yes/no indicative.

36. The method defined in claim 33 wherein the probability comprises a probability estimate.

37. A method for performing coding on an input stream, wherein the input stream comprises a plurality of symbols from an alphabet of a symbols, said method comprising the steps of:

receiving a symbol in the input stream;

selecting a transition in one of a plurality of states in a transition machine having a plurality of states, wherein each of the plurality of states has at least one transition for each of the predetermined number of symbols in the alphabet, and wherein each of the transitions is associated with an output stream, wherein the transition in said one of said plurality of states is selected according to the symbol in the input stream;

outputting the output stream associated with said transition and transition to a next state, wherein a variable number of symbols is output from the transition machine for at least two distinct symbols in the input stream, such that the input stream is coded.

38. The method defined in claim 37 wherein each output stream is chosen, such that output stream is outputted, such that the input stream is channel modulated.

39. The method defined in claim 37 wherein each output stream is chosen, such that output stream is outputted, such that the input stream is channel modulated and compressed by use of a single transition machine.

40. The method defined in claim 37 further comprising the steps of:

receiving a probability for the symbol;

receiving an indication for said symbol, wherein the indication indicates whether said symbol is within one of a plurality of possible first states, wherein the transition is located according to probability and the indication.

41. The method defined in claim 40 wherein the indication comprises a binary decision pair.

42. The method defined in claim 40 wherein the indication comprises a yes/no indicative.

43. The method defined in claim 40 wherein the probability comprises a probability estimate.

44. A method for performing coding on an input stream, wherein the input stream comprises a plurality of symbols from an alphabet of a symbols, said method comprising the steps of:

receiving a symbol in the input stream;

selecting a transition in one of a plurality of states in a transition machine having a plurality of states, wherein each of the plurality of states has at least one transition for each of the predetermined number of symbols in the alphabet, and wherein each of the transitions is associated with an output stream, wherein the transition in said one of said plurality of states is selected according to the symbol in the input stream;

outputting the output stream associated with said transition and transition to a next state, wherein a variable number of symbols is output from the transition machine for at least two distinct symbols in the input stream, such that output stream is outputted, such that the input stream is error correction coded.

45. The method defined in claim 44 further comprising the steps of:

receiving a probability for the symbol;

receiving a indication for said symbol, wherein the indication indicates whether said symbol is within one of a plurality of possible first states, wherein the transition is located according to probability and the indication.

46. The method defined in claim 45 wherein the indication comprises a binary decision pair.

47. The method defined in claim 45 wherein the indication comprises a yes/no indicative.

48. The method in claim 45 wherein the probability comprises a probability estimate.

49. A method for performing coding on an input stream, wherein the input stream comprises a plurality of symbols from an alphabet of a symbols, said method comprising the steps of:

selecting a transition in one of a plurality of states in a transition machine having a plurality of states, wherein each of the plurality of states has at least one transition for each of the predetermined number of symbols in the alphabet, and wherein each of the transitions is associated with an output stream, wherein the transition in said one of said plurality of states is selected according to a symbol in the input stream;

outputting the output stream associated with said transition and transition to a next state, wherein a variable number of symbols is output from the transition machine for at least two distinct symbols in the input stream, such that the input stream is channel modulated and error correction coded.

50. A method for performing coding on an input stream, wherein the input stream comprises a plurality of symbols from an alphabet of a symbols, said method comprising the steps of:

selecting a transition in one of a plurality of states in a transition machine having a plurality of states, wherein each of the plurality of states has at least one transition for each of the predetermined number of symbols in the alphabet, and wherein each of the transitions is associated with an output stream, wherein the transition in said one of said plurality of states is selected according to a symbol in the input stream;

outputting the output stream associated with said transition and transition to a next state, wherein a variable number of symbols is output from the transition machine for at least two distinct symbols in the input stream, such that the input stream is compressed, channel modulated and error correction coded.

51. A method for performing coding on an input stream, wherein the input stream comprises a plurality of symbols from an alphabet of a symbols, said method comprising the steps of:

selecting a transition in one of a plurality of states in a transition machine having a plurality of states, wherein each of the plurality of states has at least one transition for each of the predetermined number of symbols in the alphabet, and wherein each of the transitions is associated with an output stream, wherein the transition in said one of said plurality of states is selected according to a symbol in the input stream;

outputting the output stream associated with said transition and transition to a next state, wherein a variable number of symbols is output from the transition machine for at least two distinct symbols in the input stream, such that the input stream is error correction coded and compressed.

52. An apparatus for performing channel modulation on an input bit streams having a plurality of input bits, said apparatus comprising:

a transition machine having a plurality of states, each of said plurality of states having at least one transition pair, and wherein each transition in said at least one transition pair is associated with an output bit stream that is output when each transition is selected, and further wherein said at least one transition pair is chosen according to a portion of said plurality of input bits, wherein each of the output bit streams comprises a channel coded and compressed representation of input bits;

means for selecting a transition in said at least one transition pair in said one of said states according to said portion of said plurality of input bits; and

means for outputting the output bit streams associated with said transition and transitioning to the next state, wherein a variable number of bits is output from the transition machine for each portion of said plurality of input bits, wherein a plurality of input bits are generated in response to the input bit streams, such that the input bit streams is channel coded and compressed by use of a single transition machine.

53. The apparatus defined in claim 52 wherein said transition machine comprises a ROM.

54. The apparatus defined in claim 52 wherein each portion of a plurality of input bits comprises one bit.

55. An apparatus for performing channel modulation on an input bit streams having a plurality of input bits, said apparatus comprising:

a transition machine having a plurality of states, each of said plurality of states having at least one transition pair, and wherein each transition in said at least one transition pair is associated with an output bit stream that is output when each transition is selected, and further wherein said at least one transition pair is chosen according to a portion of said plurality of input bits, wherein each of the output bit streams comprises a channel coded and channel error correction coded representation of input bits;

means for selecting a transition in said at least one transition pair in said one of said states according to said portion of said plurality of input bits; and

means for outputting the output bit streams associated with said transition and transitioning to the next state, wherein a variable number of bits is output from the transition machine for each portion of said plurality of input bits, wherein a plurality of input bits are generated in response to the input bit streams, such that the input bit stream is error correction coded and channel coded.

56. An apparatus for performing channel modulation on an input bit streams having a plurality of input bits, said apparatus comprising:

a transition machine having a plurality of states, each of said plurality of states having at least one transition pair, and wherein each transition in said at least one transition pair is associated with an output bit stream that is output when each transition is selected, and further wherein said at least one transition pair is chosen according to a portion of said plurality of input bits, wherein each of the output bit streams comprises a compressed, channel coded, and channel error correction coded representation of input bits;

means for selecting a transition in said at least one transition pair in said one of said states according to said portion of said plurality of input bits; and

means for outputting the output bit streams associated with said transition and transitioning to the next state, wherein a variable number of bits is output from the transition machine for each portion of said plurality of input bits, wherein a plurality of input bits are generated in response to the input bit streams, such that the input bit stream is compressed, error correction coded and channel coded.

57. An apparatus for performing error correction on an input bit stream having a plurality of input bits, said apparatus comprising a transition machine having a plurality of states, wherein each of the plurality of states has at least one transition pair and each of the transition in said at least one transition pair is associated with an output bit stream, wherein each output bit stream comprises a compressed and error correction coded representation of input bits;

means for selecting a transition in said at least one transition pair in said one of said states according to said portion of said plurality of input bits; and

means for outputting the output bit stream associated with said transition, wherein a variable number of bits is output from the transition machine for each portion of said plurality of input bits, wherein a plurality of output bits are generated in response to the input bit stream, such that the input bit stream is compressed and error correction coded.