US005691992A
`5,691,992
`(11) Patent Number:
`United States Patent 1
`Molnaretal.
`[45] Date of Patent:
`Nov. 25, 1997
`
`
`[54] PUNCTURED CODING SYSTEM FOR
`PROVIDING UNEQUAL ERROR
`PROTECTIONIN A DIGITAL
`COMMUNICATION SYSTEM
`
`Kjell J. Hole, “An Algorithm for Determining If a Rate
`(n-1)/n Punctured Convolutional Encoder is Catastrophic,”
`IEEETransaction
`Communications,
`vol. 39, No. 3, Mar.
`MSACHONS ONO
`#4VOR
`9)
`NO.
`2)
`MEL
`1991.
`
`[75]
`
`Inventors: Barbara Davis Molnar, Stanley Lynn
`Reinhold; Amer Aref Hassan, ail of
`Cary, N.C.
`
`{73] Assignee: Ericsson Inc., Research Triangle Park,
`N.C.
`:
`
`(21] Appl. No.: 542,276
`[22] Filed:
`Oct. 12, 1995
`E51]
`Tint, C19 ncecssssesssssnseennantenssneeeuneseenenn H03M 13/00
`[52] U.S. C1.eecsssesssssssssesasecessesansssosesnssneessonresanes 371/37.1
`
`[58] Field of Search ...........:cccececsece 371/43, 37.1, 30
`[56]
`References Cited
`U.S. PATENT DOCUMENTS
`
`3/1992 Cameron ........-sesssscssressereeeees 371/37.1
`5,099,482
`
`3/1993 Halbert-Lassaleet al.
`............ 370/204
`5,197,061
`.sscsssssssns 375/261
`4/1994 Calderbank et al.
`5,305,352
`REI
`FOREIGN PATENT DOCUMENTS
`11/1995 European Pat. Off. .
`0676875
`OTHER PUBLICATIONS
`Yutaka Yasuda, Kanshiro Kashiki and Yasuo. Hirata,
`“High—Rate Punctured Convolutional Codes for Soft Deci-
`sion Viterbi Decoding,” JEEE Transactions on Communi-
`cations, vol. Com-32, No. 3, Mar. 1984.
`
`Primary Examiner—Stephen M.Baker
`Attomey, Agent, or Firm—David G. Matthews
`
`[57]
`
`ABSTRACT
`
`A coding system for error protecting both insignificant and
`significant symbols of a digital message to be transmitted
`from a transmitter to a receiver of a digital system. Error
`protection for both insignificant and significant symbols is
`provided by coding at the transmitter both significant and
`insignificant symbols of message blocks forming the digital
`message. The symbol rate of the coded signal to be trans-
`mitted is reduced and unequal error protection is provided to
`the significant symbols by puncturing a selected number of
`insignificant symbols of each codewordof the coded signal.
`At th
`:
`ion
`de
`tae
`gs
`de f
`h
`t
`the receiver, a correction
`determination is made
`for eac’
`received codeword as to whether the erasures and errors of
`the received codeword are correctable. The correction deter-
`mination is a function of the number of exrors, number of
`erasures, and the minimum distance of the code. Based on
`us netswe the received codeword is
`epunctured and
`decoded.
`
`21 Claims, 6 Drawing Sheets
`
`peewee en
`
`ees
`
`ae
`
`Estimated Message
`
`IPR2018-1556
`HTC EX1019, Page 1
`
`IPR2018-1556
`HTC EX1019, Page 1
`
`

`

`U.S. Patent
`
`Nov. 25, 1997
`
`Sheet 1 of 6
`
`5,691,992
`
`wee weew aw ew ow = 7
`
`|
`
`
`
`saleteteteteaetael -| Digital Message !
`
`
`Channel
`TTT TTTTa
`
`Encoder|“°\__#7777777 77+ Coded Signal |
`20
`Rane oem ee ce ce ces ee oe ee ee oe
`12
`pooaeenn----- 1
`enn ences : Punctured Signal|
`8
`
`eeeeet
`
`22
`
`PTT Tee 7
`a ealaleaaeiieiaia | Modulated Signal
`
`Na cm ce mee ee en ome oe mee ee
`
`44
`
`| Received |
`NN eee i Modulated Signal|
`
`------------ '
`
`
`
`Channel|..———SifGuh57+ -------
`
`|!
`eee |; Demodulated
`!
`Signal
`;
`oe | Depunctured
`L___ Signal ___
`
`Decoder
`32
`
`Estimated Message
`
`FIG.1
`
`IPR2018-1556
`HTC EX1019, Page 2
`
`IPR2018-1556
`HTC EX1019, Page 2
`
`

