Nothing Special   »   [go: up one dir, main page]

US6697985B1 - Predictive forward error correction redundancy - Google Patents

Predictive forward error correction redundancy Download PDF

Info

Publication number
US6697985B1
US6697985B1 US09/677,671 US67767100A US6697985B1 US 6697985 B1 US6697985 B1 US 6697985B1 US 67767100 A US67767100 A US 67767100A US 6697985 B1 US6697985 B1 US 6697985B1
Authority
US
United States
Prior art keywords
code word
code
errors
primary
portions
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime, expires
Application number
US09/677,671
Inventor
Ishai Ilani
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Actelis Networks Inc
Original Assignee
Actelis Networks Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Actelis Networks Inc filed Critical Actelis Networks Inc
Priority to US09/677,671 priority Critical patent/US6697985B1/en
Assigned to ACTELIS NETWORKS INC. reassignment ACTELIS NETWORKS INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: ILANI, ISHAI
Application granted granted Critical
Publication of US6697985B1 publication Critical patent/US6697985B1/en
Assigned to MIGDALOR INVESTMENT FUND IN BUSINESS, LIMITED PARTNERSHIP reassignment MIGDALOR INVESTMENT FUND IN BUSINESS, LIMITED PARTNERSHIP SECURITY INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: ACTELIS NETWORKS INC.
Adjusted expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0056—Systems characterized by the type of code used
    • H04L1/0057—Block codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/25—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM]
    • H03M13/253—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] with concatenated codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/25—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM]
    • H03M13/256—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] with trellis coding, e.g. with convolutional codes and TCM
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2906—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2906—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
    • H03M13/2927—Decoding strategies
    • H03M13/293—Decoding strategies with erasure setting
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2933—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using a block and a convolutional code
    • H03M13/2936—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using a block and a convolutional code comprising an outer Reed-Solomon code and an inner convolutional code
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0041—Arrangements at the transmitter end
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0045—Arrangements at the receiver end
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0056—Systems characterized by the type of code used
    • H04L1/0059—Convolutional codes
    • H04L1/006—Trellis-coded modulation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0056—Systems characterized by the type of code used
    • H04L1/0064—Concatenated codes
    • H04L1/0065—Serial concatenated codes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0056—Systems characterized by the type of code used
    • H04L1/0071—Use of interleaving
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
    • H03M13/1515—Reed-Solomon codes

