SM codec method and apparatus

• US 4,847,842 A
• Filed: 11/19/1987
• Issued: 07/11/1989
• Est. Priority Date: 11/19/1987
• Status: Expired due to Term

• Current Assignee: Interdigital Technology Corporation (InterDigital, Inc.)
• Original Assignee: SCS Telecom, Inc.
• Inventors: Schilling, Donald L.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): BEAUSOLIEL JR, ROBERT W
• Application Number:
  US07/122,948
• Time in Patent Office: 600 Days
• Field of Search: 371/37, 371/38, 371/39, 371/40, 371/49, 371/50, 371/51, 371/35, 375/26, 375/27, 375/41, 375/42, 375/34
• US Class Current: 714/755
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes

Abstract

A Schilling-Manela encoding codec is provided comprising the steps of storing a block of a data-bit sequence in a memory, calculating parity-check symbols from parity-line symbols having p-bits per symbol along parity lines, and setting the parity-check symbols equal to the modulo-2^p sum of the data symbols. The data-bit sequence and parity-check symbols are transformed from Gray symbols, and the Gray symbols are transformed to modulation symbols. A Schilling-Manela decoding method is provided comprising the steps of storing an encoded data-bit sequence in a memory. The encoded-data-bit sequence includes a parity-check-symbol sequence which is stored in parity-memory cells, and a data-bit sequence which is blocked and stored in information-memory cells. The parity-check symbols and the data symbols along the parity lines in the information-memory cells are found. The count of each composite cell on a composite-error graph traversed by the path of each of the parity lines having an error is incremented and the largest-number cell in the composite-error graph having the largest number is determined. The largest number is compared to a threshold, and a new data symbol is chosen to minimize the count in the largest-number cell and substituted into the stored data-bit sequence.

Claims

1. A process for encoding a Schilling-Manela error correcting and detecting code comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information-memory cells and parity-check memory cells;

calculating parity-check symbols from data symbols, along at least two parity paths having different slopes in said information-memory cells by adding modulo-2^p the data symbols along each of the parity paths;

setting the parity-check symbol for each parity path equal to the modulo-2^p sum of the data symbols along each of the parity paths, respectively;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence; and

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel.

2. A process for encoding a Schilling-Manela error correcting and detecting code comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information-memory cells and parity-check memory cells;

calculating parity-check symbols from data symbols, along a first and a second set of parity lines, each of the first set of parity lines having a straight diagonal path with a first slope through said information-memory cells and each of the second set of parity lines having a straight diagonal path with a second slope through said information-memory cells, by adding modulo-2^p the parity-line symbols along each of the parity lines, respectively;

setting the parity-check symbol for each parity line equal to the modulo-2^p sum of the parity-line symbols along each parity line, respectively;

storing the parity-check symbols in parity-memory cells of said memory means;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence; and

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel.

3. A process for decoding a Schilling-Manela error correcting and detecting code encoded sequence, transformed by a Gray code and transformed to a modulation-symbol sequence, comprising the steps of:

transforming the modulation symbol sequence encoded with a Gray code into an encoded-data-symbol sequence;

storing the encoded-data-symbol sequence in memory means having at least g rows by h columns of information-memory cells and R_Max rows of parity-memory cells, wherein said encoded-data-symbol sequence includes a parity-check-symbol sequence having parity-check symbols stored in the R_Max rows of parity-memory cells, and a data-symbol sequence blocked and stored in the g rows by h columns of information-memory cells;

determining parity lines in memory means with data symbols and parity-check symbols, having an error;

incrementing a count of each composite cell on a composite-error graph traversed by a path of each of the parity lines having an error;

determining the largest-number cell in the composite-error graph having the largest number;

comparing the largest number to a threshold;

determining, provided the largest number exceeds the threshold, a new-data symbol for the memory cell in the information-memory cells corresponding to the largest-number cell in the composite-error graph having the largest number, wherein the new-data symbol minimizes the count in the largest-number cell; and

substituting the new-data symbol into the stored data-symbol sequence.

4. A process for decoding a data-symbol sequence encoded with a Schilling-Manela error correcting and detecting code encoded sequence, transformed by a Gray code and transformed to modulation symbol sequence, comprising the steps of:

transforming the modulation symbol sequence into an encoded-data-symbol sequence;

