Patent US5115436A successfully refreshed from Google Patents.
US5115436A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Forward error correction code system
Assignee: Nytell Software LLC
•
Filing: 1990-05-04
•
Granted: 1992-05-19
•
Expires: 2010-05-04
Abstract
Abstract In accordance with an inventive FEC code, data is transmitted in codewords comprising n m-bit symbols. Of the n symbols, k symbols are known information symbols and h symbols are parity symbols for erasure correction. All of the symbols of the codeword are elements of a field of 2 m integers which is closed with respect to addition and multiplication such as a Galois field. To determine the h parity symbols, an encoder circuit derives a matrix corresponding to a set of simultaneous equations in terms of the k known information symbols and the h parity symbols. This set of equations is then solved for the h parity symbols so that a codeword is transmitted comprising k known information symbols and h known parity symbols. At a decoder, the values of up to h erased symbols in the codeword may be reconstructed using a similar set of simultaneous equations.
Inventors
- 👤 Anthony J. McAuley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 23:25
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/17
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
209 words
A method for communicating information in a broadband telecommunications network using a forward error correcting code comprising the steps of at an encoder, generating signals representing an n symbol codeword with m bits per symbol, said codeword comprising k known information symbols and h parity symbols having predetermined locations in said codeword, each of said symbols being chosen from a field of 2 m integers which is closed with respect to addition and multiplication, electronically generating signals representing a set of h simultaneous linear algebraic equations in terms of said k known information symbols and said h parity symbols, electronically determining signals which represent solutions of said set of simultaneous equations to determine said h parity symbols, transmitting said signals representing said codeword from said encoder comprising said k information symbols and said h parity symbols, receiving said transmitted signal representing said codeword at a decoder, and at said decoder, electronically correcting up to h symbol erasures of said codeword, said symbol erasures being a combination of erased information symbols and parity symbols, said correcting step comprising the step of electronically generating a set of linear algebraic simultaneous equations and electronically determining signals which represent solutions of said set of simultaneous equations to determine up to h symbol erasures.
Claim 2
Independent Claim
209 words
A method for communicating information in a broadband telecommunications network using a forward error correcting code comprising the steps of at an encoder, generating signals representing an n symbol codeword with m bits per symbol, said codeword comprising k known information symbols and h parity symbols having predetermined locations in said codeword, each of said symbols being chosen from a field of 2 m integers which is closed with respect to addition and multiplication, electronically generating signals representing a set of h simultaneous linear algebraic equations in terms of said k known information symbols and said h parity symbols, electronically determining signals which represent solutions of said set of simultaneous equations to determine said h parity symbols, transmitting said signals representing said codeword from said encoder comprising said k information symbols and said h parity symbols, receiving said transmitted signal representing said codeword at a decoder, and at said decoder, electronically correcting up to h symbol erasures of said codeword, said symbol erasures being a combination of erased information symbols and parity symbols, said correcting step comprising the step of electronically generating a set of linear algebraic simultaneous equations and electronically determining signals which represent solutions of said set of simultaneous equations to determine up to h symbol erasures.
Claim 3
Dependent Claim
41 words
The method of claim 1 where all of said integers are elements of a Galois Field and said set of equations is based on constraining a polynomial formed using the symbols of the codeword to be divisible by a generator polynomial.
Claim 4
Dependent Claim
14 words
The method of claim 1 wherein said field of integers obeys mod m arithmetic.
Claim 5
Dependent Claim
14 words
The method of claim 1 wherein said field of integers is a Galois Field.
Claim 6
Dependent Claim
45 words
The method of claim 1 for communicating information in a broadband telecommunication network using a forward error correcting code wherein, said receiving step entails loading said symbols of said codeword immediately for processing as said symbols are received without awaiting receipt of all codeword symbols.
Claim 7
Dependent Claim
152 words
A forward error correction coding circuit comprising: an input accumulation circuit comprising a linear array of interconnected input accumulation cells for receiving n input symbols of a codeword comprising k known symbols and h unknown symbols, for marking the positions of the unknown symbols and for forming weighted accumulations of the known symbols, an equation generation circuit comprising a linear array of equation generation cells wherein each one of said equation generation cells corresponds to one of said input accumulation cells for receiving unknown symbol position markers and weighted accumulations of said known symbols from said corresponding input accumulation cell and for outputting a matrix corresponding to a system of simultaneous equations for determining said unknown symbols, and a simultaneous equation solver circuit comprising a two dimensional array of interconnected simultaneous equation cells for receiving said matrix from said equation generation circuit and for solving said matrix to obtain said unknown symbols.
Claim 8
Dependent Claim
152 words
A forward error correction coding circuit comprising: an input accumulation circuit comprising a linear array of interconnected input accumulation cells for receiving n input symbols of a codeword comprising k known symbols and h unknown symbols, for marking the positions of the unknown symbols and for forming weighted accumulations of the known symbols, an equation generation circuit comprising a linear array of equation generation cells wherein each one of said equation generation cells corresponds to one of said input accumulation cells for receiving unknown symbol position markers and weighted accumulations of said known symbols from said corresponding input accumulation cell and for outputting a matrix corresponding to a system of simultaneous equations for determining said unknown symbols, and a simultaneous equation solver circuit comprising a two dimensional array of interconnected simultaneous equation cells for receiving said matrix from said equation generation circuit and for solving said matrix to obtain said unknown symbols.
Claim 9
Dependent Claim
48 words
The circuit of claim 6 wherein said coding circuit is an encoder circuit and wherein said k known symbols are k information symbols to be transmitted and said h unknown symbols are h parity symbols to be used for erasure correction and having known locations in said codeword
Claim 10
Dependent Claim
30 words
The circuit of claim 6 wherein said coding circuit is a decoder and wherein said k known symbols are k received symbols and said h unknown symbols are h erasures.
Claim 11
Dependent Claim
38 words
The coding circuit of claim 6 wherein said input accumulation circuit comprises an array of h input accumulation cells linked together in a chain, each of said cells comprising a Galois Field adder and a Galois Field multiplier.
Claim 12
Dependent Claim
38 words
The coding circuit of claim 6 wherein said equation generation circuit comprises h equation generation cells linked together in a chain, each of said equation generation cells comprising a Galois field multiplier for calculating elements of said matrix
Claim 13
Dependent Claim
42 words
The coding circuit of claim 6 wherein said simultaneous equation circuit comprises an array of cells having h+1 columns and h rows interconnected by horizontal and vertical buses, each of said cells comprising a Galois Field multiplier and a Galois Field adder.
Claim 14
Dependent Claim
35 words
The forward error correction coding circuit of claim 6 wherein each of said codeword symbols received at said input accumulation cells is loaded upon receipt for further processing without awaiting receipt of all codeword symbols.
Claim 15
Dependent Claim
182 words
An electronic coding method for communicating signals in a broadband transmission network comprising the steps of at an encoder and a decoder, electronically producing signals representing a codeword having symbols with each symbol having m-bits, said codeword comprising k information symbols and h parity symbols, and where, at said encoder, k information symbols are of known value and location and h parity symbols are of known location but unknown value, and where, at said decoder, up to h of any of said n symbols are of known location but unknown value, all of the symbols of the codeword being elements of a closed field of integers with 2 m elements, said producing step further comprising at a coding circuit, electronically forming signals representing a matrix of values corresponding to a set of linear algebraic equations derived by constraining a polynomial formed using the codeword symbols as coefficients to be divisible by a generator polynomial, and electronically determining signals representing the value of said h unknown symbols at said encoder and up to h unknown symbols at said decoder by solving said matrix.
Claim 16
Dependent Claim
182 words
An electronic coding method for communicating signals in a broadband transmission network comprising the steps of at an encoder and a decoder, electronically producing signals representing a codeword having symbols with each symbol having m-bits, said codeword comprising k information symbols and h parity symbols, and where, at said encoder, k information symbols are of known value and location and h parity symbols are of known location but unknown value, and where, at said decoder, up to h of any of said n symbols are of known location but unknown value, all of the symbols of the codeword being elements of a closed field of integers with 2 m elements, said producing step further comprising at a coding circuit, electronically forming signals representing a matrix of values corresponding to a set of linear algebraic equations derived by constraining a polynomial formed using the codeword symbols as coefficients to be divisible by a generator polynomial, and electronically determining signals representing the value of said h unknown symbols at said encoder and up to h unknown symbols at said decoder by solving said matrix.
Claim 17
Dependent Claim
54 words
The electronic coding method of claim 12 for communicating signals in a broadband transmission network further comprising the steps of transmitting the codeword of n known symbols generated at said encoder to said decoder, and, at said decoder, generating up to h unknown symbols using non-erased symbols of the codeword received from said encoder.
References Cited (Backward Citations)
US4586183A
Cited
US4866654A
Cited
US4809275A
Cited
US4852098A
Cited
US4939733A
Cited
US4835775A
Cited
US4958348A
Cited
US5007067A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-05-19 | 1995-11-18 | 1996-05-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-05-19 | 1999-11-18 | 2000-05-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-05-19 | 2003-11-18 | 2004-05-19 | $7700.00 | Window Closed / Lapsed |