`

`US. Patent
`
`Nov. 25, 1997
`
`Sheet 2 of 6
`
`5,691,992
`
`34\
`
`DEMODULATED
`SIGNAL
`
`42
`
`
`CORRECTION
`
`
`DETERMINATION
`CODEWORD
`
`DEPUNC-
`CIRCUIT
`CORRECTION
`
`
`
`CIRCUIT
`U
`
`
`CALCULATOR
`
`ERROR
`COMPARATOR
`
`48
`
`
`
`
`
`
`
`
`MEMORY
`
`44
`
`FIG. 2
`
`IPR2018-1556
`HTC EX1019, Page 3
`
`IPR2018-1556
`HTC EX1019, Page 3
`
`

`

`US. Patent
`
`Nov. 25, 1997
`
`Sheet 3 of 6
`
`5,691,992
`
`INPUT DIGITAL
`MESSAGE
`
`CODEDIGITAL
`MESSAGE TO PRODUCE
`CODED SIGNAL
`
`
`
`50
`
`52
`
`PUNCTUREt
`INSIGNIFICANT SYMBOLS|_%4
`IN EACH CODEWORD
`
`MODULATE PUNCTURED|56
`SIGNAL
`
`TRANSMIT MODULATED
`SIGNAL OVER CHANNEL
`
`DEMODULATE RECEIVED
`MODULATED SIGNAL
`
`38
`
`60
`
`(a)
`
`FIG. 3a
`
`IPR2018-1556
`HTC EX1019, Page 4
`
`IPR2018-1556
`HTC EX1019, Page 4
`
`

`

`US. Patent
`
`Nov. 25, 1997
`
`Sheet 4 of 6
`
`5,691,992
`
`
`
`
`
`DETERMINE
`NUMBER OF
`SYMBOL ERRORS
`FOR CODEWORD
`
`SUBSTITUTE
`SYMBOLS
`
`
`
` FILL ERASURES WITH
`
`
`
`
`
`DECODE NON-
`OUTPUT NON-
`_ CORRECTED
`
`CORRECTED
`
`
`No
`DEPUNCTURED
`
`
`
`MESSAGE
`
`CODEWORD
`BLOCK
`
`
`
`
`
`CORRECT
`ERROR
`
`SYMBOLS AND |-———
`ERASURES
`
` DECODE
`
`
`CORRECTED
`
`DEPUNCTURED
`CODEWORD
` FIG. 3b
`
`OUTPUT
`
`CORRECTED
`
`MESSAGE
`BLOCK
`
`
`
`56
`
`58
`
`60
`
`
`
`IPR2018-1556
`HTC EX1019, Page 5
`
`IPR2018-1556
`HTC EX1019, Page 5
`
`

`