storing the encoded-data-symbol sequence in memory means having at least g rows by h columns of information-memory cells and R_Max rows of parity-memory cells, wherein said encoded-data-symbol sequence includes a parity-check-symbol sequence having parity-check symbols stored in the R_Max rows of parity-memory cells, and a data-symbol sequence having information symbols blocked and stored in the g rows by h columns of information-memory cells;

determining a first parity line in memory means with data symbols and parity-check symbols, having an error;

determining a second parity line in memory means with data symbols and parity-check symbols, having an error;

comparing the data symbols and parity-check symbols along the first and second parity lines, respectively, for determining the parity-line symbol having an error;

substituting a new symbol for the parity-line symbol having an error so that first and second parity lines are not in error; and

outputting the corrected data-symbol sequence.

5. A Schilling-Manela error correcting and detecting code encoding apparatus comprising:

memory means having g rows by h columns of information-memory cells and R_Max rows of parity-memory cells coupled to a data source for storing a block of a data-symbol sequence;

processor means coupled to said memory means for calculating parity-check symbols having p-bits per symbol, along a first and a second set of parity lines, each of the first set of parity lines having a straight diagonal path with a first slope through the g rows by h columns of said information-memory cells and each of the second set of parity lines having a straight diagonal path with a second slope through the g rows by h columns of said information-memory cells, by adding modulo-2^p the data symbols along each of the parity lines, respectively, and setting the parity-check symbol for each parity line equal to the modulo-2^p sum of the data symbols along each parity line, respectively, and storing the parity-check symbols in the parity-memory cells of said memory means, and outputting an encoded-data-symbol sequence comprising the data-symbol sequence and the parity-check symbols;

Gray means for transforming the encoded-data-symbol sequence into a Gray-symbol sequence; and

modulation means responsive to the Gray symbol sequence for generating a modulation-symbol sequence.

6. A Schilling-Manela error correcting and detecting code encoding apparatus comprising:

memory means having g rows by h columns of information-memory cells and R_max rows of parity-memory cells coupled to a data source for storing a block of a data-symbol sequence;

processor means coupled to said memory means for calculating a plurality of parity-check symbols from data symbols having p bits per symbol, along a plurality of parity paths in the g rows by h columns of said information-memory cells by adding modulo-2^p the data symbols along each of the parity paths, and setting the parity-check symbol for each parity path equal to the modulo-2^p sum of the data symbols along each of the parity paths, respectively;

Gray means for transforming an encoded-data-symbol sequence into a Gray-symbol sequence; and

modulation means responsive to the Gray symbol sequence for generating a modulation-symbol sequence.

7. A Schilling-Manela decoding apparatus comprising:

demodulation means coupled to a data source for transforming a modulation-symbol sequence into an encoded-data-symbol sequence;

memory means having at least g rows by h columns of information-memory cells and R_max rows of parity-memory cells, coupled to said demodulation means for storing a block of an encoded-data-symbol sequence, wherein said encoded-data-symbol sequence includes a parity-check-symbol sequence having parity-check symbols stored in the parity-memory cells and a data-symbol sequence having information symbols stored in the g rows by h columns of said information-memory cells;

a composite-error graph having g rows by h columns and R_max rows of composite cells; and

processor means coupled to said memory means and said composite-error graph for finding the parity-check symbols and the data symbols along parity lines in the g rows by h columns of information-memory cells, having an error, incrementing a count of each composite cell on the composite-error graph traversed by a path of each of the parity lines having an error, determining the largest-number cell in the composite-error graph having the largest number, comparing the largest number to a threshold, determining, provided the largest number exceeds the threshold, a new-data symbol for the memory cell in the information-memory cells corresponding to the largest-number cell in the composite-error graph having the largest number, wherein the new-data symbol minimizes the count in the largest-number cell, and substituting the new-data symbol into the information-memory cells.

8. A Schilling-Manela decoding apparatus comprising:

demodulation means coupled to a data source for transforming a modulation-symbol sequence into an encoded-data-symbol sequence;

memory means having at least g rows by h columns of information-memory cells and R_max rows of parity-memory cells, coupled to said demodulation means for storing a block of an encoded-data-bit sequence, wherein said encoded-data-bit sequence includes a parity-check-bit sequence having parity-check bits stored in the R_max rows of parity-memory cells and a data-bit sequence having information bits stored in the g rows by h columns of said information-memory cells;

