Error correction systems with modified Viterbi decoding

• US 5,539,757 A
• Filed: 12/22/1993
• Issued: 07/23/1996
• Est. Priority Date: 12/22/1993
• Status: Expired due to Fees

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Zhou, Yong, Thorkildsen, Reed, Cox, Richard V.
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US08/173,818
• Time in Patent Office: 944 Days
• Field of Search: 371/43, 371/44, 371/45, 371/37
• US Class Current: 714/795
• CPC Class Codes: H03M 13/3961 Arrangements of methods for branch or transition metric calculation
• CPC Class Codes: H03M 13/4107 implementing add, compare, select [ACS] operations
• CPC Class Codes: H03M 13/4161 implementing path management
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing
• CPC Class Codes: H03M 13/6569 Implementation on processors, e.g. DSPs, or software implementations
• CPC Class Codes: H03M 13/6583 Normalization other than scaling, e.g. by subtraction
• CPC Class Codes: H04L 1/0054 Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms

Abstract

In a communications system, a convolutional encoder encodes data from a data source and a modified Viterbi decoder decodes the encoded data after the encoded dated passes through an error producing channel. The decoder calculates selected metric increments, known as kernel metric increments, for half the states, and selects survivor metrics for all states.

Claims

1. A communication system, comprising:

a channel;

a modulator at one end of the channel and a demodulator at the other end of the channel;

a convolutional encoder having a constant length K and N=2.sup.(K-1) states and responsive to a data source and coupled to the modulator;

a modified Viterbi decoder coupled to said demodulator;

said decoder including means for reading successive words from the demodulator;

said decoder including means for calculating kernel metric increments for only N/2 states;

said decoder including selector means for comparing accumulative metrics for each metric increment and selecting survivors for two new states; and

tracing means in said decoder for tracing back from a zero state;

said calculating means being for calculating up to N/2 metrics.

2. A modified Viterbi decoder for decoding from a channel, encoded words in code having a constant length K and N=2.sup.(K-1) words, comprising:

means for reading words from the channel;

means for calculating kernel metric increments for only N/2 states;

selector means for comparing accumulative metrics for each metric increment and selecting survivors for two new states; and

tracing means for tracing back from a zero state;

said calculating means being for calculating up to N/2 metric increments.

3. A method of processing information, comprising the following steps:

encoding data from a data source in a convolutional decoder;

modulating the encoded data;

passing the modulated and encoded data through a data channel;

demodulating the data from the channel;

decoding the demodulated data with a modified Viterbi decoder;

the decoding step including reading successive total of N states of successive words from the demodulator;

the decoding step further including calculating kernel metric increments for only N/2 metrics in said decoder;

said decoding step further including comparing metrics and selecting survivors for two new states; and

tracing back from a first state.

4. A method of processing encoded data, comprising:

reading a successive total of N states of successive words in the data;

calculating kernel metric increments for only N/2 metrics in the words;

comparing metrics and selecting survivors for two new states; and

tracing back from a first state.