United States Patent (19)
`Kobayashi et al.
`
`54 SYSTEM AND METHOD FOR ERROR
`CORRECTING ARECEIVED DATA STREAM
`IN A CONCATENATED SYSTEM
`
`75 Inventors: Hisashi Kobayashi; Jan Bajcsy, both
`of Princeton, N.J.
`73 Assignee: The Trustees of Princeton University,
`Princeton, N.J.
`
`21 Appl. No.: 08/840,383
`22 Filed:
`Apr. 28, 1997
`(51) Int. Cl." .................................................... H03M 13700
`52 U.S. Cl. .............................................................. 714/755
`58 Field of Search ..................................... 714/755, 752;
`371/37.4, 43.7
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`3,622,986 11/1971 Tang et al. ........................... 340/146.1
`5,721,745 2/1998 Hladik et al. .......................... 371/37.4
`OTHER PUBLICATIONS
`Error-Correcting Codes, Second Ed., Peterson et al., pp.
`2-3-8.
`Prentice-Hall Series in Computer Applications in Electrical
`Engineering, Shu Lin et al., pp. 274-280, “Error Control
`Coding: Fundamentals and Applications”.
`IBM Journal of Research and Development, Jan. 1971, vol.
`15 H. Kobayashi, pp. 64-74, “ Application of Probabilistic
`Decoding to Digital Magnetic Recording Systems”.
`Kluwer Academic Publishers, Jan W. M. Bergmans, pp.
`316-323, “Digital Baseband Transmission and Recording”.
`IEEE Communications Magazine, Apr. 1986-vol. 24, No. 4,
`Carl-Erik Sundberg, pp. 26-38, “Continous Phase Modula
`tion'.
`
`US006029264A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,029,264
`Feb. 22, 2000
`
`IEEE Transactions on Communication Technology, vol.
`COM-19, No. 4 Aug. 1971, H. Kobayashi et al., pp.
`467-477, “On Decoding of Correlative Level Coding Sys
`tems with Ambiguity Zone Detection”.
`IEEE Transactions on Communication Technology, vol.
`COM-19, No. 6 Dec. 1971, H. Kobayashi, pp. 1087–1100,
`“A Survey of Coding Schemes for Transmission or Record
`ing of Digital Data”.
`IEEE Transactions on Information Theory, vol. IT-17, No.
`5, Sep. 1971, H. Kobayashi, pp. 586–594, “Correlative
`Level Coding and Maximum-Likelihood Decoding”.
`IEEE Transactions on Communications, vol. 44-No. 10,
`Oct. 1996, C. Berrou et al., pp. 1261–1270, “Near Optimum
`Error Correcting Coding and Decoding: Turbo-Codes'.
`Xiao-an Wang, Stephen B. Wicker, A Soft-Output Decoding
`Algorithm for concatenated System, IEEE, pp. 543–553,
`Feb. 3, 1996.
`Primary Examiner Albert De Cady
`Assistant Examiner. Shelly A Chase
`57
`ABSTRACT
`A received signal is first converted into a digital Sequence
`that may contain "erasures” (or ambiguity Symbols) as well
`as errors. Then iterative decoding is applied in order to
`eliminate or reduce the erasures. This decoding procedure
`WorkS effectively with the associated transmitter that adopts
`a concatenation of an outer coder, a permutation and an inner
`coder. The principal of the invention is also applicable to a
`System in which the inner coder is replaced by a “digital
`modulator' that introduces Some constraint, or a channel
`that introduces Some memory Such as partial response
`Signaling, interSymbol interference or multipath propaga
`tion. The invention can be applied to many existing Systems
`while maintaining “backward compatibility” in the Sense
`that the transmitter side need not be modified.
`
`12 Claims, 14 Drawing Sheets
`
`10
`
`22
`ERASURE/
`ERROR
`CORRECTOR
`
`14
`
`RECEIVER
`
`18
`
`16
`
`
`
`INNER
`DECODER
`
`INVERSE
`PERMUTATION
`
`OUTER
`DECODER
`
`26
`
`24
`
`N
`
`SINK
`
`NPROvy
`YES
`
`
`
`
`
`PERMUTATION
`
`Page 1 of 23
`
`SAMSUNG EXHIBIT 1005
`
`