a composite-error graph having g rows by h columns of composite cells; and

processor means coupled to said memory means and said composite-error graph for finding the parity-check bits and the data bits along parity lines in the g rows by h columns of information-memory cells, having an error, incrementing a count of each composite cell on a composite-error graph traversed by the path of each of the parity lines having an error, determining the largest-number cell in the composite-error graph having the largest number, comparing the largest number to a threshold, and inverting, provided the largest number exceeds the threshold, the data bit in the information-memory cells corresponding to the largest-number cell in the composite-error graph having the largest number, thereby a new-data bit minimizes the count in the largest-number cell.

9. A process for decoding a Schilling-Manela error correcting and detecting code comprising the steps of:

demodulating a modulation-symbol sequence into an encoded-data-symbol sequence;

storing the encoded-data-bit sequence in memory means having λ

-dimensional information-memory cells and R_max rows of parity-memory cells, wherein said encoded-data-symbol sequence includes a parity-check-symbol sequence having parity-check symbols stored in the parity-memory cells, and a data-symbol sequence blocked and stored in the λ

-dimensional information-memory cells;

finding the parity-check symbols and the data symbols along parity lines in the information-memory cells, having an error;

incrementing a count of each composite cell on a composite-error graph traversed by the path of each of the parity lines having an error;

determining the largest-number cell in the composite-error graph having the largest number;

comparing the largest number to a threshold;

determining, provided the largest number exceeds the threshold, a new-data symbol for the memory cell in the information-memory cells corresponding to the largest-number cell in the composite-error graph having the largest number, wherein the new-data symbol minimizes the count in the largest-number cell; and

substituting the new-data symbol into the stored data-symbol sequence.

10. A process for encoding a PASM error correcting and detecting code comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information-memory cells and parity-check memory cells;

calculating a first set of parity-check symbols from the data symbols along a first set of parity lines, by setting the parity-check symbol for each of the first set of parity-check symbols for each parity line equal to the modulo-2^p sum of the data symbols along each parity line, wherein each parity line of the first set of parity lines has a path with a first slope traversing through said information-memory cells, and said first set of parity-check symbols forms a first parity row located in said parity-check memory cells;

calculating at least a second set of parity-check symbols from the data symbols and parity-check symbols along a second set of parity lines, by setting the parity-check symbol for each of the second set of parity-check symbols for each parity line equal to the modulo-2^p sum of the data symbols and parity-check symbols along each parity line, wherein each parity line of the second set of parity lines has a path with a second slope traversing through said information-memory cells and through said first parity row, and said second set of parity-check symbols form a second parity row located in said parity-check memory cells;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence; and

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel.

11. A process for encoding a PASM error correcting and detecting code comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information-memory cells and parity-check memory cells;

calculating a first set of parity-check symbols from the data symbols along a first set of parity lines, by setting the parity-check symbol for each of the first set of parity-check symbols for each parity line equal to the modulo-2^p sum of the data symbols along each parity line, wherein each parity line of the first set of parity lines has a path with a first slope traversing through said information-memory cells, and said first set of parity-check symbols forms a first parity row located in said parity-check memory cells;

calculating a second set of parity-check symbols from the data symbols and parity-check symbols along a second set of parity lines, by setting the parity-check symbol for each of the second set of parity-check symbols for each parity line equal to the modulo-2^p sum of the data symbols and parity-check symbols along each parity line, wherein each parity line of the second set of parity lines has a path with a second slope traversing through said information-memory cells and through said first parity row, and said second set of parity-check symbols form a second parity row located in said parity-check memory cells;

calculating at least a third set of parity-check symbols from the data symbols and parity-check symbols along a third set of parity lines, by setting the parity-check symbol for each of the third set of parity-check symbols for each parity line equal to the modulo-2^p sum of the data symbols and parity-check symbols along each parity line, wherein each parity line of the third set of parity lines has a path with a third slope traversing through said information-memory cells and through said first and second parity rows, and said third set of parity-check symbols form a third parity row located in said parity-check memory cells;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence; and

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel.

