Maximum-likelihood decoding method and device

• US 5,432,820 A
• Filed: 07/26/1993
• Issued: 07/11/1995
• Est. Priority Date: 11/19/1990
• Status: Expired due to Term

• Current Assignee: Toshiba Storage Device Corp (Toshiba Corporation)
• Original Assignee: Fujitsu Limited
• Inventors: Kasai, Kiichirou, Mutoh, Hiroshi, Sugawara, Takao, Mizoshita, Yoshifumi, Aikawa, Takashi
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): Kobayashi, Duane
• Application Number:
  US07/910,311
• Time in Patent Office: 715 Days
• Field of Search: 371/43, 375/94, 375/101, 375/14, 375/99
• US Class Current: 375/341
• CPC Class Codes: H03M 13/39 Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes

Abstract

A maximum-likelihood decoding method for decoding an input signal subject to intersymbol interference. An assumption is made of a measure of an interference caused by a future signal that is later in a sequence than an assumed data sequence, on the basis of a predetermined bits of sample values of said input signal that are earlier in a sequence than an assumed data sequence stored in an assumed path memory (104). An assumed sample value of said input signal by referring to this measure of interference. Maximum-likelihood decoding is conducted on said input signal, on the basis of this assumed sample value and a sample value of said input signal; a plurality of survivor paths are generated and stored in a path memory (102); data for the most likely one of survivor paths is output as a decoded data sequence.

Claims

1. A maximum-likelihood decoding method for decoding an input signal subject to intersymbol interference, comprising the steps of:

(a) assuming a measure of interference caused by a future signal, that is later in time sequence than an assumed data sequence, on the basis of predetermined bits of sample values of said input signal that is earlier in time sequence than the assumed data sequence stored in an assumed path memory;

(b) obtaining a sample value of said input signal by referring to the measure of interference; and

(c) generating a plurality of survivor paths by conducting maximum-likelihood decoding on said input signal, employing an assumed sample value and said obtained sample value of said input signal and, thereafter, storing the generated survivor paths in a path memory and outputting data of the most likely survivor path as a decoded data sequence.

2. A maximum-likelihood decoding method as claimed in claim 1, wherein:

said step (a) comprises a step of assuming a measure of interference, caused by said future signal, on the basis of said predetermined bits of sample values of said input signal and said assumed data sequence; and

said step (c) comprises a step of obtaining an assumed sample value on the basis of said assumed data sequence and data of said survivor path.

3. A maximum-likelihood decoding method as claimed in claim 1, further comprising:

in step (a), assuming said measure of interference caused by said future signal, on the basis of said predetermined bits of sample values of said input signal and of said assumed data sequence; and

(d) assuming a measure of interference caused by a past signal that is earlier in time sequence than said assumed data sequence, on the basis of predetermined bits of sample values of an input signal that are later in time sequence than said assumed data sequence, and wherein said step (b) further comprises a step of obtaining said assumed sample value, on the basis of a measure of interference caused by said future signal, said assumed data sequence and a measure of interference caused by said past signal.

4. A maximum-likelihood decoding method as claimed in claim 1, further comprising:

in step (a), assuming a measure of interference caused by said future signal, on the basis of said predetermined bits of sample value of an input signal and said assumed data sequence;

(d) obtaining a first measure of interference caused by a past signal that is later in a sequence than said assumed data sequence, on the basis of a plurality of bits of sample values of said input signal that are later in time sequence than said assumed data sequence;

(e) obtaining a second measure of interference caused by a past signal on the basis of data of said survivor path;

(f) selecting the second measure of interference caused by said past signal when an output data from the last storage of said path memory converges, and selecting the first measure of interference caused by said past signal when there is no convergence; and

said step (b) obtains said assumed sample value on the basis of the selected measure of interference, said assumed data sequence and the measure of interference caused by said future signal.

5. A maximum-likelihood decoding method as claimed in claim 1, further comprising:

