US5007067A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Diversity coding for transparent self-healing communications networks
Assignee: Nokia Bell Labs
•
Filing: 1989-09-29
•
Granted: 1991-04-09
•
Expires: 2009-09-29
Abstract
Abstract This invention is a technique for the substantially instantaneous self-healing of digital communications networks. Digital data streams from each of N nearby sources are combined and encoded to produce N+M coded data streams using a coding algorithm. The N+M coded data streams are then each transmitted over a separate long haul communications link to a decoder where any N of the N+M coded data streams can be decoded uniquely to produce the original N data streams. The orginal N data streams are then distributed to their respective separate end destinations. If any M or less of the N+M long haul communications links fails, i.e. as in a telephone line that gets cut or a long distance switch that fails, no rerouting of traffic need be done. Rather, the receiver detects loss of carrier on the failed link(s), and immediately supplies the missing data by decoding the data from the at least N remaining links. The technique overcomes a long felt problem of trying to reroute traffic by using sophisticated resource allocation techniques when a communications link fails.
Inventors
- 👤 Ender Ayanoglu
- 👤 Richard D. Gitlin
- 👤 Chih-Lin I
- 👤 James E. Mazo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 14:01
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/02; H04L25/00; H04L25/38; H04L25/40; H04L25/49; H04L25/4906; H04L25/4908
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
132 words
In a communications system comprising a plurality of N independent data streams and a pluraity of N+M communications links, a method of providing protection against the failure of up to M of the N+M communications links, M>1, comprising the steps of: (a) encoding the N independent data streams to generate N+M separate coded streams, any N of which may be used to decode the N independent data streams; said step of encoding including the step of generating a matrix product GD where D is a vector comprising N digital data symbols, one digital data symbol from each of the data streams, and G is a matrix comprising M+N rows, each row comprising N digital elements; (b) transmitting each of the N+M coded streams over a separate one of the N+M communications links.
Claim 2
Dependent Claim
132 words
In a communications system comprising a plurality of N independent data streams and a pluraity of N+M communications links, a method of providing protection against the failure of up to M of the N+M communications links, M>1, comprising the steps of: (a) encoding the N independent data streams to generate N+M separate coded streams, any N of which may be used to decode the N independent data streams; said step of encoding including the step of generating a matrix product GD where D is a vector comprising N digital data symbols, one digital data symbol from each of the data streams, and G is a matrix comprising M+N rows, each row comprising N digital elements; (b) transmitting each of the N+M coded streams over a separate one of the N+M communications links.
Claim 3
Dependent Claim
23 words
The method according to claim 1 wherein the generator matrix G is arranged such that any combination of N rows are linearly independent.
Claim 4
Dependent Claim
23 words
The method according to claim 2 wherein the matrix G is equivalent to an N×N identity matrix concatenated with an M×N parity matrix.
Claim 5
Dependent Claim
69 words
The method according to claim 3 wherein the M×N parity matrix comprises M rows, each row comprising N elements, and wherein each element is assigned a separate value r.sup.(i-1)(j-1), where 1≦i≦M, i is one of M row numbers, 1≦j≦N, j is one of N column numbers, and r is a primitive root of a finite field, or proportional to a root of unity in a field of complex numbers.
Claim 6
Dependent Claim
144 words
The method according to claim 3 wherein the M×N parity matrix is equivalent to a matrix formed from a product A -1 B, wherein A comprises M rows, each row comprising M elements, and wherein each element is assigned a separate value r.sup.(i-1)(j-1), where 1≦i≦M, i is one of M row numbers, N+1≦j≦N+M, j is one of M column numbers, and r is a primitive root of a finite field, or proportional to a root of unity in a field of complex numbers, and wherein B comprises M rows, each row comprising N elements, and wherein each element is assigned a separate value r.sup.(i-1)(j-1) where 1≦i≦M, i is one of M row numbers, 1≦j≦N, j is one of N column numbers, and r is a primitive root of a finite field, or proportional to a root of unity in a field of complex numbers.
Claim 7
Dependent Claim
51 words
The method according to claim 1, 2, 3, 4, or 5 wherein the plurality of N data streams are produced from a plurality of sources, and wherein said step (a) comprises the step of partially encoding the N independent data streams at each of the plurality of N or fewer sources.
Claim 8
Dependent Claim
51 words
The method according to claim 1, 2, 3, 4, or 5 wherein the plurality of N data streams are received at a plurality of destinations, and wherein said step (d) comprises the step of partially decoding the N independent data streams at each of the plurality of N or fewer destinations.
Claim 9
Dependent Claim
109 words
A communications system for conveying N data streams of interest, said communications system comprising: means for encoding the N data streams of interest to generate N+M coded streams, where M>1 and where any N of the N+M coded streams may be used to decode the N data streams of interest; said means for encoding comprising means for generating a matrix product GD where D comprises N digital data symbols, one digital data symbol from each of the data streams, and the matrix G comprises M+N rows, each row comprising N digital elements; N+M communications links, each communications link being disposed for conveying a separate one of the coded streams.
Claim 10
Dependent Claim
109 words
A communications system for conveying N data streams of interest, said communications system comprising: means for encoding the N data streams of interest to generate N+M coded streams, where M>1 and where any N of the N+M coded streams may be used to decode the N data streams of interest; said means for encoding comprising means for generating a matrix product GD where D comprises N digital data symbols, one digital data symbol from each of the data streams, and the matrix G comprises M+N rows, each row comprising N digital elements; N+M communications links, each communications link being disposed for conveying a separate one of the coded streams.
Claim 11
Dependent Claim
23 words
The communication system according to claim 8 wherein the G matrix is arranged such that any combination of N rows are linearly independent.
Claim 12
Dependent Claim
24 words
The communications system according to claim 9 wherein the matrix G is equivalent to an N×N identity matrix concatenated with an M×N parity matrix.
Claim 13
Dependent Claim
71 words
The communications system according to claim 10 wherein the M×N parity matrix comprises M rows, each row comprising N elements, and wherein each element is assigned a separate value r.sup.(i-1)(j-1), where 1≦i≦M, where i is one of M row numbers, 1≦j≦M+N, j is one of M+N column numbers, and r is a primitive root of a finite field or proportional to a root of unity in a field of complex numbers.
Claim 14
Dependent Claim
145 words
The communications system according to claim 10 wherein the M×N parity matrix is equivalent to a matrix formed from a product A -1 B, wherein A comprises M rows, each row comprising M elements, and wherein each element is assigned a separate value r.sup.(i-1)(j-1), where 1≦i≦M, i is one of M row numbers, N+1≦j≦N+M, j is one of M column numbers, and r is a primitive root of a finite field, or proportional to a root of unity in a field of complex numbers, and wherein B comprises M rows, each row comprising N elements, and wherein each element is assigned a separate value r.sup.(i-1)(j-1) where 1≦i≦M, i is one of M row numbers, 1≦j≦N, j is one of N column numbers, and r is a primitive root of a finite field, or proportional to a rood of unity in a field of complex numbers.
Claim 15
Dependent Claim
53 words
The communications system according to claim 8, 9, 10, 11, or 12 wherein the plurality of N independent data streams are produced from a plurality of sources, and wherein said means for encoding comprises means for partially encoding the N independent data streams at each of the plurality of N or fewer sources.
Claim 16
Dependent Claim
56 words
The communications system according to claim 8, 9, 10, 11, or 12 wherein the plurality of N independent data streams are received at a plurality of destinations, and wherein said means for receiving and for recovering comprises means for partially decoding the N independent data streams at each of the plurality of N or fewer destinations.
References Cited (Backward Citations)
US3065420A
Cited
US3444516A
Cited
US3681694A
Cited
US3878463A
Cited
US4370745A
Cited
US4541095A
Cited
US4881245A
Cited
US4601046A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-04-08 | 1994-10-08 | 1995-04-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-04-08 | 1998-10-08 | 1999-04-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-04-08 | 2002-10-08 | 2003-04-09 | $7700.00 | Window Closed / Lapsed |