12. A process for encoding a PASM error correcting and detecting code comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information-memory cells and parity-check memory cells;

calculating a first set of parity-check symbols from the data symbols along a first set of parity lines, wherein each parity line of the first set of parity lines has a path with a first slope traversing through said information-memory cells;

calculating a second set of parity-check symbols from the data symbols and parity-check symbols along a second set of parity lines, wherein each parity line of the second set of parity lines has a path with a second slope traversing through said information-memory cells and through said parity-check memory cells;

calculating at least a third set of parity-check symbols from the data symbols and parity-check symbols along a third set of parity lines, wherein each parity line of the third set of parity lines has a path with a third slope traversing through said information-memory cells and through said parity-check memory cells;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence; and

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel.

13. A process for encoding a PASM error correcting and detecting code comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information-memory cells and parity-check memory cells;

calculating a first set of parity-check symbols from the data symbols along a first set of parity lines, wherein each parity line of the first set of parity lines has a path with a first slope traversing through said information-memory cells;

storing said first set of parity-check symbols in a first parity row located in said parity-check memory cells;

calculating at least a second set of parity-check symbols from the data symbols and parity-check symbols along a second set of parity lines, wherein each parity line of the second set of parity lines has a path with a second slope traversing through said information-memory cells and through said first parity row;

storing said second set of parity-check symbols in a second parity row located in said parity-check memory cells;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence; and

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel.

14. A process for encoding a TASM error correcting and detecting code comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information memory cells and parity-check memory cells;

calculating a first parity-check symbol from data symbols and parity-check symbols located in the information memory cells and parity-check memory cells, respectively, along a first parity path having a first slope passing through the information memory cells and parity-check memory cells by adding modulo 2^p the data symbols and parity-check symbols along the first parity path;

storing said first parity-check symbol in a first parity row located in said parity-check memory cells;

calculating a second parity-check symbol from data symbols and parity-check symbols located in the information memory cells and parity-check memory cells, respectively, along a second parity path having a second slope by adding modulo 2^p the data symbols and parity-check symbols along the second parity path, wherein said second parity path traverses through said first parity-check symbol;

storing said second parity-check symbol in said second parity row;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence; and

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel.

15. A process for encoding a TASM error correcting and detecting code comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information memory cells and parity-check memory cells;

calculating a first parity-check symbol from data symbols and parity-check symbols located in the information memory cells and parity-check memory cells, respectively, along a first parity path having a first slope passing through the information memory cells and parity-check memory cells by adding modulo 2^p the data symbols and parity-check symbols along the first parity path;

storing said first parity-check symbol in a first parity row located in said parity-check memory cells;

calculating a second parity-check symbols from data symbols and parity-check symbols located in the information memory cells and parity-check memory cells, respectively, along a second parity path having a second slope by adding modulo 2^p the data symbols and parity-check symbols along the second parity path, wherein said second parity path traverses through said first parity-check symbol;

storing said second parity-check symbol in said second parity row;

calculating at least a third parity-check symbol from data symbols and parity-check symbols located in the information memory cells and parity-check memory cells, respectively, along a third parity path having a third slope passing through the second parity-check row, and through the information memory cells and parity-check memory cells, by adding modulo 2^p the data symbols and parity-check symbols along the third parity path, wherein said third parity path traverses through said second parity-check symbol;

storing said third parity-check symbol in a third parity row located in said parity-memory cells;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence; and

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel.

16. A process for encoding a TASM error correcting and detecting code comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information memory cells and parity-check memory cells;

calculating a first parity-check symbol from data symbols and parity-check symbols located in the information memory cells and parity-check memory cells, respectively, along a first parity path having a first slope passing through the information memory cells and parity-check memory cells;

calculating at least a second parity-check symbol from data symbols and parity-check symbols located in the information memory cells and parity-check memory cells, respectively, along a second parity path having a second slope, wherein said second parity path traverses through said first parity-check symbol;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence; and

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel.

17. A process for using a PASM error correcting and detecting code in an ARQ channel, comprising the steps of:

storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information memory cells and parity-check memory cells;

calculating a first parity-check symbol from data symbols located in the information memory cells along a first parity path having a first slope passing through the information memory cells;

calculating at least a second parity-check symbol from data symbols and parity-check symbols located in the information memory cells and parity-check memory cells, respectively, along a second parity path having a second slope;