(d) generating a tentative decoded data sequence by equalizing and digitizing said input signal, wherein said step (b) further comprises a step of obtaining an assumed sample value in accordance with the following equation;

##EQU17## where a_i represents one bit of an assumed data sequence stored in an assumed path memory, b_i represents one bit of decoded data sequence stored in a path memory, c_i represents one bit of a tentative decoded data sequence obtained in step (d), g_-i represents a sample value of an input signal having an isolated waveform, g represents an assumed sample value, and each of _i, _k, _m represents an integer.

6. A maximum likelihood decoding method as recited in claim 1, further comprising:

in step (b), obtaining an assumed sample value in accordance with the following equation;

##EQU18## where a_i represents one bit of an assumed data sequence stored in an assumed path memory, b_i represents one bit of decoded data sequence stored in a path memory, g_-i represents a sample value of an input signal having an isolated waveform, X_-m-1 represents a sample value of an input signal, y represents an assumed sample value, and each of _i, _k, _m represents an integer.

7. A maximum-likelihood method as claimed in claim 1, further comprising:

in step (b), obtaining an assumed sample value in accordance with the following equation;

##EQU19## where a_i represents one bit of an assumed data sequence stored in an assumed path memory, b_i represents one bit of a decoded data sequence stored in a path memory, g_-1 represents a sample value of an input signal having an isolated waveform, X_m+1 and X_-m-1 each represents a sample value of an input signal, y represents an assumed sample value, and each of _i, _k, _m represents an integer.

8. A maximum-likelihood decoding method as claimed in claim 1, further comprising:

(d) generating a tentative decoded data sequence by conducting maximum-likelihood decoding on a sample value of said input signal; and

in step (b), obtaining an assumed sample value in accordance with the following equation;

##EQU20## where a_i represents one bit of an assumed data sequence stored in an assumed path memory, b_i represents one bit of a decoded data sequence stored in a path memory, c_i represents one bit of a tentative decoded data sequence obtained in step (d), g_-1 represents a sample value of an input signal having an isolated waveform, y represents an assumed sample value, and each of _i, _k, _m represents an integer.

9. A maximum-likelihood decoding method as claimed in claim 8, further comprising:

(e) conducting an error correcting decoding on a tentative decoded data sequence generated in step (d), and generated a tentative decoded data sequence.

10. A maximum-likelihood decoding device comprising:

A/D (analog/digital) converting means for conducting sampling on an input signal and generating a sample value;

an assumed path memory for storing an assumed data sequence;

an assumed sample value computing means for computing an assumed sample value of said input signal by assuming a measure of interference caused by a future signal that is later in time sequence than an assumed data sequence on the basis of predetermined bits of sample values of said input signal that are earlier in time sequence than an assumed data sequence stored in said assumed path memory, and by referring to said measure of interference; and

decoding means for outputting the most likely one of a plurality of survivor paths, as a decoded data sequence, after storing the survivor paths generated by conducting maximum-likelihood decoding on said input signal on the basis of said assumed sample value and a sample value of said input signal.

11. A maximum-likelihood decoding device as claimed in claim 10, wherein said assumed sample value computing means further comprises:

first means for assuming a measure of interference caused by said future signal, on the basis of said predetermined bits of sample values of an input signal and said assumed data sequence; and

second means for obtaining said assumed sample value on the basis said measure of interference, said assumed data sequence, and a survivor path.

12. A maximum-likelihood decoding device as claimed in claim 10, wherein:

said assumed sample value computing means comprises first means for assuming a measure of interference caused by said future signal on the basis of said predetermined bits of sample values of an input signal and said assumed data sequence;

said maximum-likelihood decoding device comprises second means for assuming a measure of interference caused by a past signal that is earlier in time sequence than said assumed data sequence, on the basis of a predetermined bits of sample values of an input signal that are later in time sequence than said assumed data sequence, and

said assumed sample value computing means comprises third means for obtaining said assumed sample value on the basis of a measure of interference caused by said future signal, said assumed data sequence, and a measure of interference caused by said past signal.