`

`U.S. Patent
`
`
`
`6,029.264
`
`
`
`TENNWHO (HELITO
`
`Page 2 of 23
`
`

`

`U.S. Patent
`
`Feb. 22, 2000
`
`Sheet 2 of 14
`
`6,029.264
`
`
`
`
`
`TENNWHO (JELITO
`
`èJELLIWSNW}}|
`
`èJEAIBOE}}
`
`Page 3 of 23
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 22, 2000
`Feb. 22, 2000
`
`Sheet 3 of 14
`Sheet 3 of 14
`
`6,029.264
`6,029,264
`
`V¢éOld
`
`Oo
`Ww
`
`oO
`Ww
`
`=
`
`LNO
`
`—a
`
`— W
`
`w
`
`oO
`uw)
`
`m
`
`co
`
`™
`N
`
`co
`N
`
`©
`
`Ww
`m
`
`st
`
`~
`
`NI
`
`
`
`Page 4 of 23
`
`Page 4 of 23
`
`
`

`

`U.S. Patent
`
`TENNWHO±
`
`
`
`
`
`
`
`
`
`6,029.264
`
`XJEWWEITHELNI
`
`Page 5 of 23
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 22, 2000
`
`Sheet 5 of 14
`
`6,029.264
`6,029,264
`
`g9Sls
`
`
`
`V9Ols TANNVHOD
`
`S3YNSVYS
`
`Page 6 of 23
`
`Page 6 of 23
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 22, 2000
`
`Sheet 6 of 14
`
`6,029.264
`6,029,264
`
`
`
`92veQL
`
`
`
`Sl”yIAIGOIY
`
`vl
`
`ZZ
`GC
`
`Ol
`
`S4Aé44000350
`NOLLWLNWa3d
`
`JISYSANI
`
`YANNI
`
`Y¥300030
`
`/3xNsves
`
`YOuNS
`
`YOLOIYYOO
`
`VLO9I4
`
`NOLWLAWYSd
`
`gZols
`
`TANNVHO
`
`YANNI
`
`Y3IdOONS
`NOILWLAWYSd
`YIGOONS
`
`Y3LNO
`
`YALLINSNVYL
`
`JOYNOS
`
`Page 7 of 23
`
`
`
`
`
`
`
`
`
`Page 7 of 23
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 22, 2000
`
`Sheet 7 of 14
`
`6,029.264
`
`
`
`>{BC]OONE NJENNI
`
`
`
`
`
`
`
`
`
`(JEWWEITHE IN?
`
`
`
`NEC]OOEO (JENNI
`
`Page 8 of 23
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 22, 2000
`Feb. 22, 2000
`
`
`
`6,029,264
`6,029.264
`
`FIG.9B
`
`Sheet 8 of 14
`Sheet 8 of 14
`
`FIG.9A
`
`Page 9 of 23
`
`Page 9 of 23
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 22, 2000
`Feb. 22, 2000
`
`Sheet 9 of 14
`Sheet 9 of 14
`
`6,029,264
`6,029.264
`
`
`
`
`
`
`
`
`
`.
`H - .
`x\s N21,
`t S
`(2
`
`FIG.10B
`ti Lil
`
`-e
`
`
`
`1.
`
`FIG.10A
`
`
`
`
`
`
`
`
`
`=
`
`Page 10 of 23
`
`Page 10 of 23
`
`

`

`U.S. Patent
`
`Feb. 22, 2000
`
`Sheet 10 of 14
`
`6,029.264
`
`
`
`TENNWHO
`
`TENNWHO
`
`Page 11 of 23
`
`

`

`Feb. 22, 2000
`Feb. 22, 2000
`
`Sheet 11 of 14
`Sheet 11 of 14
`
`6,029.264
`6,029,264
`
`U.S. Patent
`U.S. Patent
`
`GtLtols
`
`YOLO3YNOD
`
`3/3
`
`
`
`Page 12 of 23
`
`Page 12 of 23
`
`

`

`Feb. 22, 2000
`
`Sheet 12 of 14
`
`6,029,264
`
`VelOld
`
`élSls
`
`3/3
`
`YOLOINNOO
`
`U.S. Patent
`
`“TANNVHO
`
`
`
`Page 13 of 23
`
`Page 13 of 23
`
`
`

`

`Sheet 13 of 14
`Sheet 13 of 14
`
`6,029.264
`6,029,264
`
`Feb. 22, 2000
`Feb. 22, 2000
`
`etOld
`
`U.S. Patent
`U.S. Patent
`
`
`
`Page 14 of 23
`
`Page 14 of 23
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 22, 2000
`
`Sheet 14 of 14
`
`264
`6,029,264
`
`Volold
`
`avlols
`
`JOUNOS
`
`
`
`Page 15 of 23
`
`Page 15 of 23
`
`
`

`

`1
`SYSTEMAND METHOD FOR ERROR
`CORRECTING ARECEIVED DATA STREAM
`IN A CONCATENATED SYSTEM
`
`FIELD OF THE INVENTION
`
`This invention relates to error correction of a received
`data Stream and more particularly to an error correction
`method and System which employs ambiguity Zone
`detection, permutation and inverse permutation and iterative
`processing to perform the error correction action.
`
`BACKGROUND OF THE ART
`Aprimary objective of any digital communication System
`is to transmit information at the maximum possible rate and
`receive it with minimum errors or distortion. Similarly, a
`main design objective of data Storage System is to allow the
`System to Store information with the maximum possible
`density and to retrieve it with the least possible errors. A
`variety of error control coding Schemes, channels with
`constraint, and digital modulation with constraint have been
`devised to improve data transmission and recording Systems.
`
`15
`
`CONCATENATED ENCODING AND
`DECODING SYSTEMS
`
`Error control codes Such as block codes and convolutional
`codes are usually applied to digital Sequences for the pur
`pose of coping with errors which may happen in bursts as
`well as randomly. Basically, error control coding expands
`the information Sequence by adding additional bits for error
`correction/detection purposes. The encoded Sequence then
`contains Some constraint or redundancy. Such constraint is
`then exploited by the receiver to identify possible errors that
`may exist in the received Sequence. For example, if the
`received Sequence does not satisfy parity-check equations,
`then the receiver detects the existence of Some errors and, in
`Some cases, can correct them.
`In order to achieve a higher performance, a concatenation
`of two error correcting codes is Sometimes adopted. FIG. 1
`depicts Such a concatenated encoding System and the cor
`responding decoding System. Here the term "inner encoder'
`is used in the Sense that the inner encoder is closer to the
`communication channel. Hence a Subsystem including an
`inner encoder, the communication channel and an inner
`decoder, is often called an “outer channel”. The outer
`encoder therefore Sees the Outer channel as the effective
`channel.
`An example is to use a block code (e.g., a Reed-Solomon
`code) as the Outer code and a convolutional code as the inner
`code. An “interleaver' is often placed between the two
`encoders, because when the inner decoder makes erroneous
`decisions, it tends to create bursts of errors due to the nature
`of the convolutional code. FIG. 2 depicts Such a concat
`enated System. An interleaver is an example of a device
`which permutes a data Stream in a manner which is revers
`ible. An example of an interleaver is shown in FIG. 2a, with
`bits 0-63 being serially loaded into adjacent rows. An output
`is obtained by Sequentially accessing adjacent columns of
`bits. The interleaving action disperses adjacent bit values
`and prevents a burst error from affecting a Sequential run of
`bits in the original data Stream.
`By having the interleaver in front of the outer channel, the
`outer encoder and decoder do not have to deal with long
`bursts of errors. (See e.g., S. Lin and D.J. Costello, Jr., Error
`Control Coding:Fundamentals and Applications, Prentice
`Hall, 1983. pp. 535-538.) The type of system represented in
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,029.264
`
`2
`FIG. 2 is closely related to the invention to be described
`below, in that a receiver incorporating the invention can be
`applied to the illustrated class Systems without changing the
`transmitter Side hence, as will be seen, the invention is
`backward compatible with Such existing Systems.
`CHANNELS WITH CONSTRAINT
`The notion of concatenated System can be generalized to
`a System in which the inner encoder is not a conventional
`error correcting encoder (Such as a block code or convolu
`tional code), but is a special type of signaling Scheme or a
`channel with Some constraint or memory. (See e.g., H.
`Kobayashi, “A Survey of Coding Schemes for Transmission
`or Recording of Digital Data”, IEEE Trans. Communication
`Technology, vol. COM-19, pp. 1087–1100, December
`1971).
`Intersymbol interference (ISI) and/or interchannel inter
`ference (ICI) due to channel distortion, may sometimes be
`predominant factors in limiting performance and reliability.
`A number of coding techniques have been developed to
`reduce adverse effects due to these factors. Partial-response
`channel coding is well recognized as a bandwidth-efficient
`transmission technique and can be viewed as a technique to
`shape the Signal Spectrum by introducing a controlled
`amount of ISI. An optimal decoding Structure for a partial
`response channel is known as maximum-likelihood (ML)
`decoding (See e.g., H. Kobayashi, "Application of Proba
`bilistic Decoding to Magnetic Recording Systems”, IBM J.
`of Res. and Develop. Vol. 15, Jan. 1971, pp. 64–74., and H.
`Kobayashi, “Correlative Level Coding and Maximum
`Likelihood Decoding”, IEEE Trans. Information Theory,
`Vol. IT-17, Sep. 1971, pp. 586–594).
`A System with partial-response channel coding and maxi
`mum likelihood decoding has become popular in recent
`years and is often referred to as a PRML System (see e.g., J.
`W. M. Bergmans, “Digital Baseband Transmission and
`Recording”, Kluwer Academic Publishers, 1996).
`Another class of codes, often used in digital recording, is
`run-length limited codes, denoted (d.k)-limited codes. The
`integer parameters d and k represent the minimum and
`maximum numbers of runs of either 0's or 1's that are
`allowed in the encoded Sequence. The lower bound d is
`chosen from the ISI consideration, and the upper bound k is
`Set to insure clock Synchronization capability at the receiver
`Side.
`Both partial-response channels and run-length limited
`codes can be viewed as techniques that introduce Some
`constraints into the digital Sequence to be transmitted.
`Similarly, a channel with ISI and/or multipath fading intro
`duces Some memory in the received Sequence. Such con
`straints or memory should be exploited by the receiver to
`identify possible errors or biases that may exist in the
`received Sequence. FIG.3 shows a generalized concatenated
`System where the inner encoder represents a channel with
`Some constraint.
`
`DIGITAL MODULATION WITH CONSTRAINT
`Techniques similar to partial-response Signaling have
`been developed in digital modulation Schemes. One impor
`tant class of Such modulation techniques is known as con
`tinuous phase modulation (CPM) or continuous envelope
`coded modulation (see e.g., C. E. Sundberg, “Continuous
`Phase Modulation', IEEE Communications Magazine, April
`1986, pp. 25–38). Here, some constraint is introduced in the
`modulated Signal, because the phase values that the modu
`lated Signal is allowed to take are limited to a Subset of the
`
`Page 16 of 23
`
`

`

`3
`Set of phase values defined for the modulation System. An
`example of CPM is MSK (minimum shift keying) in which
`the phases that the modulated Signal is permitted to take at
`a given Symbol time are only the phases adjacent to the
`previous Symbol phase.
`Another class of digital phase modulation techniques with
`Similar properties is those that use differential precoding of
`the data. In this case, the correlation is caused by the
`preceding and consequent modulation. An example of dif
`ferentially precoded digital phase modulation is L/4-QDPSK
`(L/4-Shifted quadrature differential phase shift keying).
`These modulation techniques can be viewed as a means to
`minimize the adverse effects of unknown/time-varying
`channel attenuation, fading and nonlinear power
`15
`amplification, while still allowing bandwidth efficient com
`munication. Since the amplitude of transmitted Signals con
`tains no information, one can reproduce the original infor
`mation even if the amplitude has been Significantly
`distorted. These classes of digital modulation techniques
`have come to be predominantly used in wireleSS communi
`cation Systems. FIG. 4 depicts a concatenated System in
`which the inner encoder is a modulator with Some constraint.
`
`CODED MODULATION
`Instead of concatenating two error control codes, an error
`control code may be concatenated with digital modulation.
`A trellis-coded modulation (TCM) is a well-known example
`in which a convolutional code and digital-phase modulation
`are combined. The receiver can correct most errors
`effectively, Since the receiver can exploit the constraint that
`the received phase Sequence must Satisfy. This is because a
`particular method (called set partitioning) is used to map the
`convolutional code Sequence into the amplitudes and/or
`phases of the modulated Signal. A concatenated System with
`TCM is schematically shown in FIG. 5.
`An optimal decoding Structure for continuous phase
`modulation, precoded digital phase modulation and TCM is
`maximum-likelihood (ML) decoding, Similar to that origi
`nally derived for convolutional codes (i.e., Viterbi decoding)
`and for partial-response Systems.
`ERASURES
`A receiver may be designed to decide that a Symbol
`should be erased when it is received ambiguously. Suppose
`that a channel input is binary, i.e., 0 or 1. When a received
`Symbol is corrupted by Strong noise or interference and its
`value is near the threshold between 0 and 1, then the receiver
`may opt not to make a hard decision regarding the value of
`the symbol, and labels it as “e”, which stands for an erasure.
`To implement an erasure, a quantizer is required with
`additional threshold(s), see FIG. 6a). When the input is
`binary, the output with erasure option can be represented by
`two bits, e.g., by (00), (01) and (10) to denote “0”, “e” and
`“1”, respectively.
`A In coding theory a binary erasure channel (BEC) has
`been well studied (see e.g., W.W. Peterson and E.J. Weldon,
`Jr., “Error Correcting Codes", 2nd Edition, MIT Press, 1994.
`p. 8). The channel characteristic of a BEC is shown in FIG.
`6b, where the possible errors are limited to erased digits. In
`other words 0 is never mistaken as 1 and Vice versa.
`Kobayashi and Tang, “On Decoding of Correlative Level
`Coding Systems with Ambiguity Zone”, IEEE Trans.
`Communications, Vol. COM-19, pp. 467-477, Aug. 1971)
`generalized the erasure concept and applied it to partial
`response Systems. They showed that decoding with the
`generalized erasure, which they termed ambiguity Zone
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,029.264
`
`4
`decoding can achieve a near-optimum performance, while
`retaining decoding complexity at a minimal level.
`AS discussed above, a large class of digital communica
`tion or recording Systems can be viewed as concatenated
`Systems in which each building block may be an error
`control encoder, a modulator with constraints, or a channel
`with constraints. The conventional method of receiving Such
`Signals is to perform the inverse operations of the transmit
`ter's building blocks, in the reverse order. In other words,
`building blocks at the receiver are an inner decoder, a
`de-interleaver and an Outer decoder. The inner decoder
`attempts to do its best in correcting errors and delivers the
`resultant output to the outer decoder. Such a decoding
`procedure may be called a “one-path' decoding method.
`Such a one-path method is still Susceptible to being unable
`to correct many error States, notwithstanding a general
`ability to correct for many error conditions.
`Accordingly, it is an object of the invention to improve
`error correction performance of a receiver System which
`receives digital data over a noisy communication channel
`(e.g., radio channel, cable channel).
`It is another object of the invention to improve error
`correction performance of a System which retrieves data
`from a memory (e.g., digital magnetic recording disk) which
`is Subject to random/burst noise or medium defects.
`SUMMARY OF THE INVENTION
`A method error corrects a received data Stream in a
`general concatenated System in which a plurality of encod
`ing algorithms and/or entities which impose a constraint are
`connected either in series or in parallel or both. The method
`includes the Steps of: (a) Sampling signal levels in the
`received data Stream and assigning discrete data values to
`Sampled Signal levels falling in non-ambiguous amplitude
`and/or phase ranges and assigning ambiguity values to
`Sampled Signal levels falling within an ambiguity range of
`amplitude and/or phase values, and outputting a quantized
`data Stream comprising the discrete data values and ambi
`guity values; (b) decoding and error correcting data values
`making up the quantized data Stream to create an error
`corrected data Stream, the decoding including plural decod
`ing actions for decoding data that has been encoded or
`Subjected to a constraint by the plural concatenated entities,
`c) correcting data values and ambiguity values in the quan
`tized data Stream by Substitution of corrected data values
`from the error corrected data Stream into corresponding data
`values in the quantized data Stream, to thereby create a
`revised data stream; and d) iteratively Subjecting the revised
`data Stream, both as is and as further revised, to steps b) and
`c) to improve an error correction State of the revised data
`Stream. In a preferred embodiment, the data making up the
`received data Stream has been Subjected to a permutation
`action to time-wise Separate original contiguous data values.
`The method Subjects the quantized data Stream to an inverse
`permutation action in producing the error-corrected data
`Stream and further re-permutes the error-corrected data
`Stream (in step (c)) to return it to a format identical to that
`of the quantized data Stream before the Substitution is
`performed.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a prior art concatenated
`System for decoding and error correcting a received data
`Stream.
`FIG. 2 is a block diagram of a transmitter and receiver in
`a concatenated System, with interleaving, for decoding and
`error correcting a received data Stream.
`
`Page 17 of 23
`
`

`