transforming the data symbols and parity-check symbols into Gray symbols, having a minimum distance between adjacent symbols, and thereby generating a Gray symbol sequence;

transforming the Gray symbol sequence into a modulation symbol sequence, for transmission over a communications channel;

transmitting the modulation-symbol sequence comprising the data-symbol sequence and the first block of parity-check symbols, over a communications channel having a feedback channel;

demodulating the modulation-symbol sequence into an encoded-data-symbol sequence;

storing the encoded-data-symbol sequence in receiver-memory means having receiver-information-memory cells and receiver-parity-memory cells, wherein said encoded-data-symbol sequence includes a received-parity-check-symbol sequence having received-parity-check symbols stored in the receiver-parity-memory cells, and a receiver-data-symbol sequence blocked and stored in the receiver-information-memory cells;

finding the parity-check symbols and the data symbols along parity lines in receiver-information-memory cells, having an error;

incrementing a count of each composite cell on a composite-error graph traversed by the path of each of the parity lines having an error;

determining the largest-number cell in the composite-error graph having the largest number;

comparing the largest number to a threshold;

changing, provided the largest number exceeds the threshold, the data or parity-check symbol in the receiver-information-memory cells corresponding to the largest-number cell in the composite-error graph having the largest number, thereby the new-data symbol minimizes the count in the largest-number cell;

sending a retransmit request to the transmitter if some errors are not correctable;

sending a second block of parity-check symbols over the communications channel;

using the second set of parity-check symbols, repeating the steps of finding the parity-check symbols and the data or parity-check symbols along the parity lines in said receiver-memory means, having an error;

incrementing the count of each composite cell on a composite-error graph traversed by the path of each of the parity lines having an error;

determining the largest-number cell in the composite-error graph having the largest number;

comparing the largest number to a threshold; and

changing, provided the largest number exceeds the threshold, the data or parity-check symbol in the receiver-memory means corresponding to the largest-number cell in the composite-error graph having the largest number, thereby the new-data symbol minimizes the count in the largest-number cell.

18. A PASM error correcting and detecting code encoding apparatus comprising:

memory means coupled to a data source for storing a block of a data-symbol sequence;

processor means coupled to said memory means for calculating a first set of parity-check symbols from the data symbols along a first set of parity lines, wherein each parity line of the first set of parity lines has a path with a first slope traversing through said information-memory cells, and said first set of parity-check symbols forms a first parity row located in said parity-check memory cells, calculating at least a second set of parity-check symbols from the data symbols along a second set of parity lines, wherein each parity line of the second set of parity lines has a path with a second slope traversing through said information-memory cells and through said first parity row, and said second set of parity-check symbols form a second parity row located in said parity-check memory cells, and outputting an encoded-data-symbol sequence comprising the data-symbol sequence and the parity-check symbols;

Gray means for transforming the encoded-data-symbol sequence into a Gray-symbol sequence; and

modulation means responsive to the Gray symbol sequence for generating a modulation-symbol sequence.

19. A TASM error correcting and detecting code encoding apparatus comprising:

memory means coupled to a data source for storing a block of a data-symbol sequence having data symbols with p-bits per symbol, in memory means having information memory cells and parity-check memory cells;

processor means for calculating a first set of parity-check symbols from data symbols located in the information memory cells, along a first parity path having a first slope passing through the information memory cells and parity-check memory cells by adding modulo 2^p the data symbols and parity-check symbols along the first parity path;

storing said first set of parity-check symbols in a first parity row located in said parity-check memory cells;

calculating at least a second set of parity-check symbols from data symbols and parity-check symbols located in the information memory cells and parity-check memory cells, respectively, along a second parity path having a second slope by adding modulo 2^p the data symbols and parity-check symbols along the second parity path, wherein said second parity-check symbols are located at said second slope with reference to the first parity-check symbols, in a second parity row located in said parity-check memory cells;

storing said second parity-check symbols in said second parity row; and

outputting an encoded-data-symbol sequence comprising the data-symbol sequence and the parity-check sequence;

Gray means for transforming the encoded-data-symbol sequence into a Gray-symbol sequence; and

modulation means responsive to the Gray symbol sequence for generating a modulation-symbol sequence.