13. A maximum-likelihood decoding device as claimed in claim 10, wherein;

said assumed sample value computing means further comprises first means for assuming a measure of interference on the basis of said predetermined bits of sample values of an input signal and said assumed data sequence and

said maximum-likelihood decoding device further comprises;

second means for obtaining a firs measure of interference caused by a past signal that is earlier in a sequence than said assumed data sequence, on the basis of a plurality of bits of sample values of said input signal that are later in a sequence than said assumed data sequence;

third means for obtaining a second measure of interference caused by a past signal, on the basis of data of said survivor path;

fourth means for selecting the second measure of interference caused by said past signal when an output from the last storage of said path memory converges, and for selecting the first measure of interference caused by said past signal when there is no convergence; and

said assumed sample value computing means obtains said assumed sample value on the basis of the measure of interference selected, said assumed data sequence, and a measure of interference caused by said future signal.

14. A maximum-likelihood decoding device as claimed in claim 10, further comprising:

generating means for generating a tentative decoded data sequence by equalizing and digitizing said input signal; and

said assumed sample value computing means further comprises means for obtaining assumed sample value in accordance with the following equation;

##EQU21## where a_i represents one bit of assumed data sequence stored in an assumed path memory, b_i represents one bit of a decoded data sequence stored n a path memory, c_i represents one bit of a tentative decoded data sequence obtained in step (d), g_-i represents a sample value of an input signal having an isolated waveform, g represents an assumed sample value, and each of _i, _k, _m represents an integer.

15. A maximum-likelihood decoding device as claimed in claim 10, wherein:

said assumed sample value computing means further comprises means for obtaining an assumed sample value in accordance wit the following equation;

##EQU22## where a_i represents one bit of an assumed data sequence stored in an assumed path memory, b_i represents one bit of a decoded data sequence stored in a path memory, g_-i represents a sample value of an input signal having an isolated waveform, x_m+1 and X_-m-1 each represents a sample value of an input signal, and each of _i, _k, _m represents an integer.

16. A maximum-likelihood decoding device as claimed in claim 10, wherein

said assumed sample value computing means comprises steps for obtaining an assumed sample value in accordance with the following equation:

##EQU23## where a_i represents one bit of an assumed data sequence stored in an assumed path memory, b_i represents one bit of a decoded data sequence stored in a path memory, g_-i represents a sample value of an input signal having an isolated waveform, X_m+1 and X_-m-1 each represents a sample value of an input signal, and _i, _k, m each represents an integer.

17. A maximum-likelihood decoding device as claimed in claim 10, further comprising:

generating means for conducting maximum-likelihood decoding on a sample value of said input signal and for generating a tentative decode data sequence, wherein said assumed sample value computing means further comprises means for obtaining an assumed sample value in accordance with the following equation;

##EQU24## where a_i represents one bit of an assumed data sequence stored in an assumed path memory, b_i represents one bit of a decoded data sequence stored in a path memory, c_i represents one bit of a tentative decoded data sequence, g_-i represents a sample value of an input signal having an isolated waveform, y represents an assumed sample value, and each of _i, _k, _m represents an integer;

said generating means comprises a first Viterbi decoder, said A/D converting means, an assumed path memory and an assumed sample value computing means; and

said decoding means constitutes a second Viterbi decoder.

18. A maximum-likelihood decoding device as claimed in claim 17, further comprising:

generating means for generating a tentative decoded data sequence after conducting error correcting decoding on a tentative decoded data sequence generated in said generating means.

19. A maximum-likelihood decoding device as claimed in claim 18, wherein said generating means generates said tentative decoded data sequence by generating pulses from the equalized input.

20. A maximum-likelihood decoding device as claimed in claim 14, wherein said generating means further comprises:

clock pulse generating means for generating clock pulses based on an equalized input signal; and

A/D converting means for generating said tentative decoded data sequence by digitizing an input signal that is equalized in synchronization with said clock pulses.