Definitions

  • the present invention relates to data telecommunications in general, and more particularly to forward error correction therefor.
  • FEC Forward Error Correction
  • FEC is used to find and correct limited errors caused by a transport or storage system in order to ensure the validity of the received message without requiring retransmissions.
  • FEC encoding techniques such as Reed-Solomon (RS) encoding, provide data redundancy by adding extra code symbols to a transmitted message which provide the necessary detection and correction information. The number of redundant symbols is determined by the amount and type of error correction required.
  • RS encoding is an example of a block code where the data to be transmitted are divided into blocks, with each block comprising k symbols of data.
  • code rate refers to the ratio k/n, and is used to express the average amount of data symbols versus the amount of transmitted symbols.
  • a code rate of 0.8 would indicate that the average over all time intervals T of the ratio of data symbols that were encoded in time interval T to the total number of transmitted symbols in time interval T, is 80%.
  • the additional redundancy symbols must contain enough information to allow the position of an erroneous information symbol to be located and its value determined.
  • Some symbols that are either known or suspected to be in error or otherwise unreliable may be labeled as “erasures.” The position of each erasure may be provided in advance to the decoder which then ignores the actual value of the erasure and instead reconstructs its value using the redundancy symbols.
  • a forward error correction system including a coder operative to encode a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, at least one transmitting modem for transmitting the code words, at least one receiving modem for receiving the code words, a decoder operative to detect errors in any of the code words, correct any of the errors and erasures in the code words, and communicate the positions of any of the errors, and a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions to the decoder.
  • the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
  • the coder is a Reed-Solomon coder.
  • code words are either of systematic, non-systematic, and convolutional code words.
  • code words are of different lengths.
  • the at least one transmitting modem includes a plurality of transmitting modems, and the system further includes a demultiplexer for demultiplexing the code words, thereby causing each of the transmitting modems to transmit a different portion of each of the code words.
  • the at least one receiving modem includes a plurality of receiving modems for receiving the different portions of each of the code words, and the system further includes a multiplexer for multiplexing the portions, thereby reconstructing the code words.
  • the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
  • system further includes an interleaver for interleaving the code words, and a deinterleaver for deinterleaving the interleaved code words.
  • the controller is operative to send a configuration signal to the decoder configuring the decoder for decoding either of the primary and the secondary code words.
  • a forward error correction system including a coder operative to encode a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, a demultiplexer for demultiplexing each of the code words into a plurality of portions, a plurality of transmitting modems, each transmitting modem for transmitting a different one of the plurality of portions, a plurality of receiving modems for receiving the plurality of portions, a multiplexer for multiplexing the plurality of portions, thereby reconstructing the code words, a primary decoder operative to detect any errors in any of the primary code words, correct any of the errors, and communicate the positions of any of the errors, a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as
  • the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
  • the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
  • code words are either of systematic, non-systematic, and convolutional code words.
  • code words are of different lengths.
  • system further includes an interleaver for interleaving the code words, and a deinterleaver for deinterleaving the interleaved code words.
  • a forward error correction system including a coder operative to encode a data stream into at least one code word at a first code rate, a demultiplexer for demultiplexing the code word into a plurality of portions, a plurality of transmitting modems, each transmitting modem for transmitting a different one of the plurality of portions, a plurality of receiving modems for receiving the plurality of portions, where any of the modems is operative to determine its function status and transmit a signal indicating the status, a multiplexer for multiplexing the plurality of portions, thereby reconstructing the code word, a decoder operative to detect any errors in the code word, correct any of the errors, and correct erasures, and a controller operative to receive the signal and, where the signal indicates that any of the modems is functioning improperly, report erasure positions corresponding to the portion transmitted by the improperly functioning modem to the decoder, where the decoder is operative to receive the report of erasure
  • the controller is operative to instruct either of the encoder and the decoder to encode at a second code rate having a sufficient redundancy to accommodate the number of the errors and erasures.
  • a forward error correction system including an outer coder operative to encode a data stream into at least one outer code word, an inner coder operative to encode the outer code word into at least one inner code word using either of an error correcting code and an error checking code, a communications channel for transmitting the inner code word, an inner decoder operative to receive the transmitted inner code word from the communications channel, determine the validity of the inner code word, communicate the validity of the inner code word, and decode the inner code word, thereby reconstituting the outer code word, a controller operative to receive from the inner coder the communication of validity of the inner code word, map the inner code word to its corresponding position in the reconstituted outer code word, and, where the inner code word is invalid, and report the position as an erasure position, and an outer decoder operative to receive the reconstituted outer code word from the inner decoder and the erasure positions from the inner decoder, detect errors in the reconstituted outer code word, and correct any of the errors and
  • the outer coder is a Reed-Solomon coder and the outer decoder is a Reed-Solomon decoder.
  • the inner coder and the inner decoder employ Trellis Coded Modulation.
  • the inner coder and the inner decoder employ Cyclic Redundancy Checking.
  • system further includes an interleaver for interleaving the code words, and a deinterleaver for deinterleaving the interleaved code words.
  • a forward error correction method including encoding a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, transmitting the code words from a transmitting modem to a receiving modem, detecting any errors in any of the transmitted code words, predicting from any of the errors in the primary code word at least one error in the secondary code word, and reporting any of the predicted errors as erasure positions.
  • the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
  • the transmitting step includes demultiplexing the code words into a plurality of code word portions, transmitting the portions via a plurality of transmitting modems, receiving the portions via a plurality of receiving modems, and multiplexing the plurality of portions, thereby reconstructing the code word.
  • the method further includes interleaving the code words prior to the transmitting step, and deinterleaving the interleaved code words subsequent to the transmitting step.
  • the method further includes configuring the decoder for decoding either of the primary and the secondary code words.
  • the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
  • the predicting step includes predicting after determining that the number of errors detected in any of the portions exceeds a predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
  • the method further includes interleaving the code words prior to the demultiplexing step, and deinterleaving the interleaved code words subsequent to the multiplexing step.
  • a forward error correction method including encoding a data stream into at least one code word at a first code rate, demultiplexing each of the code words into a plurality of portions, transmitting a different one of the plurality of portions via a plurality of transmitting modems, receiving a different one of the plurality of portions via a plurality of receiving modems, multiplexing the plurality of portions, thereby reconstructing the code words, determining the function status of any of the modems, and where any of the modems is functioning improperly, decoding as erasures the portion transmitted by the improperly functioning modem.
  • a forward error correction method including firstly encoding a data stream into at least one outer code word, secondly encoding the outer code word into at least one inner code word using either of an error correcting code and an error checking code, transmitting the inner code word, receive the transmitted inner code word, determining the validity of the transmitted inner code word, firstly decoding the inner code word, thereby reconstituting the outer code word, mapping the inner code word to its corresponding position in the reconstituted outer code word, and where the inner code word is invalid, secondly decoding the reconstituted outer code word where the position is treated as an erasure position.
  • the firstly coding step includes coding using Reed-Solomon coding and the secondly decoding step includes decoding using Reed-Solomon decoding.
  • the secondly coding step includes coding using Trellis Coded Modulation coding and the firstly decoding step includes decoding using Trellis Coded Modulation decoding.
  • the secondly coding step includes coding using Cyclic Redundancy Check coding and the firstly decoding step includes decoding using Cyclic Redundancy Check decoding.
  • a forward error correction system including a decoder operative to receive the code words, detect errors in any of the code words, correct any of the errors and erasures in the code words, and communicate the positions of any of the errors, and a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions to the decoder.
  • system further includes a coder operative to encode the data stream.
  • system further includes at least one transmitting modem for receiving the code words ultimately from the coder and transmitting the code words, and at least one receiving modem for receiving the code words from the at least one transmitting modem and for providing the code words ultimately to the decoder.
  • the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
  • the at least one transmitting modem includes a plurality of transmitting modems and the system further includes a demultiplexer intermediate the coder and the transmitting modems for demultiplexing the code words, thereby causing each of the transmitting modems to transit a different portion of each of the code words.
  • the at least one receiving modem includes a plurality of receiving modems for receiving the different portions of each of the code words and the system further includes a multiplexer intermediate the receiving modems and the decoder for multiplexing the portions, thereby reconstructing the code words.
  • the controller is operative to predict after determining the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
  • system further includes an interleaver intermediate the coder and the at least one transmitting modem for interleaving the code words, and a deinterleaver intermediate the at least one receiving modem and the decoder for deinterleaving the interleaved code words.
  • the controller is operative to send a configuration signal to the decoder configuring the decoder for decoding either of the primary and the secondary code words.
  • a forward error correction system including a primary decoder operative to receive the primary code words, detect any errors in any of the primary code words, correct any of the errors, and communicate the positions of any of the errors, a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions, and a secondary decoder operative to receive the report of erasure positions and correct any of the erasures in the secondary code words.
  • system further includes a coder operative to encode the data stream.
  • system further includes at least one transmitting modem for receiving the code words ultimately from the coder and transmitting the code words, and at least one receiving modem for receiving the code words from the at least one transmitting modem and for providing the code words ultimately to either of the decoders.
  • the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
  • the at least one transmitting modem includes a plurality of transmitting modems and the system further includes a demultiplexer intermediate the coder and the transmitting modems for demultiplexing the code words, thereby causing each of the transmitting modems to transmit a different portion of each of the code words.
  • the at least one receiving modem includes a plurality of receiving modems for receiving the different portions of each of the code words and the system further includes a multiplexer intermediate the receiving modems and the decoders for multiplexing the portions, thereby reconstructing the code words.
  • the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
  • system further includes an interleaver intermediate the coder and the at least one transmitting modem for interleaving the code words, and a deinterleaver intermediate the at least one receiving modem and the decoders for deinterleaving the interleaved code words.
  • a forward error correction system including a plurality of receiving modems for receiving the plurality of portions, where any of the modems is operative to determine its function status and transmit a signal indicating the status, a multiplexer for multiplexing the plurality of portions, thereby reconstructing the code word, a decoder operative to detect any errors in the code word, correct any of the errors, and correct erasures, and a controller operative to receive the signal and, where the signal indicates that any of the modems is functioning improperly, report erasure positions corresponding to the portion transmitted by the improperly functioning modem to the decoder, where the decoder is operative to receive the report of erasure positions and correct any of the erasures in any of the code words.
  • system further includes a coder operative to encode the data stream.
  • the controller is operative to instruct either of the encoder and the decoder to encode at a second code rate having a sufficient redundancy to accommodate the number of the errors and erasures.
  • system further includes at least one transmitting modem for receiving the code words ultimately from the coder and transmitting the code words.
  • the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
  • the at least one transmitting modem includes a plurality of transmitting modems and the system further includes a demultiplexer intermediate the coder and the transmitting modems for demultiplexing the code words, thereby causing each of the transmitting modems to transmit a different portion of each of the code words.
  • the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
  • system further includes an interleaver intermediate the coder and the at least one transmitting modem for interleaving the code words, and a deinterleaver intermediate the at least one receiving modem and the decoder for deinterleaving the interleaved code words.
  • a forward error correction system including an inner decoder operative to receive the inner code word, determine the validity of the inner code word, communicate the validity of the inner code word, and decode the inner code word, thereby reconstituting the outer code word, a controller operative to receive from the inner coder the communication of validity of the inner code word, map the inner code word to its corresponding position in the reconstituted outer code word, and, where the inner code word is invalid, and report the position as an erasure position, and an outer decoder operative to receive the reconstituted outer code word from the inner decoder and the erasure positions from the inner decoder, detect errors in the reconstituted outer code word, and correct any of the errors and erasures in the reconstituted outer code word.
  • system further includes an outer coder operative to encode the data stream into the at least one outer code word, an inner coder operative to encode the outer code word into the at least one inner code word, and a communications channel for transmitting the inner code word to the inner decoder.
  • a forward error correction method including detecting any errors in any of the transmitted code words, predicting from any of the errors in the primary code word at least one error in the secondary code word, and correcting any of the predicted errors as erasure positions in any of the secondary code words.
  • the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
  • the method further includes coding the data stream at a coder, demultiplexing the code words into a plurality of code word portions, transmitting the portions via a plurality of transmitting modems, receiving the portions via a plurality of receiving modems, and multiplexing the plurality of portions, thereby reconstructing the code word.
  • the method further includes interleaving the code words prior to the transmitting step, and deinterleaving the interleaved code words subsequent to the transmitting step.
  • the method further includes configuring the decoder for decoding either of the primary and the secondary code words.
  • a forward error correction method including detecting any errors in any of the primary code words at a primary decoder, predicting from any of the errors in the primary code word at least one error in the secondary code word, and correcting any of the predicted errors as erasures in the secondary code words at a secondary encoder.
  • the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
  • the method further includes coding the data stream at a coder, demultiplexing the code words into a plurality of code word portions, transmitting the portions via a plurality of transmitting modems, receiving the portions via a plurality of receiving modems, and multiplexing the plurality of portions, thereby reconstructing the code word.
  • the method further includes interleaving the code words prior to the transmitting step, and deinterleaving the interleaved code words subsequent to the transmitting step.
  • a forward error correction method including receiving a different one of the plurality of portions via a plurality of receiving modems, multiplexing the plurality of portions, thereby reconstructing the code words, determining the function status of any of the modems, and where any of the modems is functioning improperly, correcting as erasures the portion transmitted by the improperly functioning modem.
  • a forward error correction method including determining the validity of the transmitted inner code word, firstly decoding the inner code word, thereby reconstituting the outer code word, mapping the inner code word to its corresponding position in the reconstituted outer code word, and where the inner code word is invalid, secondly decoding the reconstituted outer code word where the position is treated as an erasure position.
  • the method further includes firstly coding using Reed-Solomon coding and where the secondly decoding step includes decoding using Reed-Solomon decoding.
  • the secondly coding step includes coding using Trellis Coded Modulation coding and the firstly decoding step includes decoding using Trellis Coded Modulation decoding.
  • the secondly coding step includes coding using Cyclic Redundancy Check coding and the firstly decoding step includes decoding using Cyclic Redundancy Check decoding.
  • references to code words having a data portion and a redundancy portion may be understood as either referring to distinct data and redundancy portions common to systematic coding techniques, or indistinct, co-mingled portions common to non-systematic and convolutional coding techniques. It is further appreciated throughout the specification and claims that references to elements of the invention “reporting” information to other elements of the invention refers to the providing of information through notifications, indications, signals, or any other suitable communication technique known in the art.
  • FIGS. 1-5 taken separately, are simplified block-flow diagrams of a forward error correction system, each constructed and operative in accordance with a different preferred embodiment of the present invention.
  • FIG. 1 is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention.
  • a data stream is encoded at a coder 10 , such as a Reed-Solomon coder, into one or more code words 12 , each typically having a data portion k and a redundancy portion r.
  • the code words 12 are then demultiplexed at a demultiplexer 14 for parallel transmission via a plurality of modems in a modem pool 16 , where each modem preferably transmits a different portion of each code word 12 .
  • the transmissions are then received by a plurality of modems in a modem pool 18 , and multiplexed at a multiplexer 20 into reconstituted code words 22 that correspond to code words 12 .
  • Code words 22 are then decoded at a decoder 24 .
  • Redundancy portion r preferably provides sufficient redundancy to allow correction of a predetermined number of errors.
  • redundancy portion r comprises sufficient redundancy to allow the system to recover from a failure of a predetermined number of modems in either of modem pools 16 and 18 .
  • the redundancy portion r in each code word should comprise at least 20% of the code word length, thus providing a code rate of 0.8.
  • FIG. 2 is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention.
  • a data stream is encoded at a coder 30 , such as a Reed-Solomon coder, into one or more code words 32 , each typically having a data portion k and a redundancy portion r.
  • the code words 32 are then demultiplexed at a demultiplexer 34 for parallel transmission via a plurality of modems in a modem pool 36 , where each modem preferably transmits a different portion of each code word 32 .
  • the transmissions are then received by a plurality of modems in a modem pool 38 , and multiplexed at a multiplexer 40 into reconstituted code words 42 that correspond to code words 32 .
  • Code words 42 are then decoded at a decoder 44 .
  • Each modem in modem pool 38 is preferably able to determine whether or not it is functioning properly using conventional techniques, such as through the detection of a received power signal or synchronization word, and preferably sends a status signal to a controller 46 indicating such.
  • controller 46 informs decoder 44 that those portions of the code words transmitted by the malfunctioning modem are to be treated as erasures and sends a signal indicating their positions to decoder 44 .
  • Controller 46 may optionally send a configuration signal to both encoder 30 and decoder 44 to change the coding parameters to accommodate the number of errors and erasures encountered by increasing or decreasing the amount of redundancy in the code words.
  • the code rate of the system of FIG. 2 may be increased from 0.8 to 0.9, and the system will recover from a failure of one modem by marking the positions of those symbols which were to be transmitted via the malfunctioning modem as erasures.
  • FIG. 3 is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention.
  • a data stream is encoded at a coder 50 , typically a Reed-Solomon coder, into one or more primary code words 52 and one or more secondary code words 54 .
  • code words 52 and 54 are shown as having the same code word length and are represented using systematic encoding, where the data and redundancy portions are not intermingled, it is appreciated that code words 52 and 54 may use either systematic or non-systematic encoding and that their lengths may be different.
  • Primary code word 52 typically comprises a data portion k and a redundancy portion r.
  • Redundancy portion r preferably comprises sufficient redundancy to allow correction of a predetermined number of errors.
  • Secondary code words 54 preferably comprise a redundancy portion r ⁇ and a data portion ⁇ in addition to data portion k.
  • Redundancy portion r ⁇ preferably comprises sufficient redundancy to allow correction of a predetermined number of erasures, and may therefore be up to half as large as redundancy portion r of primary code word 52 .
  • the size of data portion ⁇ preferably corresponds to the reduction in size of redundancy portion r ⁇ as compared to redundancy portion r of primary code words 52 .
  • the primary and secondary code words 52 and 54 are then preferably interleaved in accordance with conventional techniques at an interleaver 56 and demultiplexed at a demultiplexer 58 for parallel transmission via one or more modems in a modem pool 60 , where each modem preferably transmits a different portion of each code word.
  • the demultiplexed code word portions are received by modems in a modem pool 62 , multiplexed back into interleaved code words at a multiplexer 64 , and deinterleaved at a deinterleaver 66 into primary and secondary code words 68 and 70 corresponding to primary and secondary code words 52 and 54 .
  • Primary code word 68 is then preferably fed into a primary decoder 72 which detects and corrects any errors in primary code word 68 .
  • the position of any errors found in primary code word 68 are provided to a controller 76 which is preferably configured to predict which positions in the secondary code words are vulnerable to errors and mark these positions as erasures.
  • controller 76 may be configured to determine whether the number of errors detected in a code word portion received via a particular modem exceeds a predetermined error threshold. If the threshold is exceeded, then the modem and/or its connection is deemed to be unreliable, and each position in the code word portions subsequently received therefrom are treated as erasures. The erasure positions are then communicated from controller 76 to a secondary decoder 74 . Secondary code words 70 are then fed into secondary decoder 74 which decodes the secondary code words 70 and corrects for the erasures indicated by controller 76 . The decoded output from primary and secondary decoders 72 and 74 are then preferably fed to a multiplexer 78 , thus reconstructing the original data stream. Processing preferably continues in a cyclical manner, with primary code words followed by secondary code words followed by primary code words, etc.
  • a communication system employing the coding system of FIG. 3 with one primary code word having a code rate of 0.8 (20% redundancy) followed by four secondary code words having a code rate of 0.9 (10% redundancy) will provide good protection against a single modem failure with an overall code rate of 0.88 (12% redundancy).
  • FIG. 4 is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention.
  • the system of FIG. 4 is substantially similar to the system of FIG. 3 with the notable exception that primary decoder 72 is capable of decoding both primary and secondary code words 68 and 70 without the need for secondary decoder 74 .
  • controller 76 indicates the erasure positions to primary decoder 72 , and optionally may send a configuration signal to primary decoder 72 to change its decoding parameters accordingly in order to selectably decode both primary and secondary code words 68 and 70 .
  • FIG. 5 is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention.
  • a data stream is encoded at a outer coder 80 , such as a Reed-Solomon coder, into one or more outer code words 82 , each typically having a data portion k and a redundancy portion r.
  • outer code words 82 are then interleaved at an interleaver 84 and coded at a inner coder 86 into one or more inner code words 88 .
  • Inner coder 86 may employ an error correcting code, such as Trellis Coded Modulation (TCM), or an error checking code, such as Cyclic Redundancy Checking (CRC) Inner code words 88 are then transmitted via a communications channel 90 , which may include one or more modems or any other transmission medium.
  • TCM Trellis Coded Modulation
  • CRC Cyclic Redundancy Checking
  • the transmission is decoded at an inner decoder 92 , whose decoding method corresponds to the coding method used by inner coder 86 , and deinterleaved at a deinterleaver 94 to form reconstituted outer code words 96 that correspond to outer code words 82 .
  • Inner decoder 92 preferably checks whether inner code words 88 are valid code words in accordance with the employed error correcting code.
  • Inner decoder 92 notifies a controller 98 of each inner code word 88 that is found to be invalid. Controller 98 in turn maps the positions of each invalid code word 88 to its corresponding position in outer code word 96 and marks the position as an erasure. Controller 98 then communicates the positions of the erasures to an outer decoder 100 , whose decoding method corresponds to the coding method used by outer coder 80 , which then decodes the outer code words 96 into the original data stream.
  • outer coder 80 employs a RS code, where each symbol of the RS code is a byte, 8 bits in length.
  • each code word of the RS code will contain k+r bytes or 8(k+r) bits.
  • each k bytes of data of each outer code word 82 would be coded into 9(k+r) bits.
  • each 9-bit inner code word 88 is checked for parity. If parity is violated, the corresponding byte of the reconstituted outer code word 96 comprising the 8 data bits of the inner code word 88 is marked as an erasure.
  • the system of FIG. 5 demonstrates that whenever a concatenated coding scheme is used, such as Reed-Solomon/Vitterbi in ADSL systems, the inner decoder may be used to mark erasures and thereby improve the performance of the outer decoder.
  • a concatenated coding scheme such as Reed-Solomon/Vitterbi in ADSL systems
  • the present invention has been described with respect to RS encoding, it is appreciated that the present invention may easily be implemented for use with other codes, including block codes and convolutional codes.
  • the present invention is also applicable to codes employing soft decisions where erasures are designated by assigning 1 to the ratio pr b (1)/pr b (0) (or 0 to log(pr b (1)/pr b (0)) for a bit to be erased, where pr b (0)denotes the a priori probability that bit b is 0, and pr b (1) denotes the a priori probability that bit b is 1. It is further appreciated that any conventional error location mechanism may be used.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Prevention Of Errors In Transmission (AREA)

Abstract

A forward error correction system including a coder operative to encode a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, at least one transmitting modem for transmitting the code words, at least one receiving modem for receiving the code words, a decoder operative to detect errors in any of the code words, correct any of the errors and erasures in the code words, and communicate the positions of any of the errors, and a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions to the decoder.

Description

FIELD OF THE INVENTION
The present invention relates to data telecommunications in general, and more particularly to forward error correction therefor.
BACKGROUND OF THE INVENTION
The use of Forward Error Correction (FEC) techniques in the design of digital communications and storage systems is well known. FEC is used to find and correct limited errors caused by a transport or storage system in order to ensure the validity of the received message without requiring retransmissions. In general, FEC encoding techniques, such as Reed-Solomon (RS) encoding, provide data redundancy by adding extra code symbols to a transmitted message which provide the necessary detection and correction information. The number of redundant symbols is determined by the amount and type of error correction required. RS encoding is an example of a block code where the data to be transmitted are divided into blocks, with each block comprising k symbols of data. An additional r redundancy symbols are then added to each block of k data symbols to form a code word of length n=k+r. The “code rate” of the code refers to the ratio k/n, and is used to express the average amount of data symbols versus the amount of transmitted symbols. Thus, a code rate of 0.8 would indicate that the average over all time intervals T of the ratio of data symbols that were encoded in time interval T to the total number of transmitted symbols in time interval T, is 80%.
In general, the additional redundancy symbols must contain enough information to allow the position of an erroneous information symbol to be located and its value determined. For example, an RS decoder can detect and correct up to r/2 incorrect symbols if there are (r=n−k) redundant symbols in each code word, as one redundant symbol is used to detect and locate each error, and one more redundant symbol is used to identify the precise value of that error. Some symbols that are either known or suspected to be in error or otherwise unreliable may be labeled as “erasures.” The position of each erasure may be provided in advance to the decoder which then ignores the actual value of the erasure and instead reconstructs its value using the redundancy symbols. Since the position of each erasure is known, only one redundant symbol is needed to reconstruct the value of an erasure, and an additional redundant symbol to determine the location of the erasure is not required. In general, if a code word contains E symbols that are erasures whose locations are known and e symbols that are errors with unknown locations, the code word can be correctly decoded provided that (2e+E)<r. If the locations of all the errors are known to the decoder, the message can be correctly decoded provided that E<r, thus requiring half the number of redundant symbols needed to correct errors whose locations are not known.
While conventional FEC techniques may be used more or less successfully to correct errors, they generally must be designed with a redundancy that is greater than the number of errors they are expected to correct, with RS codes requiring up to twice as many redundancy symbols as error symbols. Thus, the greater the redundancy, the less room there is for data in each code word and the less throughput of the communication channel due to error correction overhead.
SUMMARY OF THE INVENTION
In one aspect of the present invention a forward error correction system is provided including a coder operative to encode a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, at least one transmitting modem for transmitting the code words, at least one receiving modem for receiving the code words, a decoder operative to detect errors in any of the code words, correct any of the errors and erasures in the code words, and communicate the positions of any of the errors, and a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions to the decoder.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the coder is a Reed-Solomon coder.
In another aspect of the present invention the code words are either of systematic, non-systematic, and convolutional code words.
In another aspect of the present invention the code words are of different lengths.
In another aspect of the present invention the at least one transmitting modem includes a plurality of transmitting modems, and the system further includes a demultiplexer for demultiplexing the code words, thereby causing each of the transmitting modems to transmit a different portion of each of the code words.
In another aspect of the present invention the at least one receiving modem includes a plurality of receiving modems for receiving the different portions of each of the code words, and the system further includes a multiplexer for multiplexing the portions, thereby reconstructing the code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the system further includes an interleaver for interleaving the code words, and a deinterleaver for deinterleaving the interleaved code words.
In another aspect of the present invention the controller is operative to send a configuration signal to the decoder configuring the decoder for decoding either of the primary and the secondary code words.
In another aspect of the present invention a forward error correction system is provided including a coder operative to encode a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, a demultiplexer for demultiplexing each of the code words into a plurality of portions, a plurality of transmitting modems, each transmitting modem for transmitting a different one of the plurality of portions, a plurality of receiving modems for receiving the plurality of portions, a multiplexer for multiplexing the plurality of portions, thereby reconstructing the code words, a primary decoder operative to detect any errors in any of the primary code words, correct any of the errors, and communicate the positions of any of the errors, a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions, a secondary decoder operative to receive the report of erasure positions and correct any of the erasures in the secondary code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the coder is a Reed-Solomon coder.
In another aspect of the present invention the code words are either of systematic, non-systematic, and convolutional code words.
In another aspect of the present invention the code words are of different lengths.
In another aspect of the present invention the system further includes an interleaver for interleaving the code words, and a deinterleaver for deinterleaving the interleaved code words.
In another aspect of the present invention a forward error correction system is provided including a coder operative to encode a data stream into at least one code word at a first code rate, a demultiplexer for demultiplexing the code word into a plurality of portions, a plurality of transmitting modems, each transmitting modem for transmitting a different one of the plurality of portions, a plurality of receiving modems for receiving the plurality of portions, where any of the modems is operative to determine its function status and transmit a signal indicating the status, a multiplexer for multiplexing the plurality of portions, thereby reconstructing the code word, a decoder operative to detect any errors in the code word, correct any of the errors, and correct erasures, and a controller operative to receive the signal and, where the signal indicates that any of the modems is functioning improperly, report erasure positions corresponding to the portion transmitted by the improperly functioning modem to the decoder, where the decoder is operative to receive the report of erasure positions and correct any of the erasures in any of the code words.
In another aspect of the present invention the controller is operative to instruct either of the encoder and the decoder to encode at a second code rate having a sufficient redundancy to accommodate the number of the errors and erasures.
In another aspect of the present invention a forward error correction system is provided including an outer coder operative to encode a data stream into at least one outer code word, an inner coder operative to encode the outer code word into at least one inner code word using either of an error correcting code and an error checking code, a communications channel for transmitting the inner code word, an inner decoder operative to receive the transmitted inner code word from the communications channel, determine the validity of the inner code word, communicate the validity of the inner code word, and decode the inner code word, thereby reconstituting the outer code word, a controller operative to receive from the inner coder the communication of validity of the inner code word, map the inner code word to its corresponding position in the reconstituted outer code word, and, where the inner code word is invalid, and report the position as an erasure position, and an outer decoder operative to receive the reconstituted outer code word from the inner decoder and the erasure positions from the inner decoder, detect errors in the reconstituted outer code word, and correct any of the errors and erasures in the reconstituted outer code word.
In another aspect of the present invention the outer coder is a Reed-Solomon coder and the outer decoder is a Reed-Solomon decoder.
In another aspect of the present invention the inner coder and the inner decoder employ Trellis Coded Modulation.
In another aspect of the present invention the inner coder and the inner decoder employ Cyclic Redundancy Checking.
In another aspect of the present invention the system further includes an interleaver for interleaving the code words, and a deinterleaver for deinterleaving the interleaved code words.
In another aspect of the present invention a forward error correction method is provided including encoding a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, transmitting the code words from a transmitting modem to a receiving modem, detecting any errors in any of the transmitted code words, predicting from any of the errors in the primary code word at least one error in the secondary code word, and reporting any of the predicted errors as erasure positions.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the transmitting step includes demultiplexing the code words into a plurality of code word portions, transmitting the portions via a plurality of transmitting modems, receiving the portions via a plurality of receiving modems, and multiplexing the plurality of portions, thereby reconstructing the code word.
In another aspect of the present invention the method further includes interleaving the code words prior to the transmitting step, and deinterleaving the interleaved code words subsequent to the transmitting step.
In another aspect of the present invention the method further includes configuring the decoder for decoding either of the primary and the secondary code words.
In another aspect of the present invention a forward error correction method is provided including encoding a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, demultiplexing each of the code words into a plurality of portions, transmitting a different one of the plurality of portions via a plurality of transmitting modems, receiving a different one of the plurality of portions via a plurality of receiving modems, multiplexing the plurality of portions, thereby reconstructing the code words, detecting any errors in any of the primary code words at a primary decoder, predicting from any of the errors in the primary code word at least one error in the secondary code word, reporting any of the predicted errors as erasure positions to a secondary decoder, and correcting any of the erasures in the secondary code words at the secondary encoder.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in any of the portions exceeds a predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the method further includes interleaving the code words prior to the demultiplexing step, and deinterleaving the interleaved code words subsequent to the multiplexing step.
In another aspect of the present invention a forward error correction method is provided including encoding a data stream into at least one code word at a first code rate, demultiplexing each of the code words into a plurality of portions, transmitting a different one of the plurality of portions via a plurality of transmitting modems, receiving a different one of the plurality of portions via a plurality of receiving modems, multiplexing the plurality of portions, thereby reconstructing the code words, determining the function status of any of the modems, and where any of the modems is functioning improperly, decoding as erasures the portion transmitted by the improperly functioning modem.
In another aspect of the present invention a forward error correction method is provided including firstly encoding a data stream into at least one outer code word, secondly encoding the outer code word into at least one inner code word using either of an error correcting code and an error checking code, transmitting the inner code word, receive the transmitted inner code word, determining the validity of the transmitted inner code word, firstly decoding the inner code word, thereby reconstituting the outer code word, mapping the inner code word to its corresponding position in the reconstituted outer code word, and where the inner code word is invalid, secondly decoding the reconstituted outer code word where the position is treated as an erasure position.
In another aspect of the present invention the firstly coding step includes coding using Reed-Solomon coding and the secondly decoding step includes decoding using Reed-Solomon decoding.
In another aspect of the present invention the secondly coding step includes coding using Trellis Coded Modulation coding and the firstly decoding step includes decoding using Trellis Coded Modulation decoding.
In another aspect of the present invention the secondly coding step includes coding using Cyclic Redundancy Check coding and the firstly decoding step includes decoding using Cyclic Redundancy Check decoding.
In another aspect of the present invention in a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, a forward error correction system is provided including a decoder operative to receive the code words, detect errors in any of the code words, correct any of the errors and erasures in the code words, and communicate the positions of any of the errors, and a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions to the decoder.
In another aspect of the present invention the system further includes a coder operative to encode the data stream.
In another aspect of the present invention the system further includes at least one transmitting modem for receiving the code words ultimately from the coder and transmitting the code words, and at least one receiving modem for receiving the code words from the at least one transmitting modem and for providing the code words ultimately to the decoder.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the at least one transmitting modem includes a plurality of transmitting modems and the system further includes a demultiplexer intermediate the coder and the transmitting modems for demultiplexing the code words, thereby causing each of the transmitting modems to transit a different portion of each of the code words.
In another aspect of the present invention the at least one receiving modem includes a plurality of receiving modems for receiving the different portions of each of the code words and the system further includes a multiplexer intermediate the receiving modems and the decoder for multiplexing the portions, thereby reconstructing the code words.
In another aspect of the present invention the controller is operative to predict after determining the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the system further includes an interleaver intermediate the coder and the at least one transmitting modem for interleaving the code words, and a deinterleaver intermediate the at least one receiving modem and the decoder for deinterleaving the interleaved code words.
In another aspect of the present invention the controller is operative to send a configuration signal to the decoder configuring the decoder for decoding either of the primary and the secondary code words.
In another aspect of the present invention in a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, a forward error correction system is provided including a primary decoder operative to receive the primary code words, detect any errors in any of the primary code words, correct any of the errors, and communicate the positions of any of the errors, a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions, and a secondary decoder operative to receive the report of erasure positions and correct any of the erasures in the secondary code words.
In another aspect of the present invention the system further includes a coder operative to encode the data stream.
In another aspect of the present invention the system further includes at least one transmitting modem for receiving the code words ultimately from the coder and transmitting the code words, and at least one receiving modem for receiving the code words from the at least one transmitting modem and for providing the code words ultimately to either of the decoders.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the at least one transmitting modem includes a plurality of transmitting modems and the system further includes a demultiplexer intermediate the coder and the transmitting modems for demultiplexing the code words, thereby causing each of the transmitting modems to transmit a different portion of each of the code words.
In another aspect of the present invention the at least one receiving modem includes a plurality of receiving modems for receiving the different portions of each of the code words and the system further includes a multiplexer intermediate the receiving modems and the decoders for multiplexing the portions, thereby reconstructing the code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the system further includes an interleaver intermediate the coder and the at least one transmitting modem for interleaving the code words, and a deinterleaver intermediate the at least one receiving modem and the decoders for deinterleaving the interleaved code words.
In another aspect of the present invention in a communications system including a data stream encoded into at least one code word at a first code rate, the code word transmitted in a plurality of portions, a forward error correction system is provided including a plurality of receiving modems for receiving the plurality of portions, where any of the modems is operative to determine its function status and transmit a signal indicating the status, a multiplexer for multiplexing the plurality of portions, thereby reconstructing the code word, a decoder operative to detect any errors in the code word, correct any of the errors, and correct erasures, and a controller operative to receive the signal and, where the signal indicates that any of the modems is functioning improperly, report erasure positions corresponding to the portion transmitted by the improperly functioning modem to the decoder, where the decoder is operative to receive the report of erasure positions and correct any of the erasures in any of the code words.
In another aspect of the present invention the system further includes a coder operative to encode the data stream.
In another aspect of the present invention the controller is operative to instruct either of the encoder and the decoder to encode at a second code rate having a sufficient redundancy to accommodate the number of the errors and erasures.
In another aspect of the present invention the system further includes at least one transmitting modem for receiving the code words ultimately from the coder and transmitting the code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the at least one transmitting modem includes a plurality of transmitting modems and the system further includes a demultiplexer intermediate the coder and the transmitting modems for demultiplexing the code words, thereby causing each of the transmitting modems to transmit a different portion of each of the code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the system further includes an interleaver intermediate the coder and the at least one transmitting modem for interleaving the code words, and a deinterleaver intermediate the at least one receiving modem and the decoder for deinterleaving the interleaved code words.
In another aspect of the present invention in a communications system including a data stream encoded into at least one outer code word, where the at least one outer code word is further encoded into at least one inner code word using either of an error correcting code and an error checking code, a forward error correction system is provided including an inner decoder operative to receive the inner code word, determine the validity of the inner code word, communicate the validity of the inner code word, and decode the inner code word, thereby reconstituting the outer code word, a controller operative to receive from the inner coder the communication of validity of the inner code word, map the inner code word to its corresponding position in the reconstituted outer code word, and, where the inner code word is invalid, and report the position as an erasure position, and an outer decoder operative to receive the reconstituted outer code word from the inner decoder and the erasure positions from the inner decoder, detect errors in the reconstituted outer code word, and correct any of the errors and erasures in the reconstituted outer code word.
In another aspect of the present invention the system further includes an outer coder operative to encode the data stream into the at least one outer code word, an inner coder operative to encode the outer code word into the at least one inner code word, and a communications channel for transmitting the inner code word to the inner decoder.
In another aspect of the present invention in a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each seconday code word is encoded at a second code rate that is greater than the first code rate, a forward error correction method is provided including detecting any errors in any of the transmitted code words, predicting from any of the errors in the primary code word at least one error in the secondary code word, and correcting any of the predicted errors as erasure positions in any of the secondary code words.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the method further includes coding the data stream at a coder, demultiplexing the code words into a plurality of code word portions, transmitting the portions via a plurality of transmitting modems, receiving the portions via a plurality of receiving modems, and multiplexing the plurality of portions, thereby reconstructing the code word.
In another aspect of the present invention the method further includes interleaving the code words prior to the transmitting step, and deinterleaving the interleaved code words subsequent to the transmitting step.
In another aspect of the present invention the method further includes configuring the decoder for decoding either of the primary and the secondary code words.
In another aspect of the present invention in a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, a forward error correction method is provided including detecting any errors in any of the primary code words at a primary decoder, predicting from any of the errors in the primary code word at least one error in the secondary code word, and correcting any of the predicted errors as erasures in the secondary code words at a secondary encoder.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the method further includes coding the data stream at a coder, demultiplexing the code words into a plurality of code word portions, transmitting the portions via a plurality of transmitting modems, receiving the portions via a plurality of receiving modems, and multiplexing the plurality of portions, thereby reconstructing the code word.
In another aspect of the present invention the method further includes interleaving the code words prior to the transmitting step, and deinterleaving the interleaved code words subsequent to the transmitting step.
In another aspect of the present invention in a communications system including a data stream encoded into at least one code word at a first code rate, the code word transmitted in a plurality of portions, a forward error correction method is provided including receiving a different one of the plurality of portions via a plurality of receiving modems, multiplexing the plurality of portions, thereby reconstructing the code words, determining the function status of any of the modems, and where any of the modems is functioning improperly, correcting as erasures the portion transmitted by the improperly functioning modem.
In another aspect of the present invention in a communications method including a data stream encoded into at least one outer code word, where the at least one outer code word is further encoded into at least one inner code word using either of an error correcting code and an error checking code, a forward error correction method is provided including determining the validity of the transmitted inner code word, firstly decoding the inner code word, thereby reconstituting the outer code word, mapping the inner code word to its corresponding position in the reconstituted outer code word, and where the inner code word is invalid, secondly decoding the reconstituted outer code word where the position is treated as an erasure position.
In another aspect of the present invention the method further includes firstly coding using Reed-Solomon coding and where the secondly decoding step includes decoding using Reed-Solomon decoding.
In another aspect of the present invention the secondly coding step includes coding using Trellis Coded Modulation coding and the firstly decoding step includes decoding using Trellis Coded Modulation decoding.
In another aspect of the present invention the secondly coding step includes coding using Cyclic Redundancy Check coding and the firstly decoding step includes decoding using Cyclic Redundancy Check decoding.
It is appreciated throughout the specification and claims that references to code words having a data portion and a redundancy portion may be understood as either referring to distinct data and redundancy portions common to systematic coding techniques, or indistinct, co-mingled portions common to non-systematic and convolutional coding techniques. It is further appreciated throughout the specification and claims that references to elements of the invention “reporting” information to other elements of the invention refers to the providing of information through notifications, indications, signals, or any other suitable communication technique known in the art.
The disclosures of all patents, patent applications, and other publications mentioned in this specification and of the patents, patent applications, and other publications cited therein are hereby incorporated by reference.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be understood and appreciated more fully from the following detailed description taken in conjunction with the appended drawings in which FIGS. 1-5, taken separately, are simplified block-flow diagrams of a forward error correction system, each constructed and operative in accordance with a different preferred embodiment of the present invention.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
Reference is now made to FIG. 1 which is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention. In the system of FIG. 1 a data stream is encoded at a coder 10, such as a Reed-Solomon coder, into one or more code words 12, each typically having a data portion k and a redundancy portion r. The code words 12 are then demultiplexed at a demultiplexer 14 for parallel transmission via a plurality of modems in a modem pool 16, where each modem preferably transmits a different portion of each code word 12. The transmissions are then received by a plurality of modems in a modem pool 18, and multiplexed at a multiplexer 20 into reconstituted code words 22 that correspond to code words 12. Code words 22 are then decoded at a decoder 24.
Redundancy portion r preferably provides sufficient redundancy to allow correction of a predetermined number of errors. Preferably, redundancy portion r comprises sufficient redundancy to allow the system to recover from a failure of a predetermined number of modems in either of modem pools 16 and 18. For example, if modem pool 16 numbers ten modems, all having the same transmission rate, and the design goal is to configure the system to recover from a failure of one of the modems in modem pool 16, then the redundancy portion r in each code word should comprise at least 20% of the code word length, thus providing a code rate of 0.8.
Reference is now made to FIG. 2 which is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention. In the system of FIG. 2 a data stream is encoded at a coder 30, such as a Reed-Solomon coder, into one or more code words 32, each typically having a data portion k and a redundancy portion r. The code words 32 are then demultiplexed at a demultiplexer 34 for parallel transmission via a plurality of modems in a modem pool 36, where each modem preferably transmits a different portion of each code word 32. The transmissions are then received by a plurality of modems in a modem pool 38, and multiplexed at a multiplexer 40 into reconstituted code words 42 that correspond to code words 32. Code words 42 are then decoded at a decoder 44.
Each modem in modem pool 38 is preferably able to determine whether or not it is functioning properly using conventional techniques, such as through the detection of a received power signal or synchronization word, and preferably sends a status signal to a controller 46 indicating such. Upon receiving notification of a malfunctioning modem, controller 46 informs decoder 44 that those portions of the code words transmitted by the malfunctioning modem are to be treated as erasures and sends a signal indicating their positions to decoder 44. Controller 46 may optionally send a configuration signal to both encoder 30 and decoder 44 to change the coding parameters to accommodate the number of errors and erasures encountered by increasing or decreasing the amount of redundancy in the code words.
Referring again to the example given above of a modem pool comprising ten modems with the design goal of maintaining operation where one modem fails, if the communication channel can tolerate bursts of errors for a relatively short period of time, the code rate of the system of FIG. 2 may be increased from 0.8 to 0.9, and the system will recover from a failure of one modem by marking the positions of those symbols which were to be transmitted via the malfunctioning modem as erasures.
Reference is now made to FIG. 3 which is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention. In the system of FIG. 3 a data stream is encoded at a coder 50, typically a Reed-Solomon coder, into one or more primary code words 52 and one or more secondary code words 54. Although code words 52 and 54 are shown as having the same code word length and are represented using systematic encoding, where the data and redundancy portions are not intermingled, it is appreciated that code words 52 and 54 may use either systematic or non-systematic encoding and that their lengths may be different. Primary code word 52 typically comprises a data portion k and a redundancy portion r. Redundancy portion r preferably comprises sufficient redundancy to allow correction of a predetermined number of errors. Secondary code words 54 preferably comprise a redundancy portion r−Δ and a data portion Δ in addition to data portion k. Redundancy portion r−Δ preferably comprises sufficient redundancy to allow correction of a predetermined number of erasures, and may therefore be up to half as large as redundancy portion r of primary code word 52. The size of data portion Δ preferably corresponds to the reduction in size of redundancy portion r−Δ as compared to redundancy portion r of primary code words 52.
The primary and secondary code words 52 and 54 are then preferably interleaved in accordance with conventional techniques at an interleaver 56 and demultiplexed at a demultiplexer 58 for parallel transmission via one or more modems in a modem pool 60, where each modem preferably transmits a different portion of each code word.
At the receiving end the demultiplexed code word portions are received by modems in a modem pool 62, multiplexed back into interleaved code words at a multiplexer 64, and deinterleaved at a deinterleaver 66 into primary and secondary code words 68 and 70 corresponding to primary and secondary code words 52 and 54. Primary code word 68 is then preferably fed into a primary decoder 72 which detects and corrects any errors in primary code word 68. The position of any errors found in primary code word 68 are provided to a controller 76 which is preferably configured to predict which positions in the secondary code words are vulnerable to errors and mark these positions as erasures. For example, controller 76 may be configured to determine whether the number of errors detected in a code word portion received via a particular modem exceeds a predetermined error threshold. If the threshold is exceeded, then the modem and/or its connection is deemed to be unreliable, and each position in the code word portions subsequently received therefrom are treated as erasures. The erasure positions are then communicated from controller 76 to a secondary decoder 74. Secondary code words 70 are then fed into secondary decoder 74 which decodes the secondary code words 70 and corrects for the erasures indicated by controller 76. The decoded output from primary and secondary decoders 72 and 74 are then preferably fed to a multiplexer 78, thus reconstructing the original data stream. Processing preferably continues in a cyclical manner, with primary code words followed by secondary code words followed by primary code words, etc.
Referring again to the example given above of a modem pool comprising ten modems, each having the same transmission rate, a communication system employing the coding system of FIG. 3 with one primary code word having a code rate of 0.8 (20% redundancy) followed by four secondary code words having a code rate of 0.9 (10% redundancy) will provide good protection against a single modem failure with an overall code rate of 0.88 (12% redundancy).
Reference is now made to FIG. 4 which is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention. The system of FIG. 4 is substantially similar to the system of FIG. 3 with the notable exception that primary decoder 72 is capable of decoding both primary and secondary code words 68 and 70 without the need for secondary decoder 74. In the present embodiment controller 76 indicates the erasure positions to primary decoder 72, and optionally may send a configuration signal to primary decoder 72 to change its decoding parameters accordingly in order to selectably decode both primary and secondary code words 68 and 70.
Reference is now made to FIG. 5 which is a simplified block-flow diagram of a forward error correction system, constructed and operative in accordance with a preferred embodiment of the present invention. In the system of FIG. 5 a data stream is encoded at a outer coder 80, such as a Reed-Solomon coder, into one or more outer code words 82, each typically having a data portion k and a redundancy portion r. Typically, outer code words 82 are then interleaved at an interleaver 84 and coded at a inner coder 86 into one or more inner code words 88. Inner coder 86 may employ an error correcting code, such as Trellis Coded Modulation (TCM), or an error checking code, such as Cyclic Redundancy Checking (CRC) Inner code words 88 are then transmitted via a communications channel 90, which may include one or more modems or any other transmission medium.
At the receiving end of communications channel 90, the transmission is decoded at an inner decoder 92, whose decoding method corresponds to the coding method used by inner coder 86, and deinterleaved at a deinterleaver 94 to form reconstituted outer code words 96 that correspond to outer code words 82. Inner decoder 92 preferably checks whether inner code words 88 are valid code words in accordance with the employed error correcting code. Inner decoder 92 notifies a controller 98 of each inner code word 88 that is found to be invalid. Controller 98 in turn maps the positions of each invalid code word 88 to its corresponding position in outer code word 96 and marks the position as an erasure. Controller 98 then communicates the positions of the erasures to an outer decoder 100, whose decoding method corresponds to the coding method used by outer coder 80, which then decodes the outer code words 96 into the original data stream.
In an exemplary implementation of the system of FIG. 5 outer coder 80 employs a RS code, where each symbol of the RS code is a byte, 8 bits in length. Thus, each code word of the RS code will contain k+r bytes or 8(k+r) bits. Inner coder 86 adds a parity check bit to each byte of the RS code words, thus forming inner code words 88, 9 bits in length, where k2=8 bits and r2=1 bit. In this example, each k bytes of data of each outer code word 82 would be coded into 9(k+r) bits. At the receiver, each 9-bit inner code word 88 is checked for parity. If parity is violated, the corresponding byte of the reconstituted outer code word 96 comprising the 8 data bits of the inner code word 88 is marked as an erasure.
The system of FIG. 5 demonstrates that whenever a concatenated coding scheme is used, such as Reed-Solomon/Vitterbi in ADSL systems, the inner decoder may be used to mark erasures and thereby improve the performance of the outer decoder.
Although the present invention has been described with respect to RS encoding, it is appreciated that the present invention may easily be implemented for use with other codes, including block codes and convolutional codes. The present invention is also applicable to codes employing soft decisions where erasures are designated by assigning 1 to the ratio prb(1)/prb(0) (or 0 to log(prb(1)/prb(0)) for a bit to be erased, where prb(0)denotes the a priori probability that bit b is 0, and prb(1) denotes the a priori probability that bit b is 1. It is further appreciated that any conventional error location mechanism may be used.
It is appreciated that one or more of the steps of any of the methods described herein may be omitted or carried out in a different order than that shown, without departing from the true spirit and scope of the invention.
While the methods and apparatus disclosed herein may or may not have been described with reference to specific hardware or software, the methods and apparatus have been described in a manner sufficient to enable persons of ordinary skill in the art to readily adapt commercially available hardware and software as may be needed to reduce any of the embodiments of the present invention to practice without undue experimentation and using conventional techniques.
While the present invention has been described with reference to a few specific embodiments, the description is intended to be illustrative of the invention as a whole and is not to be construed as limiting the invention to the embodiments shown. It is appreciated that various modifications may occur to those skilled in the art that, while not specifically shown herein, are nevertheless within the true spirit and scope of the invention.

Claims (37)

What is claimed is:
1. A forward error correction system comprising:
a coder operative to encode a data stream into at least one primary code word and at least one secondary code word, wherein:
each primary code word is encoded at a first code rate, and
each secondary code word is encoded at a second code rate that is greater than said first code rate,
a plurality of transmitting modems for transmitting said code words; and
a demultiplexer intermediate to said coder and said transmitting modems for demultiplexing said code words, thereby causing each of said transmitting modems to transmit a different portion of each of said code words.
2. A system according to claim 1 and further comprising:
a plurality of receiving modems for receiving said different portions of each of said code words;
a multiplexer for multiplexing said portions, thereby reconstructing said code words;
a decoder operative to detect errors in any of said code words, correct any of said errors and erasures in said code words, and communicate the positions of any of said errors; and
a controller operative to receive said communication of said error positions, predict from any of said errors in said primary code word at least one error in said secondary code word, and report any of said predicted errors as erasure positions to said decoder, wherein said controller is operative to predict after determining that the number of errors detected in said primary code word exceeds a predetermined error threshold.
3. A system according to claim 2 wherein said controller is operative to predict after determining that the number of errors detected in any of said portions exceeds said predetermined error threshold, and wherein any of said predicted errors corresponds to said portion exceeding said predetermined error threshold.
4. A system according to claim 2 wherein said controller is operative to send a configuration signal to said decoder configuring said decoder for decoding either of said primary and said secondary code words.
5. A forward error correction system comprising:
a coder operative to encode a data stream into at least one primary code word and at least one secondary code word, wherein:
each primary code word is encoded at a first code rate, and
each secondary code word is encoded at a second code rate that is greater than said first code rate,
a demultiplexer for demultiplexing each of said code words into a plurality of portions;
a plurality of transmitting modems, each transmitting modem for transmitting at least one of said plurality of portions;
a plurality of receiving modems for receiving said plurality of portions;
a multiplexer for multiplexing said plurality of portions, thereby reconstructing said code words;
a primary decoder operative to detect any errors in any of said primary code words, correct any of said errors, and communicate the positions of any of said errors;
a controller operative to receive said communication of said error positions, predict from any of said errors in said primary code word at least one error in said secondary code word, and report any of said predicted errors as erasure positions;
a secondary decoder operative to receive said report of erasure positions and correct any of said erasures in said secondary code words.
6. A system according to claim 5 wherein said controller is operative to predict after determining that the number of errors detected in said primary code word exceeds a predetermined error threshold.
7. A system according to claim 5 wherein said controller is operative to predict after determining that the number of errors detected in any of said portions exceeds said predetermined error threshold, and wherein any of said predicted errors corresponds to said portion exceeding said predetermined error threshold.
8. A forward error correction system comprising:
a coder operative to encode a data stream into at least one code word at a first code rate;
a demultiplexer for demultiplexing said code word into a plurality of portions;
a plurality of transmitting modems, each transmitting modem for transmitting at least one of said plurality of portions;
a plurality of receiving modems for receiving said plurality of portions, wherein any of said modems is operative to determine its function status and transmit a signal indicating said status;
a multiplexer for multiplexing said plurality of portions, thereby reconstructing said code word;
a decoder operative to detect any errors in said code word, correct any of said errors, and correct erasures; and
a controller operative to receive said signal and, where said signal indicates that any of said modems is functioning improperly, report erasure positions corresponding to said portion transmitted by said improperly functioning modem to said decoder, wherein said decoder is operative to receive said report of erasure positions and correct any of said erasures in any of said code words.
9. A system according to claim 8 wherein said controller is operative to instruct said encoder to encode and said decoder to decode at a second code rate having a redundancy to accommodate the number of said errors and erasures.
10. A forward error correction method comprising:
encoding a data stream into at least one primary code word and at least one secondary code word, wherein:
each primary code word is encoded at a first code rate, and
each secondary code word is encoded at a second code rate that is greater than said first code rate,
demultiplexing said code words into a plurality of code word portions;
transmitting said portions via a plurality of transmitting modems;
receiving said portions via a plurality of receiving modems;
multiplexing said plurality of portions, thereby reconstructing said code word;
detecting any errors in any of said transmitted code words;
predicting from any of said errors in said primary code word at least one error in said secondary code word; and
correcting any of said predicted errors as erasure positions in any of said secondary code words.
11. A method according to claim 10 wherein said predicting step comprises predicting after determining that the number of errors detected in said primary code word exceeds a predetermined error threshold.
12. A method according to claim 10 and further comprising configuring said decoder for decoding either of said primary and said secondary code words.
13. A forward error correction method comprising:
encoding a data stream into at least one primary code word and at least one secondary code word, wherein:
each primary code word is encoded at a first code rate, and
each secondary code word is encoded at a second code rate that is greater than said first code rate,
demultiplexing each of said code words into a plurality of portions;
transmitting said plurality of portions via a plurality of transmitting modems;
receiving said plurality of portions via a plurality of receiving modems;
multiplexing said plurality of portions, thereby reconstructing said code words;
detecting any errors in any of said primary code words at a primary decoder;
predicting from any of said errors in said primary code word at least one error in said secondary code word; and
correcting any of said predicted errors as erasures in said secondary code words at a secondary encoder.
14. A method according to claim 13 wherein said predicting step comprises predicting after determining that the number of errors detected in said primary code word exceeds a predetermined error threshold.
15. A method according to claim 13 wherein said predicting step comprises predicting said at least one error in said secondary code word after determining that the number of errors detected in any of said portions exceeds a predetermined error threshold, and wherein any of said predicted errors corresponds to said portion exceeding said predetermined error threshold.
16. A forward error correction method comprising:
encoding a data stream into at least one code word at a first code rate;
demultiplexing each of said code words into a plurality of portions;
transmitting said plurality of portions via a plurality of transmitting modems;
receiving said plurality of portions via a plurality of receiving modems;
multiplexing said plurality of portions, thereby reconstructing said code words;
determining the function status of any of said modems; and
where any of said modems is functioning improperly, correcting as erasures said portion transmitted by said improperly functioning modem.
17. In a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, wherein each primary code word is encoded at a first code rate and each secondary code word is encoded at a second code rate that is greater than said first code rate, a forward error correction system comprising:
a plurality of receiving modems for receiving different portions of each of said code words;
a multiplexer for multiplexing said portions, thereby reconstructing said code words;
a decoder operative to receive said code words, detect errors in any of said code words, correct any of said errors and erasures in said code words, and communicate the positions of any of said errors; and
a controller operative to receive said communication of said error positions, predict from any of said errors in said primary code word at least one error in said secondary code word, and report any of said predicted errors as erasure positions to said decoder.
18. A system according to claim 17 and further comprising a coder operative to encode said data stream.
19. A system according to claim 18 and further comprising a plurality of transmitting modems and a demultiplexer intermediate to said coder and said transmitting modems for demultiplexing said code words prior to transmission, thereby causing each of said transmitting modems to transmit a different portion of each of said code words.
20. A system according to claim 19 wherein said controller is operative to predict after determining that the number of errors detected in any of said portions exceeds said predetermined error threshold, and wherein any of said predicted errors corresponds to said portion exceeding said predetermined error threshold.
21. A system according to claim 17 wherein said controller is operative to predict said at least one error in said secondary code word after determining that the number of errors detected in said primary code word exceeds a predetermined error threshold.
22. A system according to claim 17 wherein said controller is operative to send a configuration signal to said decoder configuring said decoder for decoding either of said primary and said secondary code words.
23. In a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, wherein each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than said first code rate, a forward error correction system comprising:
a plurality of receiving modems for receiving different portions of each of said code words;
a multiplexer for multiplexing said portions, thereby reconstructing said code words;
a primary decoder operative to receive said primary code words, detect any errors in any of said primary code words, correct any of said errors, and communicate the positions of any of said errors;
a controller operative to receive said communication of said error positions, predict from any of said errors in said primary code word at least one error in said secondary code word, and report any of said predicted errors as erasure positions; and
a secondary decoder operative to receive said report of erasure positions and correct any of said erasures in said secondary code words.
24. A system according to claim 23 and further comprising a coder operative to encode said data stream.
25. A system according to claim 24 and further comprising a plurality of transmitting modems and a demultiplexer intermediate said coder and said transmitting modems for demultiplexing said code words prior to transmission, thereby causing each of said transmitting modems to transmit a different portion of each of said code words.
26. A system according to claim 25 wherein said controller is operative to predict after determining that the number of errors detected in any of said portions exceeds said predetermined error threshold, and wherein any of said predicted errors corresponds to said portion exceeding said predetermined error threshold.
27. A system according to claim 23 wherein said controller is operative to predict after determining that the number of errors detected in said primary code word exceeds a predetermined error threshold.
28. In a communications system including a data stream encoded into at least one code word at a first code rate, said code word transmitted in a plurality of portions, a forward error correction system comprising:
a plurality of receiving modems for receiving said plurality of portions, wherein any of said modems is operative to determine its function status and transmit a signal indicating said status;
a multiplexer for multiplexing said plurality of portions, thereby reconstructing said code word;
a decoder operative to detect any errors in said code word, correct any of said errors, and correct erasures; and
a controller operative to receive said signal and, where said signal indicates that any of said modems is functioning improperly, report erasure positions corresponding to said portion transmitted by said improperly functioning modem to said decoder, wherein said decoder is operative to receive said report of erasure positions and correct any of said erasures in any of said code words.
29. A system according to claim 28 and further comprising a coder operative to encode said data stream.
30. A system according to claim 29 wherein said controller is operative to instruct said encoder to encode and said decoder to decode at a second code rate having a redundancy to accommodate the number of said errors and erasures.
31. A system according to claim 29 and further comprising a plurality of transmitting modems and a demultiplexer intermediate said coder and said transmitting modems for demultiplexing said code words prior to transmission, thereby causing each of said transmitting modems to transmit a different portion of each of said code words.
32. In a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, wherein each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than said first code rate, a forward error correction method comprising:
coding said data stream at a coder;
demultiplexing said code words into a plurality of code word portions;
transmitting said portions via a plurality of transmitting modems;
receiving said portions via a plurality of receiving modems;
multiplexing said plurality of portions, thereby reconstructing said code word;
detecting any errors in any of said transmitted code words;
predicting from any of said errors in said primary code word at least one error in said secondary code word; and
correcting any of said predicted errors as erasure positions in any of said secondary code words.
33. A method according to claim 32 wherein said predicting step comprises predicting after determining that the number of errors detected in said primary code word exceeds a predetermined error threshold.
34. A method according to claim 32 and further comprising configuring said decoder for decoding either of said primary and said secondary code words.
35. In a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, wherein each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than said first code rate, a forward error correction method comprising:
coding said data stream at a coder;
demultiplexing said code words into a plurality of code word portions;
transmitting said portions via a plurality of transmitting modems;
receiving said portions via a plurality of receiving modems;
multiplexing said plurality of portions, thereby reconstructing said code word;
detecting any errors in any of said primary code words at a primary decoder;
predicting from any of said errors in said primary code word at least one error in said secondary code word; and
correcting any of said predicted errors as erasures in said secondary code words at a secondary encoder.
36. A method according to claim 35 wherein said predicting step comprises predicting after determining that the number of errors detected in said primary code word exceeds a predetermined error threshold.
37. In a communications system including a data stream encoded into at least one code word at a first code rate, said code word transmitted in a plurality of portions, a forward error correction method comprising:
receiving said plurality of portions via a plurality of receiving modems;
multiplexing said plurality of portions, thereby reconstructing said code words;
determining the function status of any of said modems; and
where any of said modems is functioning improperly, correcting as erasures said portion transmitted by said improperly functioning modem.
US09/677,671 2000-10-04 2000-10-04 Predictive forward error correction redundancy Expired - Lifetime US6697985B1 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
US09/677,671 US6697985B1 (en) 2000-10-04 2000-10-04 Predictive forward error correction redundancy

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US09/677,671 US6697985B1 (en) 2000-10-04 2000-10-04 Predictive forward error correction redundancy

Publications (1)

Publication Number Publication Date
US6697985B1 true US6697985B1 (en) 2004-02-24

Family

ID=31496233

Family Applications (1)

Application Number Title Priority Date Filing Date
US09/677,671 Expired - Lifetime US6697985B1 (en) 2000-10-04 2000-10-04 Predictive forward error correction redundancy

Country Status (1)

Country Link
US (1) US6697985B1 (en)

Cited By (21)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020001353A1 (en) * 2000-04-18 2002-01-03 Citta Richard W. Enhanced slice prediction feedback
US20050268205A1 (en) * 2004-05-31 2005-12-01 Samsung Electronics Co., Ltd. Method and apparatus for decoding inner and outer codes in a mobile communication system
US20060005099A1 (en) * 2004-06-01 2006-01-05 Nery Strasman Method and system for program based redundancy
US7065696B1 (en) * 2003-04-11 2006-06-20 Broadlogic Network Technologies Inc. Method and system for providing high-speed forward error correction for multi-stream data
US20070116266A1 (en) * 2005-11-22 2007-05-24 Greco Paul M Method, system, and apparatus for dynamically validating a data encryption operation
US20070127595A1 (en) * 2001-04-23 2007-06-07 Cellular Elements Llc Reduced complexity coding system using iterative decoding
US20070245208A1 (en) * 2006-04-13 2007-10-18 Nee Chi-Ping Erasures assisted block code decoder and related method
US20070260850A1 (en) * 2006-03-17 2007-11-08 Fujitsu Limited Data transferring method, and communication system and program applied with the method
US20070288313A1 (en) * 2006-06-09 2007-12-13 Mark Brodson E-Coupon System and Method
US20080062909A1 (en) * 2006-09-12 2008-03-13 Samsung Electronics Co., Ltd. Apparatus and method for supporting distributed spatial multiplexing and distributed spatial diversity in multi-hop relay system
US20080065963A1 (en) * 2006-08-22 2008-03-13 Korea Advanced Institute Of Science & Technology Forward error correction decoder and method thereof
US20090018908A1 (en) * 2007-07-12 2009-01-15 Oksana Dersovitz Electronic coupon device
US20090106115A1 (en) * 2004-12-01 2009-04-23 James Vicki L E-Coupon Settlement and Clearing Process
US7698619B1 (en) * 2005-08-25 2010-04-13 Marvell International Ltd. Erasure forecasting and error-correction strategies
US20100146372A1 (en) * 2006-12-19 2010-06-10 Martin Tomlinson Decoding of serial concatenated codes using erasure patterns
FR2954873A1 (en) * 2009-12-24 2011-07-01 Canon Kk Coded packets decoding method for e.g. wireless communication network, involves marking symbol of packet corresponding to deleted position of list, and decoding packet according to marked deleted symbol
US20130128987A1 (en) * 2011-11-22 2013-05-23 Canon Kabushiki Kaisha Communication of data blocks over a communication system
US20130246884A1 (en) * 2012-03-16 2013-09-19 Hughes Network System, Llc Method and apparatus for wireless data transmission subject to periodic signal blockages
US20140101521A1 (en) * 2012-10-09 2014-04-10 Samsung Electronics Co. Ltd. Method and apparatus for decoding received packets in broadcasting and communication system
US9397704B2 (en) 2012-03-16 2016-07-19 Hughes Networks Systems, Llc Method and apparatus for wireless data transmission subject to periodic signal blockages
WO2023179634A1 (en) * 2022-03-22 2023-09-28 华为技术有限公司 Data writing method and processing system

Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4649541A (en) * 1984-11-21 1987-03-10 The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration Reed-Solomon decoder
US5107503A (en) * 1987-08-24 1992-04-21 Digital Equipment Corporation High bandwidth reed-solomon encoding, decoding and error correcting circuit
US5373511A (en) * 1992-05-04 1994-12-13 Motorola, Inc. Method for decoding a reed solomon encoded signal with inner code and apparatus for doing same
US5457704A (en) * 1993-05-21 1995-10-10 At&T Ipm Corp. Post processing method and apparatus for symbol reliability generation
US5719884A (en) * 1995-07-27 1998-02-17 Hewlett-Packard Company Error correction method and apparatus based on two-dimensional code array with reduced redundancy
US6023783A (en) * 1996-05-15 2000-02-08 California Institute Of Technology Hybrid concatenated codes and iterative decoding
US6192503B1 (en) * 1997-08-14 2001-02-20 Ericsson Inc. Communications system and methods employing selective recursive decording
US6304995B1 (en) * 1999-01-26 2001-10-16 Trw Inc. Pipelined architecture to decode parallel and serial concatenated codes
US6415413B1 (en) * 1998-06-18 2002-07-02 Globespanvirata, Inc. Configurable Reed-Solomon controller and method

Patent Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4649541A (en) * 1984-11-21 1987-03-10 The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration Reed-Solomon decoder
US5107503A (en) * 1987-08-24 1992-04-21 Digital Equipment Corporation High bandwidth reed-solomon encoding, decoding and error correcting circuit
US5373511A (en) * 1992-05-04 1994-12-13 Motorola, Inc. Method for decoding a reed solomon encoded signal with inner code and apparatus for doing same
US5457704A (en) * 1993-05-21 1995-10-10 At&T Ipm Corp. Post processing method and apparatus for symbol reliability generation
US5719884A (en) * 1995-07-27 1998-02-17 Hewlett-Packard Company Error correction method and apparatus based on two-dimensional code array with reduced redundancy
US6023783A (en) * 1996-05-15 2000-02-08 California Institute Of Technology Hybrid concatenated codes and iterative decoding
US6192503B1 (en) * 1997-08-14 2001-02-20 Ericsson Inc. Communications system and methods employing selective recursive decording
US6415413B1 (en) * 1998-06-18 2002-07-02 Globespanvirata, Inc. Configurable Reed-Solomon controller and method
US6304995B1 (en) * 1999-01-26 2001-10-16 Trw Inc. Pipelined architecture to decode parallel and serial concatenated codes

Cited By (38)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020001353A1 (en) * 2000-04-18 2002-01-03 Citta Richard W. Enhanced slice prediction feedback
US6963618B2 (en) * 2000-04-18 2005-11-08 Zenith Electronics Corporation Enhanced slice prediction feedback
US7693235B2 (en) * 2001-04-23 2010-04-06 California Institute Of Technology Reduced complexity coding system using iterative decoding
US20070127595A1 (en) * 2001-04-23 2007-06-07 Cellular Elements Llc Reduced complexity coding system using iterative decoding
US7065696B1 (en) * 2003-04-11 2006-06-20 Broadlogic Network Technologies Inc. Method and system for providing high-speed forward error correction for multi-stream data
US20050268205A1 (en) * 2004-05-31 2005-12-01 Samsung Electronics Co., Ltd. Method and apparatus for decoding inner and outer codes in a mobile communication system
US7539928B2 (en) * 2004-05-31 2009-05-26 Samsung Electronics Co., Ltd. Method and apparatus for decoding inner and outer codes in a mobile communication system
US20060005099A1 (en) * 2004-06-01 2006-01-05 Nery Strasman Method and system for program based redundancy
US7676720B2 (en) * 2004-06-01 2010-03-09 BigBand Networks, Inc Method and system for program based redundancy
US11861611B2 (en) 2004-12-01 2024-01-02 Fidelity Information Services, Llc E-Coupon settlement and clearing process
US11507951B2 (en) 2004-12-01 2022-11-22 Fidelity Information Services, Llc E-coupon settlement and clearing process
US10248951B2 (en) 2004-12-01 2019-04-02 Metavante Corporation E-coupon settlement and clearing process
US20090106115A1 (en) * 2004-12-01 2009-04-23 James Vicki L E-Coupon Settlement and Clearing Process
US8046659B1 (en) 2005-08-25 2011-10-25 Marvell International Ltd. Erasure forecasting and error-correction strategies
US7698619B1 (en) * 2005-08-25 2010-04-13 Marvell International Ltd. Erasure forecasting and error-correction strategies
US20070116266A1 (en) * 2005-11-22 2007-05-24 Greco Paul M Method, system, and apparatus for dynamically validating a data encryption operation
US8135958B2 (en) 2005-11-22 2012-03-13 International Business Machines Corporation Method, system, and apparatus for dynamically validating a data encryption operation
US20070260850A1 (en) * 2006-03-17 2007-11-08 Fujitsu Limited Data transferring method, and communication system and program applied with the method
US8171355B2 (en) * 2006-03-17 2012-05-01 Fujitsu Limited Data transferring method, and communication system and program applied with the method
US20070245208A1 (en) * 2006-04-13 2007-10-18 Nee Chi-Ping Erasures assisted block code decoder and related method
US7734984B2 (en) * 2006-04-13 2010-06-08 Trident Microsystems (Far East) Ltd. Erasures assisted block code decoder and related method
US20100229070A1 (en) * 2006-04-13 2010-09-09 Nee Chi-Ping Erasures Assisted Block Code Decoder And Related Method
US8065593B2 (en) 2006-04-13 2011-11-22 Trident Microsystems (Far East) Ltd. Erasures assisted block code decoder and related method
US20070288313A1 (en) * 2006-06-09 2007-12-13 Mark Brodson E-Coupon System and Method
US20080065963A1 (en) * 2006-08-22 2008-03-13 Korea Advanced Institute Of Science & Technology Forward error correction decoder and method thereof
US8010880B2 (en) * 2006-08-22 2011-08-30 Korea Advanced Institute Of Science & Technology Forward error correction decoder and method thereof
US20080062909A1 (en) * 2006-09-12 2008-03-13 Samsung Electronics Co., Ltd. Apparatus and method for supporting distributed spatial multiplexing and distributed spatial diversity in multi-hop relay system
US9203554B2 (en) * 2006-09-12 2015-12-01 Samsung Electronics Co., Ltd. Apparatus and method for supporting distributed spatial multiplexing and distributed spatial diversity in multi-hop relay system
US20100146372A1 (en) * 2006-12-19 2010-06-10 Martin Tomlinson Decoding of serial concatenated codes using erasure patterns
US20090018908A1 (en) * 2007-07-12 2009-01-15 Oksana Dersovitz Electronic coupon device
FR2954873A1 (en) * 2009-12-24 2011-07-01 Canon Kk Coded packets decoding method for e.g. wireless communication network, involves marking symbol of packet corresponding to deleted position of list, and decoding packet according to marked deleted symbol
US20130128987A1 (en) * 2011-11-22 2013-05-23 Canon Kabushiki Kaisha Communication of data blocks over a communication system
US9009559B2 (en) * 2012-03-16 2015-04-14 Hughes Network Systems, Llc Method and apparatus for wireless data transmission subject to periodic signal blockages
US9397704B2 (en) 2012-03-16 2016-07-19 Hughes Networks Systems, Llc Method and apparatus for wireless data transmission subject to periodic signal blockages
US20130246884A1 (en) * 2012-03-16 2013-09-19 Hughes Network System, Llc Method and apparatus for wireless data transmission subject to periodic signal blockages
US9705640B2 (en) * 2012-10-09 2017-07-11 Samsung Electronics Co., Ltd. Method and apparatus for decoding received packets in broadcasting and communication system
US20140101521A1 (en) * 2012-10-09 2014-04-10 Samsung Electronics Co. Ltd. Method and apparatus for decoding received packets in broadcasting and communication system
WO2023179634A1 (en) * 2022-03-22 2023-09-28 华为技术有限公司 Data writing method and processing system

Similar Documents

Publication Publication Date Title
US6697985B1 (en) Predictive forward error correction redundancy
EP0998072B1 (en) Forward error correction for ARQ protocol
JP4719205B2 (en) Turbo coding and decoding with stepwise data transmission and processing
EP0855108B1 (en) A coding system and method providing unequal error protection by puncturing less significant symbols
CA2698533C (en) Multi-layer cyclic redundancy check code in wireless communication system
KR101608788B1 (en) Method and device for channel coding
JP4386587B2 (en) Encoding or decoding method and encoding or decoding apparatus
WO1997014225A9 (en) A coding system and method providing unequal error protection by puncturing less significant symbols
KR20000068230A (en) Information data multiplexing transmission system, multiplexer and demultiplexer used therefor, and error correcting encoder and decoder
KR101061116B1 (en) Uplink Control Information Transmission Method and Decoding Method of Control Information in a Mobile Communication System
US20090077448A1 (en) Forward error correction codec
JP2001007784A (en) Data transmission method, data transmission system, transmitter and receiver
GB2216752A (en) Forward error correction in packet switched communications
KR20050114162A (en) Method and apparatus for decoding inner code and outer code in a mobile communication system using reed-solomon code
US11057148B2 (en) Data encoding and decoding
US7861137B2 (en) System for identifying localized burst errors
EP0981863B1 (en) Method and apparatus for enhanced performance in a system employing convolutional decoding
CN113366872B (en) LPWAN communication protocol design using parallel concatenated convolutional codes
KR100880630B1 (en) Transmission chain in communication system and method for transmitting and detecting physical channel format uging the same
AU754735B2 (en) Error correction with two block codes

Legal Events

Date Code Title Description
AS Assignment

Owner name: ACTELIS NETWORKS INC., CALIFORNIA

Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:ILANI, ISHAI;REEL/FRAME:011188/0242

Effective date: 20000926

STCF Information on status: patent grant

Free format text: PATENTED CASE

FEPP Fee payment procedure

Free format text: PAYOR NUMBER ASSIGNED (ORIGINAL EVENT CODE: ASPN); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY

Free format text: PAYER NUMBER DE-ASSIGNED (ORIGINAL EVENT CODE: RMPN); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY

FPAY Fee payment

Year of fee payment: 4

FEPP Fee payment procedure

Free format text: PAYOR NUMBER ASSIGNED (ORIGINAL EVENT CODE: ASPN); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY

Free format text: PAYER NUMBER DE-ASSIGNED (ORIGINAL EVENT CODE: RMPN); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY

FPAY Fee payment

Year of fee payment: 8

FPAY Fee payment

Year of fee payment: 12

AS Assignment

Owner name: MIGDALOR INVESTMENT FUND IN BUSINESS, LIMITED PARTNERSHIP, ISRAEL

Free format text: SECURITY INTEREST;ASSIGNOR:ACTELIS NETWORKS INC.;REEL/FRAME:054947/0765

Effective date: 20201230