`S
`FIG. 2a is a Schematic which illustrates an interleaving
`proceSS.
`FIG. 3 is a block diagram of a concatenated System for
`decoding and error correcting a received data Stream,
`wherein the inner encoder is a channel with constraint.
`FIG. 4 is a block diagram of a concatenated System for
`decoding and error correcting a received data Stream,
`wherein the inner encoder is a modulator with constraint.
`FIG. 5 is a block diagram of a concatenated system for
`decoding and error correcting a received data Stream,
`wherein the inner encoder is a trellis-coded modulator
`(TCM).
`FIG. 6a is a block diagram of a prior art erasure channel.
`FIG. 6b is a channel transition diagram of the prior art
`erasure channel.
`FIG. 7a is a block diagram of a transmitter portion of a
`concatenated System for decoding and error correcting a
`received data Stream, which Systemincorporates the inven
`tion hereof.
`FIG. 7b is a block diagram of a receiver portion of a
`concatenated System for decoding and error correcting a
`received data Stream, which System incorporates the inven
`tion hereof.
`FIG. 8 is a block diagram of the concatenated system of
`FIGS. 7a and 7b, which system incorporates a Hamming
`code and duobinary Signalling.
`FIG. 9a is a plot of input/output relationship of a quantizer
`for duobinary Signals, in a prior art threshold detector.
`FIG.9b is a plot of input/output relationship of a quantizer
`for duobinary Signals, in a prior art ambiguity Zone detector.
`FIGS. 10a and 10b are charts which illustrate four phase
`modulation with four ambiguity Zones (FIG. 10a) and with
`eight ambiguity Zones (FIG. 10b).
`FIG. 11a is a block diagram of a concatenated System
`incorporating the invention which employs three encoderS.
`FIG. 11b is a block diagram of a concatenated System
`equivalent to that shown in FIG. 11a which employs two
`encoderS.
`FIG. 11c is a block diagram of a concatenated System
`employing an iterative encoder for the equivalent two
`encoder system of FIG. 11b.
`FIG. 11d is a block diagram of a concatenated System
`employing an expanded encoder for the three encoder Sys
`tem of FIG. 11a.
`FIG. 12a is a block diagram of a concatenated System
`employing an equivalent two encoder System for the three
`encoder system of FIG. 11a.
`FIG. 12b is a block diagram of a concatenated System
`employing an iterative decoder for the equivalent two
`encoder system of FIG. 12a.
`FIG. 12c is a block diagram of a concatenated System
`employing an expanded decoder for the three encoder Sys
`tem of FIG. 11a.
`FIG. 13 is a block diagram of a concatenated System
`employing an iterative three decoder System for the three
`encoder system of FIG. 11a, with one feedback loop.
`FIG. 14a is a block diagram of a two-parallel concat
`enated System incorporating the invention.
`FIG. 14b is a block diagram of an iterative decoder for the
`two-parallel concatenated system of FIG. 14a.
`DETAILED DESCRIPTION OF THE
`INVENTION
`Iterative Decoding with Ambiguity Zone Detection (AZD)
`and Permutation
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,029.264
`
`6
`A System incorporating the invention is Schematically
`shown in FIG. 7. The transmitter side is almost the same as
`any of the concatenated Systems discussed above, except
`that a “permutation' module has been inserted, for gener
`alization purposes, (instead of the interleaver) between the
`outer and inner encoders. A carefully designed permutation
`module can improve the System more than a conventional
`interleaver, however it is to be understood that an interleaver
`is within the ambit of a permutation module and is a special
`and Simple type of permutation module. Similarly, a con
`catenated System without an interleaver (FIG. 1) also can
`embody the invention, as no interleaver is equivalent to
`insertion of an “identity permutation”. Thus, the invention
`can be applied to a large class of Systems with little or no
`modification at the transmitter Side.
`The invention places an AZD (ambiguity Zone detector)
`10 at the receiver front end 12. An AZD is a threshold
`detector (or quantizer) which assigns "erasure Symbols' to
`those digits that fall in ambiguous Zones (see the example
`described below). The output sequence from AZD 10 is then
`processed by passing it to concatenated decoderS 14 an 16
`which are connected in a loop. Between decoders 14 and 16
`is an inverse permutation module 18 (in the forward path)
`and a permutation module 20 (in the feedback path). Per
`mutation module 20 is identical to the permutation module
`used at the transmitter.
`Thus, in a first iteration after receiving a data Stream, the
`output Sequence from AZD14 is processed by inner decoder
`14, inverse permutation module 18 (which reverses the
`permutation inserted at the transmitter) and outer decoder
`16. The decoded (and error-corrected) data stream is then
`processed by permutation module 20 which re-permutes the
`data Stream to the form it had upon arrival at receiver input
`12. At the end of a first iteration, the original output
`sequence from AZD 10 is modified by an error/erasure
`corrector 22, which incorporates the corrections made in the
`first pass through the forward path. The Second iteration
`applies the modified AZD output to the above-mentioned
`receiver blocks, in the Same order as in the first iteration. The
`cyclical decoding procedure repeats.
`At each iteration, Some of the remaining errorS/erasures
`will be resolved, and error/eraSure corrector module 22
`modifies the AZD output Sequence, by use of a simple logic
`circuit (or logic table) which Substitutes Some digits of the
`AZD sequence with their corrected values. In the first
`iteration, the error/erasure corrector module 22 plays no
`role, Since the feedback loop provides no information at Such
`time. The iterative procedure ends when all erasures are
`resolved and no errors are detected, or when no new
`resolution of error/erasures are achieved, or after a pre
`scribed number of steps (as determined by logic block 24).
`At this point there are two options if the decoded Sequence
`contains Some unresolved erasures or detectable errors: (1)
`the receiver can reject the received Sequence and ask the
`transmitter for a retransmission, or (2) the receiver can make
`“hard” decisions on these digits and deliver the decoded
`result to data Sink 26. This cyclic decoding procedure is
`hereafter referred to as iterative decoding.
`If the channel contains burst errors, the original AZD
`output will contain errorSferasures in clusters, hence the
`provision of a permutation module or interleaver module is
`helpful in enabling correction of Some Such error conditions.
`However, even if the channel errors are random, i.e., not
`bursty, errorSferasures that remain unresolved after a few
`decoding cycles tend to form clusters. This is because
`isolated errorSferasures will be the first ones to disappear,
`and the remaining errors are likely to be the ones that appear
`
`Page 18 of 23
`
`

`

`7
`in a bunch. The permutation and inverse-permutation in the
`decoding loop will Separate these digits apart, hence the
`decoders in the next cycle Stage can then resolve these
`isolated errorS/erasures.
`An Illustrative Example of the Invention
`It is easiest to explain the invention by way of an example.
`A concatenated system of the type shown in FIG. 3 is shown
`in further detail in FIG. 8 which illustrates both the trans
`mission and reception sides. As the Outer code, a (7, 4)
`Hamming code is used and the inner code is duobinary
`Signaling with a precoder. An (n, k) Hamming code is a
`Single error correcting code, which can correct any Single
`error that may exist in a block of bits, consisting of message
`bits, and parity-check bits (see e.g., Lin/Costello or
`Peterson/Weldon for details on Hamming codes).
`Duobinary Signaling is often achieved by Sending a binary
`pulse Sequence at a faster rate than is possible in ordinary
`transmission (see e.g., Bergmans, or any of the aforemen
`tioned articles by Kobayashi). When the channel input is
`binary (O or 1), then the channel output, Sampled at an
`appropriate rate, should be equivalent to the Sum of the
`present and preceding digits. Thus, the output Sequence is a
`three-level Sequence, i.e., 0, 1, or 2. This three-level
`Sequence cannot take on these values independently,
`because of the nature of its construction. For example, the
`output Sequence should not have direct transitions from 0 to
`2 or Vice versa. The resultant ternary Sequence, called
`duobinary, is a Sequence with Some correlation property due
`to the channel bandwidth constraint.
`The precoder introduces a simple transformation prior to
`the transmission by duobinary Signaling. Its purpose is to
`prevent a possible error propagation in the decoded output.
`The precoder maps the input binary Sequence into another
`binary Sequence, based on the following rule: when the
`current input is 0, the output should remain in the previous
`value; and when the input is 1, the output changes its value
`from the previous one, i.e. either 0 to 1 or from 1 to 0.
`Precoding of a binary Sequence is similar to differential
`encoding usually used in DPSK (differential phase shift
`keying). Precoding for multi-level sequences is described in
`D. T. Tang and H. Kobayashi, “Error-Detecting Techniques
`for Multilevel Precoded Transmission', U.S. Pat. No. 3,622,
`986. Duobinary Signaling illustrated in this example is a
`Simplest case of partial-response channel coding referred to
`in the Background of the Art.
`Consider a simple packet transmission System in which
`there are 28 information bits in a packet, an example of
`which is given by the Stream:
`I=(0001001000110100010101100000)
`Rather than encoding the entire packet at once, it is first
`Segmented into blocks of k=4 bits, and each block is then
`encoded to a codeword of length n=7, by using a (7,4)
`Hamming code. Its parity-check and generator matrices are
`given in Systematic form by:
`
`and
`
`H =
`
`G =
`
`1.
`
`O
`1.
`O
`O
`
`1.
`1.
`
`O
`O
`1.
`O
`
`O
`1.
`
`O
`O
`O
`1.
`
`O
`
`1.
`O
`O
`O
`
`O
`
`1.
`O
`1.
`1.
`
`1.
`1.
`1.
`O
`
`O
`
`O
`1.
`1.
`1.
`
`Then the Hamming encoder output is the following 49
`bits (commas are placed between code words for clarity):
`
`5
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,029.264
`
`8
`L=(0001101, 0010111, 0011010, 0100011, 0101110, 0110100,
`0000000)
`To perform a permutation action, a 7x7 block interleaver
`(e.g.,see FIG.2b) is used which will store the above 49 bits
`row-wise in the following array Structure.
`
`3. :
`
`Then the permutation output is obtained by reading out
`the above array, column by column as follows:
`I=(0000000, 0001110, 0110010, 1010100, 1100110, 0111100,
`1101000).
`The precoder output is obtained by taking the modulo-2
`Sum of the current input and the previous output (where
`“modulo-2 Summation” can be implemented by Exclusive
`OR: 0+0=0, 0+1=1, 1+0=1, 1+1=0):
`I=(0000000, 0001011, 1011100, 1100111,0111011, 1010111,
`O11000)
`A duobinary Sequence which might be observed at the
`channel output, in the absence of noise, may be given by
`Is=(0000000, 0001112, 2112210, 121.0122, 1122112, 2111122,
`1121000)
`Because of channel noise or interference, a received (and
`Sampled) sequence will deviate from the Sequence Is. This
`noisy Sequence is passed into an ambiguity Zone detector
`(AZD), whose input and output relation is shown in FIG.9b,
`in contrast with an ordinary threshold detector shown in
`FIG. 9a. When the noise is large, the received sequence may
`fall in ambiguity Zones E or F. The AZD outputs are labeled
`as e or f, respectively. The Symbols e and f are called
`“generalized erasures”. The AZD output, therefore, has five
`levels {0, e, 1, f. 2). In actual implementation, these values
`may be represented by {0, 0.5, 1, 1.5, 2} or a three bit
`representation may be used, e.g., {(000), (001), (010), (011),
`(100)}, or any similar representation.
`In general, an AZD increases the quantization level by
`L-1, where L is the number of legitimate channel output
`levels (e.g., L=3 in the duobinary signal). This modest
`increase in the quantization level (hence one or a few
`additional bits required per digit) is advantageous to the
`conventional "Soft-decision’ quantizer which represents the
`received Sequence in Several-to-many bits per digit.
`Suppose that the AZD output is given by:
`
`I=(OOeOOee, 00ee112, f11f10, 1ffe122, 1eff112, 21ef122,
`f21e00).
`For Simplicity it is assumed that no errors are made by the
`AZD processing. In other words, the ambiguity Zones are Set
`wide enough to capture all the noisy data. The invention is
`applicable to cases where the AZD output may contain
`errors as well as erasures. Existence of errors in the AZD
`output does not affect the principle of the iterative decoding
`p