`eyol
`
`U.S. Patent
`
`Nov. 25, 1997
`
`Sheet 5 of 6
`
`5,691,992
`
`eecS
`
`
`AouepunpesqueoljiuBisjueoyiuBbisuyAouepunpesjuBolpUBISyueotpuBisul
`
`
`
`
`
`
`
`
`sjoqwAssjoquwAssjoquiAssjOquiAssjoquwAssjoquiAs
`[uzsotBZBHIK[tionPoOHDeyIVNDIS
`[yy|*Elyty,Hy|“avuioiaFA43018
`ne,et,te,1,reare
`
`
`
`
`
`ANvVSSAWGNOOASYNOO18ADVSSAW1Suyl4
`queoyiuBisjueoljiuBisu!jueoiiuBis=jueoyuBisur
`
`
`
`sjoquiAssjoquiAssjoquiAssjoquiAs
`
`
`
`
`
`q7Sd
`
`°FOS
`
`GayuNLONnd
`
`IPR2018-1556
`HTC EX1019, Page 6
`
`IPR2018-1556
`HTC EX1019, Page 6
`
`

`

`U.S. Patent
`
`Nov. 25, 1997
`
`Sheet 6 of 6
`
`5,691,992
`
`E2
`
`O
`
`ul
`
`O
`
`GaYHNLONNd
`
`GaAIa03u
`
`TWNODIS
`
`
`
`(ingino7aNNVHO
`
`AWNOIS
`
`€Za2OOve
`
`GSYNLONNdAG
`
`TWNDIS
`
`€222
`
`an)
`
`LZ
`
`3
`
`-UL9
`
`Ga1VWIisa
`
`qovssan
`
`IPR2018-1556
`HTC EX1019, Page 7
`
`IPR2018-1556
`HTC EX1019, Page 7
`
`

`

`5,691,992
`
`1
`PUNCTURED CODING SYSTEM FOR
`PROVIDING UNEQUAL ERROR
`PROTECTIONIN A DIGITAL
`COMMUNICATION SYSTEM
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to a punctured
`coding system for a digital communication system, and
`moreparticularly, a punctured coding system for providing
`unequal error protection for selected symbols in a digital
`message.
`
`BACKGROUND OF THE INVENTION
`
`Digital communication systems convey a digital message
`by transmitting a symbol stream from a transmitter to a
`receiver over a transmission channel. Transmission channels
`often contain noise that tends to corrupt the transmitted
`symbol stream, resulting in transmission errors and the loss
`of part of the transmitted digital message. Corruption of the
`transmitted symbol stream is a particular problem for wire-
`less transmission channels due to the high level of noise in
`wireless transmission channels.
`To minimize the impact of noise on the digital message
`being transmitted, various different coding techniques,often
`referred to as forward error correction (FEC) techniques, can
`be used to code the digital message. Representative FEC
`techniques for coding a digital message include BCH codes,
`cyclic codes, Hamming codes, Reed-Solomon codes, and
`Golay codes. One reference discussing FEC techniques is
`Shu Lin and Daniel Costello, Error Control Coding: Fun-
`damentals & Applications, Prentice Hall, which is incorpo-
`tated by reference. When properly designed, coding the
`digital message with FEC techniques improvesthe quality of
`the digital message received at the receiver.
`One problem with coding digital messages is that an
`increased number of symbols are used to represent the
`digital message, and accordingly, the symbol rate of the
`symbol stream being transmitted overthe transmission chan-
`nel must also increase. When the symbol rate increases, the
`amount of bandwidth required to transmit the symbol stream
`representingthe digital message also increases. The require-
`mentof increased bandwidth to transmit the digital message
`can be a problem because of the limited amount of band-
`width available and the high expense of using bandwidth.
`Accordingly, the benefits of coding digital messages is at
`least partially offset by the disadvantage of the need for
`increased bandwidth to transmit the coded message.
`Theproblem of increasing the bandwidth requirement by
`coding has been addressed in the prior art by only coding
`selected significant symbols of the digital message to be
`transmitted. These partial coding systems.take advantage of
`the fact that digital messages often include significant sym-
`bols and insignificant symbols. The significant symbols
`represent the more essential information of the digital mes-
`sage and the insignificant symbols representrelatively less
`essential information. Partial coding systems code the sig-
`nificant symbols and leave the insignificant symbols
`uncoded. Accordingly, partial coding schemes help protect
`the significant symbols from transmission errors and leave
`the insignificant symbols less protected. Partial coding
`schemesare used where increases in bandwidth necessitated
`by coding is only deemed worthwhile for the significant
`symbols. This results in unequal error protection for the
`digital message where the significant symbols are protected
`andthe insignificant symbols are unprotected. Because the
`insignificant symbols are unprotected, any transmission
`
`2
`errors affecting the insignificant symbols corrupt,at least to
`some degree, the quality of the received digital message.
`SUMMARYOF THE INVENTION
`
`The present invention is a coding system for error pro-
`tecting both insignificant and significant symbols of a digital
`messageto be transmitted from a transmitter to a receiver of
`a digital system. Error protection for both insignificant and
`significant symbols is provided by coding both significant
`and insignificant symbols of message blocks forming the
`digital message. The symbol rate of the coded signal to be
`transmitted is reduced and unequal error protection is pro-
`vided to the significant symbols by puncturing a selected
`number of insignificant symbols of each codeword of the
`coded signal. At the receiver, a correction determination is
`madefor each received codeword as to whether the erasures
`and errors of the received codeword are correctable. The
`correction. determination is a function of the number of
`errors, number of erasures, and the minimum distance ofthe
`code. Based on this correction determination, the received
`codeword is depunctured and decoded.
`A digital communication system according to the present
`invention includes a coding circuit, a puncturing circuit, a
`depuncturing circuit, and a decoding circuit. The coding
`circuit codes a digital message according to a predetermined
`code prior to transmission to produce codewords having
`significant message symbols,
`insignificant message
`symbols, and redundancy symbols. The redundancy sym-
`bols error protect both the significant and insignificant
`message symbols. The puncturing circuit punctures Tt insig-
`nificant symbols of each codeword prior to transmission so
`as to produce erasures in the codewords. The punctured
`codewords are then transmitted from the transmitter to the
`receiver over the communication channel.
`A depuncturing circuit in the receiver depunctures the
`received punctured codewords to produce depunctured
`codewords. The depuncturing circuit determines for each
`received punctured codeword if the punctured codewordis
`correctable.If the codeword is determined to be correctable,
`the punctured codewordis corrected and a corrected depunc-
`tured codeword is generated. If the punctured codeword is
`determinedto be non-correctable, the punctured codeword is
`not corrected and a non-corrected depunctured codeword is
`generated.
`The depunctured codewords are decoded by the decoding
`circuit to produce received message symbols. The received
`message blocks generated from the corrected depunctured
`codewordsare equivalentto their corresponding transmitted
`message blocks, while the received message blocks gener-
`ated from the non-corrected depunctured codewordsinclude
`errors.
`
`10
`
`15
`
`20
`
`30
`
`35
`
`45
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of the digital communication
`system according to the present invention.
`FIG. 2 is a block diagram of a depuncturing circuit
`according to the present invention.
`FIGS.3a and 3b are a flow chart showing operational
`steps of the digital communication system according to the
`present invention.
`FIGS. 4a-4f show an example digital message being
`coded and decoded according to the present invention.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`55
`
`65
`
`The present invention is a punctured coding system for
`providing error protection for a digital message to be trans-
`
`IPR2018-1556
`HTC EX1019, Page 8
`
`IPR2018-1556
`HTC EX1019, Page 8
`
`

`

`5,691,992
`
`3
`mitted over a communication channel. The present invention
`punctured coding system is designed to be implemented in
`a digital communication system where the transmitted digi-
`tal message may be corrupted by noise in the communica-
`tion channel. Such communication systems include radio
`communication systems such as land-based cellular systems
`and satellite-based cellular systems.
`Referring to FIG. 1, a general schematic of a digital
`communication system 10 in which the punctured coding
`system of the present invention can be implemented is
`shown. The digital communication system 10 includes a
`transmitter 12 for coding and transmitting a digital message,
`and a receiver 14 for receiving and decoding the received
`digital message. The transmitter 12 and receiver 14 include
`communication components, described below, which are
`selected, arranged, and configured to implement the punc-
`tured coding system of the present invention.
`Transmitter 12 includes an information source 16, channel
`encoder 20, and modulator 22. The information source 16
`generatesa digital message formed by a stream of message
`blocks containing significant and insignificant symbols. In
`one preferred embodiment, the information source 16 is a
`vocoder such as a VCELP (or CELP) vocoder. Such a
`vocoder generates a stream of message blocks having sig-
`nificant and insignificant symbols representing speech, and
`is used in the GSM standard used widely in Europe. The
`channel encoder 20 has a coding circuit 24 for coding the
`digital message to form a coded signal formed by codewords
`and a puncturing circuit 26 for puncturing the codewords to
`produce a punctured signal. The digital message is coded
`according to a selected code to provide error protection for
`both the significant and insignificant symbols of the digital
`message. Each codeword is punctured according to a
`selected puncture deleting pattern to produce a correspond-
`ing punctured codeword having erasures. Modulator 22 uses
`the punctured signal to produce a modulated signal whichis
`transmitted over the communication channel.
`The receiver 14 includes a demodulator 30 and channel
`decoder 32 for receiving and decoding the received modu-
`lated signal. The received modulated signal is a function of
`the noise in the channel and can be referred to as a channel
`output signal. The demodulator 32 demodulates the channel
`outputsignal to produce a demodulated signal. The demodu-
`lated signal correspondsto the transmitted punctured signal
`after it has been corrupted by the noise in the communication
`channel. The channel decoder 32 includes a depuncturing
`circuit 34 for depuncturing the demodulated signal and a
`decodingcircuit 36 for decoding the depunctured signal. The
`depuncturing circuit 34 uses the deleting pattern of the
`puncturing circuit 26 to depuncture the demodulated signal,
`and the decoding circuit 36 uses the code of the coding
`circuit 24 to decode the depunctured signal. Channel
`encoder 20 and the channel decoder 32, as well as the
`channel encoder 20, can be implemented using conventional
`microprocessors currently used in radio communication
`systems.
`A schematic of depuncturing circuit 34 is shown in FIG.
`2. The depuncturing circuit 34 generally includes a correc-
`tion determination circuit 40, a codeword correction circuit
`42 and a memory 44. Correction determination circuit 40
`includes an error calculator 46 and error comparator 48, and
`functions to determine whether each codeword is correct-
`able. A correctable codeword is a codeword for which all
`error symbols in the codeword and erasures can be cor-
`rected.
`
`To determine whether a codewordis correctable, the error
`calculator 46 determines the number of error symbols for
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`35
`
`65
`
`4
`each codeword. The numberof error symbols is outputted to
`the error comparator 48 which compares the number oferror
`symbols in the received codeword caused by the transmis-
`sion to a predetermined maximum threshold. The predeter-
`mined maximum threshold is a function of the minimum
`distance of the code and number of erasures. The predeter-
`mined maximum threshold is stored in memory 44 and
`outputted to the correction determination circuit 40 for use
`in determining whether each codewordis correctable. If the
`number of error symbols is less than the predetermined
`maximum threshold for a given codeword, then the error
`comparator 48 outputs a correctable determination signal to
`the codeword correction circuit 42. If the number of error
`symbols is more than the predetermined maximum threshold
`for a given codeword, then the error comparator 48 outputs
`a noncorrectable determination signal to the codeword cor-
`rection circuit 42.
`The codeword correction circuit 42 corrects errors and
`erasures in a received codeword in response to a correctable
`determination signal, and outputs a corrected depunctured
`codeword. Errors and erasures are corrected in the codeword
`by using bounded distance decoding algorithms (such as the
`Berlekamp-Massey algorithm). A corrected depunctured
`codeword is a codeword where errors and erasures are
`corrected, In the preferred embodiment, all errors and era-
`sures in the received codeword are corrected in response to
`the correctable determination signal. When a noncorrectable
`determination signal for a codeword is input into the code-
`word correction circuit 42, errors and erasures in the code-
`word cannot be corrected. In this case, the codeword cor-
`rection circuit 42 fills the erasures with arbitrary or
`correlated symbols, and outputs a noncorrected depunctured
`codeword.
`The corrected and noncorrected depunctured. codewords
`form the depunctured signal which is output to decoding
`circuit 36 for decoding. The decoding circuit 36 decodes the
`depunctured signal and outputs an estimated message
`formed by corrected message blocks and noncorrected mes-
`sage blocks.
`A flowchart describing the overall operation of digital
`communication system 10 and the unequal error protection
`provided by channel encoder 20 and channel decoder 32 is
`shownin FIGS. 3a and 3b. Referring to FIG. 3, a digital
`message is first outputted by information source 16 to
`channel encoder 20 (step 50). The digital message is a
`stream of message blocks with each message block includ-
`ing a plurality of message symbols. The message symbols of
`each message block are arranged in a known symbolpattern
`of significant symbols and insignificant symbols.
`The coded signal is outputted to the coding circuit 24 and
`the digital message is coded to produce a coded signal
`formed by successive codewords (step 52). Each codeword
`corresponds to one of the message blocks. In the preferred
`embodiment, the coded signal
`is coded according to a
`systematic code (or any encoding scheme where message
`symbols can be placed in specified coordinates in a
`codeword). Systematically coding the digital message
`results in a message block of k symbols being represented by
`a codeword of n symbols, where n is great than k. Each
`codeword has the k message symbols of the corresponding
`message block and n-k redundancy symbols. The k message
`symbols are arranged in a known symbolpattern of signifi-
`cant symbols and insignificant symbols. The redundancy
`symbols provide error protection for both the significant and
`insignificant message symbols.
`The coded signal is outputted to the puncturing circuit 26
`and 7 insignificant symbols of each codeword are punctured
`
`IPR2018-1556
`HTC EX1019, Page 9
`
`IPR2018-1556
`HTC EX1019, Page 9
`
`

`

`5,691,992
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`5
`according to a deleting pattern to produce a punctured signal
`(step 54). The punctured signal is formed by codewords
`having t erasures. The deleting pattern to puncture the
`codewords is selected to puncture t insignificant symbols,
`where t equals a selected number of the insignificant sym-
`bols. The number of 1 insignificant symbols chosen to be
`punctured depends on factors such as the length of the
`codewords n, the desired bit rate of the code, and the
`anticipated amount of noise in the channel. The deleting
`pattern is selected based on the symbol pattern dictating
`which code symbols are insignificant symbols and which
`code symbols are significant symbols. The punctured sym-
`bol is then outputted to modulator 22 which generates a
`modulated signal corresponding to the punctured signal
`(step 56). The modulated signal is then transmitted over a
`communication channel (step 58).
`Demodulator 30 of receiver 14 receives a channel output
`signal which is the modulated signal after it has been
`modified by the channel (step 60). The demodulator 30
`demodulates the channel outputsignal to produce a demodu-
`lated signal or received punctured signal. The received
`punctured signal is formed by received punctured code-
`words. Because of noise in the channel, errors tend to be
`introduced into the symbols of the received punctured
`codewords. Symbols in error in the received punctured
`codewords are referred to as error symbols.
`Thereceived punctured signal is outputted to depunctur-
`ing circuit 34 where each codeword of the received punc-
`tured signal is successively processed codeword by code-
`word as follows.First, a received codeword is processed by
`error calculator 46 of correction determination circuit 40 to
`determine the numberof error symbols e, in the received
`codeword (step 62). Methods for determining the number of
`error symbols e, in a received codeword are known in the
`prior art and can be determined in the preferred embodiment
`by bounded distance decoding. The number of determined
`error symbols e, is then outputted to error comparator 48
`which compares the numberof error symbols e, to a stored
`maximum error threshold e, (step 54). When using bounded
`distance decoding, the error calculator 46 can calculate the
`actual number of error symbols up to the maximum error
`threshold e,. For received codewords having a number of
`error symbols greater than the maximum error thresholdet,
`error calculator 46 determines that the number of error
`symbols is some number greater than the maximum error
`threshold e,. Accordingly, error calculator 46 can determine
`that the number of error symbols e, equals any of the
`following: 1,2, .. . ,¢,>¢,.
`In the preferred embodiment, the stored maximum error
`threshold e, is stored in memory 44 andis derived according
`to a maximum error threshold equation:
`
`6
`If the number of error symbols e, is less than or equal to
`the maximum error threshold e, then error symbols and
`erasures are corrected to produce a corrected depunctured
`codeword(step 56). In the preferred embodiment, all of the
`e, error symbols and 7 erasures are corrected by processing
`the codeword using bounded distance decoding algorithms.
`In alternative embodiments, substantially all of the e, error
`symbols are t erasures are corrected by processing the
`codeword using bounded distance decoding algorithms. The
`corrected depunctured codeword is outputted to the decod-
`ing circuit 36 and the corrected depunctured codeword is
`decoded by decoding circuit 36 (step 60). The decoding
`circuit 36 outputs an error corrected. message block formed
`by message symbols that are equivalent to the message
`symbols of the corresponding message block transmitted
`from transmitter 12.
`If the number of error symbols e, is greater then the
`maximum error threshold e, then the codeword is uncor-
`rectable. When the codeword is uncorrectable, substitute
`symbols are generated and used to fill in the punctured
`symbol (step 58) and the symbol errors are not corrected.
`The substitute symbols can be arbitrary symbols or can be
`generated through correlation techniques such as interpola-
`tion of message symbols. The non-corrected depunctured
`codeword is then output to decoding circuit 36 which
`decodes the depunctured codeword (step 64). In the pre-
`ferred embodiments, the non-corrected depunctured code-
`word is decoded by outputting the symbols of the depunc-
`tured codeword corresponding to the coordinates of the
`Message symbols in the transmitted message block. For
`instance, the first k symbols of the depunctured codeword
`(with substitute symbols) is outputted when systematic
`coding is used. Because the codeword was uncorrectable,
`the decoding circuit 36 outputs a non-corrected message
`block (step 66). The non-corrected message block includes
`message symbols that are not equivalent to the message
`symbols of the corresponding transmitted message block.
`Referring to FIG. 4 a schematic representation of an
`example digital message being transmitted from transmitter
`12 and received by receiver 14 is shown. The digital
`messageis processed in transmitter 12 and receiver 14 on a
`block-by-block basis. The digital message is formed by a
`plurality of successive message blocks of k symbols.A first
`message block having symbols i,, to i,, and a second
`message block having symbols i,, to i,, is shown in FIG. 4a.
`The first two symbols of each message block are designated
`as insignificant symbols and the remaining symbols are
`designated as significant symbols. As shown in FIG.4a, in
`the first message block symbols i,, to i,, are insignificant
`and symbols i,, toi,, are significant. Likewise, in the second
`message block symbols i,, and i,. are insignificant symbols
`and symbols i,, to i,, are significant.
`Thefirst and second message blocks are coded by coding
`circuit 24 to produce a first codeword corresponding to the
`first message block and a second codeword corresponding to
`55
`where 4d,,;, is the minimum distance of the code, t is the
`the second message block. Each codeword is formed by
`
`number of erasures, and|_|designates a floor function such
`Message symbols (i.e., insignificant and significant symbols)
`that e, equals the largest integer smaller than
`and redundancy symbols. As shown in FIG. 48, in the first
`codeword symbol c,, and c,, are insignificant symbols, c,,
`to c,, are significant symbols and c,4,1) to c., are redun-
`dancy symbols. Likewise, in the second codeword symbols
`C2, and c,, are insignificant symbols, c,, to c,, are signifi-
`cant symbols, and C2,,1) t0 C2, are redundancy symbols.
`The first and second codewords are successively punc-
`tured by puncturing circuit 26 such that insignificant sym-
`bols c,, and c,, of the first codeword are punctured and
`insignificant symbols c,, and c,, of the second codeword are
`punctured. The punctured symbols of the codeword are
`
`min —1~-T
`«=| —z—_],
`
`amin - 1-7
`2
`
`The maximum error threshold e, is the maximum number of
`errors at which the t erasures and the e, error symbols can
`be corrected. In the preferred embodiment, a receiver code-
`word is correctable if each of the e, error symbols in the
`codeword can be corrected and the 1 erasures can be
`corrected.
`
`65
`
`IPR2018-1556
`HTC EX1019, Page 10
`
`IPR2018-1556
`HTC EX1019, Page 10
`
`

`

`5,691,992
`
`10
`
`20
`
`30
`
`35
`
`7
`8
`shown crossed out in FIG. 4c. The punctured signal is
`drawings, without departing from the substance or scope of
`modulated and is transmitted to receiver 14.
`the invention. While the present
`invention has been
`Receiver 14 includes a demodulator 30 which demodu-
`described herein in detail
`in relation to its preferred
`embodiments, it is to be understood that this disclosure is
`lates the received modulated signal and outputs a received
`only illustrative and exemplary of the present invention and
`punctured signal or channel output signal. As shownin FIG.
`is merely for purposes of providing a full and enabling
`4d, the received punctured signal includes a first received
`disclosure of the invention. Accordingly, it is intended that
`codeword having symbols 0,, to 0,,, and a second received
`the invention be limited only by the spirit and scope of the
`codeword having symbols 0,, to 0,,,.. If no errors have been
`claims appended hereto.
`introduced during transmission, then symbols 0,, to 0,, of
`Whatis claimedis:
`the first received codeword equals symbols c,, to c,,, of the
`1. A coding methodfor error protecting a digital message
`transmitted first punctured Codeword, and symbols 0,, to
`to be transmitted from a transmitter to a receiver over a
`0.,, of the second received codeword equals symbols c,, to
`channel, comprising:
`C2, of the transmitted second punctured codeword.
`a) coding the digital message according to a predeter-
`As shown in FIG. 4e, the received punctured. signal is
`mined codeprior to transmission to produce codewords
`15
`depunctured by depuncturing circuit 34 to produceafirst
`having significant message symbols, insignificant mes-
`depunctured codeword 6,, to 6,,, and a second depunctured
`sage symbols, and redundancy symbols, wherein the
`codeword 6,, to 6,,. Assuming that the first received code-
`redundancy symbols error protect both the significant
`word was correctable, then errors and erasures are corrected
`and insignificant message symbols;
`in the received codeword and symbols 6,, to 6,,, of the first
`b) puncturing 7 insignificant symbols of each codeword
`depunctured codeword equals symbols c,, to c,, of the
`prior to transmission so as to produce erasures in the
`pre-transmission coded signal. Assuming that the second
`codewords;
`received codeword was not correctable, then the errors and
`c) depuncturing the punctured codewords after transmis-
`erasures are not correctablein the received second codeword
`sion to produce depunctured codewords, the step of
`and symbols 6,, to 6,,, of the second depunctured codeword
`depuncturing received punctured codewords including:
`will contain errors. Accordingly, the symbols of 6,, to 6.,, of
`1) determining for each received punctured codewordif
`the second depunctured codeword does not equal symbolc,,
`the punctured codeword is correctable, and
`to c,,, of the corresponding pre-transmission codeword.
`2) correcting the punctured codewords determined to
`The first and second depunctured codewords are decoded
`be correctable so as to produce corrected depunc-
`by decoding circuit 36, and a first estimated message block
`tured codewords;
`and a second estimated message block is outputted from
`d) decoding the depunctured codewords.
`decoding circuit 36. As shown in FIG.4f thefirst estimated
`2. The coding method of claim 1, wherein when a
`message block includes symbols ¢,, to e,, and the second
`received punctured codeword is determined to be correct-
`estimated message block includes symbols e,, to e.,. The
`able the erasures in the received punctured codeword are
`quality of an estimated message block depends on whether
`filled with the corresponding t punctured symbols and error
`the corresponding received codeword was correctable. For
`symbols are corrected such that the message symbols of the
`example,if the first message block was correctable, symbols
`corrected depunctured codeword is equivalent to the mes-
`€,,
`toe,, equal symbolsi,, to i,, Of the first message block,
`sage symbols of the corresponding transmitted codeword,
`and the first estimated message block is not impaired. As a
`and whena received punctured codeword is determined not
`second example, assumethat the second received codeword
`to be correctable the erasures in the received punctured
`was not correctable. If the second received codeword was
`codeword are filled with substitute symbols and errors are
`not correctable, the symbols e,, to e, do not equal the
`not corrected such that the message symbols of the non-
`symbolsi,, to i,, of the second message block. Accordingly,
`corrected depunctured codeword is not equivalent to the
`the second estimated message block will include some
`message symbols of the corresponding transmitted code-
`impairmentto the quality of the second estimated message
`word,
`block. Although the second estimated message block will
`3. The coding method of claim 1, wherein the predeter-
`include a certain numberof errors, the significant symbols
`mined code is a systematic code.
`are less likely to be in error compared to the insignificant
`4. The coding method of claim 1, wherein the step of
`symbols because only insignificant symbols are punctured.
`determining if the punctured codeword is correctable
`In summary, the coding system of the present invention
`includes determining the number of error symbols e, in the
`codes a digital message to provide error protection for both
`codeword.
`insignificant and significant symbols of a digital message.
`5. The coding method of claim 4, wherein the step of
`Unequal error protection is provided to the significant sym-
`determining if the punctured codeword is correctable is a
`bols by puncturing only 7 insignificant symbols. The punc-
`function of the number of error symbols e,, the number of 7
`tured signal is transmitted to a receiver where the received
`erasures, and the minimum distance d,,,, of the predeter-
`signal is processed to determine if the erasure