United States Patent [191
`Fazel et al.
`
`llllllllllllllIIIllllllllll|||||lllllllllllllllIlllllllllllllllllllllllllll
`5,218,622
`Jun. 8, 1993
`
`USOO5218622A
`[11] Patent Number:
`[45] Date ‘of Patent:
`
`[54] SYSTEM OF ENCODING DIGITAL SIGNALS
`INTENDED FOR TRANSMISSION AND/OR
`STORAGE AND A CORRESPONDING
`DECODING SYSTEM
`[75] Inventors: Khaled Fazel, Vincennes;
`Jean-Jacques Lhuillier, Saint-Maur,
`both of France
`[73] Assignee: U.S. Philips Corporation, New York,
`NY.
`[21] App]. No.: 630,700
`[22] Filed:
`Dec. 20, 1990
`[30]
`Foreign Application Priority Data
`Dec.29, 1989 [FR] France .............................. .. 8917452
`
`Feb. 16, 1990 [FR] France . . . . . .
`
`. . . . . . . . .. 90 0189]
`
`. . . . . . . . .. 90 03406
`Mar. 16, 1990 [FR] France . . . . . .
`HMN 11/02
`[51] Int‘ cl; _______
`_
`_
`[52] U.S. c1. ........II.II.I:III:117555/122- ass/13s
`’ 371/371’
`[58] Field of Search ................... .. 375/25, 31, 34, 122;
`358/133, 138, 426, 427, 430; 341/65, 67;
`371/311, 41
`
`[56]
`
`_
`References Cited
`_
`U.S. PATENT DOCUMENTS
`4,633,483 12/1986 Takahashietal. ................ .. 375/122
`4,782,387 11/1988 Sabri et al. .................... .. 358/138
`4,939,583 7/1990 Tsuboi et a1. ..................... .. 358/427
`
`4,982,282 1/1991 Saito et a1. ........................ .. 375/122
`Primary Examiner-Benedict V. Safourek
`Attorney, Agent, or Firm-Michael E. Marion
`[57]
`ABSTRACT
`A system of encoding digital signals comprising a
`source encoder followed by a transmission channel
`encoder, which is characterized in'that in the case in
`which the source encoder is a variable-length encoding
`circuit (10), the channel encoder comprises a series
`arrangement of a sub-assembly of encoding with selec
`tive protection and a sub-assembly of encoding without
`selective protection. The signals being arranged in in
`formation component blocks. The system includes a
`stage for encoding lengths of blocks for determining
`along the block an accumulated length of code words
`
`supplied by said source encoder and ensuring the en
`coding of block lengths thus determined, a stage for
`selective P‘°‘e°‘i°“ “said blocks and a Stage f°r mum‘
`plexing the signals supplied by said length encoding and
`Selcctive Protwion 5mg“- The cmespmlding deemi
`ing system comprises a transmission channel decoder
`followed by a source decoder, the channel decoder
`comprising a series arrangement of a sub-assembly for
`decoding with non-selective protection and a sub
`assembly for decoding with 11 levels of selective protec
`15°“
`
`12 Claims, 4 Drawing Sheets
`
`20
`
`10
`/
`
`f' """"""""""""""""""""""" "I
`1
`'
`BLOCK ~100
`1
`
`1
`
`l
`
`l_\
`200
`
`5
`—4-' ekilléll'e
`:
`__,_
`;
`VAHIABLE-
`;
`H LENGTH _;_i l 300 —~-- MULTIPLEXER —~ BUFFER
`1
`ENCODING E03.
`—+--
`:
`C'RCU'T
`.
`SELECTIVE
`/
`/
`I
`l
`1
`-—-—|-i PR%II'_EA%TEION
`I
`I
`I
`'
`:
`l
`301
`302
`I
`:
`V
`400
`1 CHANNEL ENCODER
`I
`"W --------- --: \\ NON-SELECTNE :
`.
`. ENCODING
`:
`;
`ASSEMBLY
`.
`‘
`I
`I
`'
`t
`
`Apple Inc. Exhibit 1005 Page 1
`
`

`
`US. Patent
`
`June 8, 1993
`
`Sheet 1 of 4
`
`5,218,622
`
`FIG. 1
`PRIOR ART
`
`SOURCE __,o
`CHANNEL
`CHANNEL
`SOURCE
`H ENCODER _' ENCODER “’ CHANNEL ‘* DECODER _’ DECODER
`\
`1
`J
`/
`/
`
`10
`/
`
`l
`
`r """""""""""""""""""""" "g
`'
`BLOCK R100
`:
`'
`LENGTH
`:
`i ' ENSPTQE'E‘G
`g
`:
`i
`VARIABLE-
`LENGTH
`'
`H ENCODING EOB|
`5
`SELECTIVE
`CIRCUIT
`:
`:
`—+~ PREGEEON
`=
`\ 200
`i
`i
`v
`400
`: CHANNEL ENCODER
`;
`'-* --------------------- --| \\ NON-SELECTIVE
`:
`:
`ENCODING
`E;
`:
`ASSEMBLY
`:
`l
`'
`i
`
`MULTIPLEXING STAGE
`
`_>_
`300 w MULTIPLEXER -> BUFFER
`—*‘
`/
`/
`I
`/
`301
`302
`
`Apple Inc. Exhibit 1005 Page 2
`
`

`
`U.S. Patent
`
`Jfine s, 1993
`
`592139522
`
`BIT
`coumme
`Cmcun
`
`‘
`
`LENGTH
`ENCODING
`CIRCUIT
`
`BLOCK
`COUNTING
`
`CIRCUIT I
`
`I
`
`BLOKH-ZYABLOV
`ENCODER
`
`SELECTIVE
`ENCODING
`CIRCUIT
`
`SELECTIVE
`ENCODING
`CIRCUIT
`
`SELECTNE
`ENCODING
`CIRCUIT
`
`SELECTIVE
`ENCODING
`CIRCUIT
`
`DEMULTI-
`PLEXING
`CIRCUIT
`
`MEMORY
`
`MATRIX
`MULITPUCATION
`CIRCUIT
`
`Apple Inc. Exhibit 1005 Page 3
`
`

`
`U-S. Patent
`
`June 8, 1993
`
`Sheet 3 of 4
`
`502
`
`?Ein?fTiielniés'rieFy'fm""m'mm'm
`"30
`FIG. 6
`
`rm. 7 l
`
`l___--_-__
`DEMULTIPLEXI
`__
`400 "g
`STAGE
`
`'
`
`:
`
`l
`I
`
`:
`;
`i
`:
`i
`
`LENGTH
`DECODING —-> MEMORY
`cmcurr
`4
`
`.
`
`I
`l
`
`l______>50
`
`COMPARATOR
`
`7---"--
`
`600
`
`Apple Inc. Exhibit 1005 Page 4
`
`

`
`US. Patent
`
`June 8, 1993
`
`Sheet 4 of 4
`
`5,218,622
`
`'QEMULTIPLEXING CIRCUIT
`
`701w
`P
`10L.
`
`F
`5
`
`@
`
`:ELLER R
`SERCUIT .
`
`DECPDER
`
`CLASSIFYING
`MEANS \,
`
`405
`MEMORY ‘#50
`
`? -
`
`'
`
`,
`
`é
`
`a
`
`.702
`
`3
`
`! 703V
`
`.
`
`701.
`
`59"
`
`g
`
`‘
`
`TRANSMISSION ERROR
`
`730‘
`MEMORY
`
`R
`
`/ ,
`
`CALCULATING’ 731
`cmcun
`
`I
`Ri
`
`I
`702
`
`73L) BETECTIONCIRCHT
`»
`(
`MULTIPLYING
`cmcun
`
`-
`
`‘
`
`‘
`
`(737
`h
`Mi
`
`735
`L
`
`COMPARATOR
`737 /
`*
`
`sun
`
`’735
`\
`STORiNG
`
`coum;:§>4.m
`cmcun
`|_"'__"'
`0500mm” R
`an
`' cmcuns\\\
`7
`L
`N \~ "‘
`. ’—1 12
`.J\\
`l
`
`1"
`
`800
`
`-
`
`MEMORY
`
`-
`
`4
`
`sun
`
`u.
`)
`aogwwm
`\__
`
`=
`
`Apple Inc. Exhibit 1005 Page 5
`
`

`
`1
`
`5,218,622
`
`SYSTEM OF ENCODING DIGITAL SIGNALS
`INTENDED FOR TRANSMISSION AND/OR
`STORAGE AND A CORRESPONDING DECODING
`SYSTEM
`
`25
`
`BACKGROUND OF THE INVENTION
`The present invention relates to a system of encoding
`digital signals comprising a source encoder followed by
`a transmission channel encoder. It also relates to a sys
`tem of decoding digital signals which were previously
`submitted to a variable-length coding, an encoding with
`selective protection and an encoding without selective
`protection, the said system comprising a transmission
`channel decoder followed by a source decoder.
`Digitizing television signals requires the possibility of
`transmitting a very large quantity of binary information
`components with a rate of the order of 220 Mbit/s. Such
`a rate cannot be ensured at reasonable cost by contem
`porary transmission channels, and different information
`encoding techniques have been proposed with the ob
`ject of reducing the quantity of information components
`and consequently the rate. Such an objective is actually
`achieved by reducing the redundancy of information
`components, but, then, each information component
`transmitted becomes essential. Any possible transmis
`sion errors which might rather easily be corrected when
`the information components to be transmitted are re
`dundant, have increasingly more serious consequences
`when this redundancy is reduced. Actually, the extent
`of faults due to transmission errors unfortunately in
`creases more rapidly than the rate reduction factor.
`When a transmission channel beset with noise is pres
`ent, efforts have been made to ?nd protection from
`these transmission errors or to reduce their effects. One
`of the techniques thus proposed consists, for the encod
`ing of information components, in associating an error
`correction coding (alternatively denoted channel cod
`ing) to a rate reducing coding (alternatively denoted
`source encoding) which renders it possible to protect in
`40
`a selective manner the information components which
`are most sensitive to transmission errors. A method and
`a coding system ensuring such a protection are de
`scribed, for example, in the U.S. Pat. No. 4,555,729.
`The recent use, in source encoders, of variable-length
`45
`codes which still further improve the performances of
`these encoders, leads to a new reduction of the redun
`dancy of the information components. Consequently,
`said information components are even more vulnerable
`to transmission errors. On the other hand, a variable
`length encoding results in allocating to information
`component blocks of similar dimensions, a variable
`number of bits as a function of the information con
`tained in each block. In this case, the presence of trans
`mission errors may cause the loss of the proper segmen
`tation of encoding words corresponding to a block, or
`the loss of synchronization between blocks, which
`would entail the appearance of false designs as well as
`spatial shifts in the picture.
`These faults are difficult to correct with contempo
`rary error correction techniques, to that extent that,
`with a variable-length encoding, the positions of impor
`tant information components in the binary sequence are
`not known. An error in the most signi?cant bits of the
`direct current component, for example, is much more
`65
`perceptable than an error in the last bits of a block of
`information components. But, by reason of the variable
`length of the coding sequences (or words), the contem
`
`60
`
`50
`
`2
`porary techniques have proved to be incapable of cor
`recting this type of error in an adapted manner.
`
`SUMMARY OF THE INVENTION
`It is an object of the invention to propose a digital
`signal encoding system which, while still being of a
`relatively simple structure, obviates the drawbacks
`mentioned in the foregoing when one wants to protect
`in a selective manner information components which
`have previously been submitted to a variable-length
`encoding. To this effect, the invention relates to a cod
`ing system characterized in that, for the case in which
`the source encoder is a variable-length coding circuit,
`the channel encoder comprises a series arrangement of
`a sub-assembly of encoding with selective protection
`and a sub-assembly of encoding without selective pro
`tection.
`The structure thus proposed provides an ef?cient
`solution for the problems mentioned. Actually, for a
`desirable average redundancy which will, for example,
`be of the order of 10% for the channel encoder, simula
`tions have shown that an encoder with selective protec
`tion combined with a source encoder would require a
`considerably complex hardware. By adopting the pro
`posed structure, that is to say by cascading two simple
`coding operations, one of which ensures a non-selective
`coarse protection and the other a selective protection at
`several levels, a compromise is realized performance
`and complexness, all this for a relatively small addi
`tional redundancy. The selective encoding has for its
`object to reduce the error rate in the bits of the signal
`blocks resulting from the variable-length coding, as a
`function of the importance of these bits, while the non
`selective encoding is intended to reduce the error rate
`of the channel to a moderate value, the two encoding
`operations thus associated sharing together the redun-'
`dancy assigned to the channel encoder.
`In a preferred embodiment, the said system is more
`speci?cally characterized in that, the signals being ar
`ranged in information component blocks, the sub
`assembly of encoding with selective protection com
`prises:
`_
`A) a stage for encoding lengths of blocks determining
`along a block an accumulated length of code words
`supplied by said source encoder and ensuring the en
`coding of block lengths thus determined;
`B) a stage for selective protection of said blocks;
`(C) a stage for multiplexing the signals supplied by
`said length encoding and selective protection stages.
`As a matter of fact, since the use of a variable-length
`encoding provides signal blocks whose dimension-that
`is to say the number of bits per block-varies as a func
`tion of the'information contained in the original block,
`it is of importance to operate an adjustment, or synchro
`nization, of these variable-size blocks so as to enable a
`distinction between information components belonging
`to each of these blocks. The solution, which here con
`sists of transmitting the length of the block, enables,
`thereafter, an easy marking of the beginning of each
`block.
`In a specific embodiment of the stage for encoding
`these lengths, this stage comprises:
`(A) means for determining the length of each block
`after the variable-length encoding, the means compris
`ing:
`(a) a bit counting circuit arranged for counting for
`each block the number of bits of the variable-length
`
`Apple Inc. Exhibit 1005 Page 6
`
`

`
`H 0
`
`15
`
`25
`
`5,218,622
`3
`encoded signals supplied by the source encoder in asso
`ciation with each block;
`(b) a memory for storing the output signal of said bit
`counting circuit;
`(B) means for counting the number of blocks whose
`length has been determined, which means comprise:
`(c) a circuit for counting blocks starting from signals
`indicating the end of a block and being also supplied by
`said source encoder;
`(d) a decision circuit for controlling reading of the
`memory as a function of the output signal of said block
`counting circuit;
`(C) length~encoding means, comprising:
`(e) an encoding circuit for supplying the words for
`encoding the length of said blocks.
`The synchronizing information components which
`are the said block lengths are very important and advan
`tageous, and their protection from errors is ensured in
`an ef?cient manner when the encoding circuit of the
`length encoding means is a simple and powerful en
`coder, for example a linear systematic binary encoder.
`Satisfactory results are obtained with an encoder de
`noted C(52, 40), for code words having a maximum of
`40 bits and 12 parity bits.
`In a speci?c embodiment of the selective block pro
`tection stage, the stage comprises:
`(A) means for classifying the bits in accordance with
`their sensitivity to transmission errors;
`(B) means for selective encoding as a function of said
`classi?cation;
`(C) means for reducing the code words resulting from
`said selective encoding. For the selective encoding
`means, a what is commonly denoted a Blokh-Zyablov
`encoder is preferably chosen, which in a simple manner
`allows, by reduction, of the adaptation of the length of
`the words to be encoded to the length of the blocks to
`be encoded. As the reducing procedure generally signif
`icantly reduces the efficiency of the code with respect
`to the non-reduced code, the choice of the Blokh-Zya
`blov code is instigated by the desire to ensure several
`protection levels, while still providing an optimum ef?
`ciency after reduction.
`In accordance with a particular embodiment of the
`said means, the coding system is such that:
`(A) the means for classifying the bits in accordance
`with their sensitivity to transmission errors comprise
`(a) a memory for receiving in a ?rst memory zone the
`variable-length encoded signals from the source en
`coder and in a second memory zone the order of the
`said encoded signals for addressing said ?rst memory
`zone and for supplying said encoded signals in a se
`quence which is modi?ed as a function of said address
`1118;
`(B) the means for selective encoding as a function of
`said classi?cation comprise:
`'
`55
`(b) a Blokh-Zyablov encoder;
`(C) the means for reducing the selective encoding
`word comprise bit suppressing means.
`Moreover, since the lengths of the blocks can vary
`signi?cantly, the encoding system is characterized in
`that the multiplexing stage comprises:
`(A) means for multiplexing the output signals of the
`said block-length encoding stage and said stage for
`selective protection of the blocks;
`(B) means for controlling the rate of the output sig
`nals from said multiplexing means;
`.
`and in that, when the length L of the block considered
`exceeds the coding capacity K of the said selective
`
`4
`protection stage, said multiplexing means also provides
`for the multiplexing of the non-coded (L-K) bits.
`Whatever the speci?c characteristics of these various
`embodiments, it is necessary to ensure also the decoding
`of digital signals which have previously been submitted
`to a processing operation as de?ned in the foregoing,
`namely a variable-length encoding followed by encod
`ing operations with and without selective protection.
`A further object of the invention is therefore to pro
`vide a decoding system suitable for processing encoded -
`digital signals such as the signals supplied by the encod
`ing system de?ned in the foregoing.
`To this effect, the invention also relates to a system
`which is characterized in that the channel decoder com
`prises, arranged in series, a decoding sub-assembly with
`non-selective protection and a decoding sub-assembly
`having n selective protection levels.
`In a preferred embodiment, this decoding system is
`characterized in that, the signals having been encoded
`in blocks, said n-selective protection level decoding
`sub-assembly comprises:
`(A) a length decoding stage, arranged for permitting
`during each decoding operation the decoding of those
`received signals which correspond to the lengths of said
`blocks;
`(B) a stage for decoding other received encoded sig
`nals;
`(C) a demultiplexing stage particularly provided for
`switching the received encoded digital signals either to
`said length decoding stage or to said stage for decoding
`the other encoded signals.
`This stage for decoding other received encoded sig
`nals preferably comprises:
`(A) means for demultiplexing said other encoded
`signals, and also any non-encoded (L-K) signals from
`said encoding with selective protection, when the
`length L of a block exceeds the encoding capacity K;
`(B) selective decoding means comprising a Blokh
`Zyablov decoder having it parallel-arranged selective
`decoding circuits,
`(C) inverse reducing means, for adapting the format
`of the signals to be decoded to the capacity of the said
`selective decoding means when the length L of a block
`is less than said encoding capacity K;
`(D) means for classifying the decoded signals in ac
`cordance with their sensitivity to transmission errors;
`(E) storage means for storing the signals thus classi
`?ed.
`‘
`More particularly, in the example described, the
`Blokh-Zyablov decoder comprises:
`(a) a matrix memory for storing the output signals of
`said ?lling circuit;
`(b) a circuit for calculating the matrix expression
`R,~=R—C(k1, k2, . . . k,~_1, 0, . . . 0) wherein R is the
`content of said matrix memory and C(lq, k2, . . . , k,-_1,
`0, . . . 0) is the code word obtained when all the kiwhich
`have not yet decoded are considered to be equal to zero;
`(0) a circuit for matrix multiplication in view of deter
`mining the matrix expression M,-= (6')- ‘R; where
`(60-1 is the inverse of the transposed matrix of the
`following matrix G:
`
`30
`
`40
`
`45
`
`65
`
`Apple Inc. Exhibit 1005 Page 7
`
`

`
`l 0
`l
`l
`l 0
`l 0
`
`(d) a decoding device, comprising a demultiplexing
`circuit, subsequently, arranged in parallel, n selective
`decoding circuits followed by a series arrangement of a
`matrix memory for storing the decoded output signals
`of said decoding circuits and a code word recovery
`circuit for recovering the code words intended for up
`dating the expression C(k1, k2, .
`.
`. , k,-_1, 0, . . . , 0)
`applied to said circuit for calculating the matrix expres
`sion R1‘;
`_
`(e) a transmission error detection circuit, in view of
`correcting the decoding effected by said decoding de
`vice, the said transmission error detection circuit being
`advantageously of such a structure that it comprises, to
`realize the (n- 1) cycles of detecting errors, means for
`comparing the columns of the matrix expression R; on
`the one hand and, for the (n- 1) levels of selective pro
`tection other than the ?rst level, the assemblies E2, E3,
`.
`.
`. , E” of the words on the other hand, which words
`are formed by combining the (n-l) last lines of the
`matrix G, by combining the (n-2) last lines of G, etc. .
`. . , and by combining the last two lines of G, and which
`are formed from the last line of G for the nth protection
`level respectively.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Particulars and advantages of the invention will now
`become more apparent from the following description
`which is given by way of example with reference to the
`accompanying drawings, in which:
`FIG. 1 is a basic circuit diagram showing, in a digital
`signal transmission circuit, the source encoder/channel
`encoder combination and the channel decoder/source
`decoder combination;
`FIG. 2 shows an embodiment of circuits of an encod
`ing system in accordance with the invention;
`FIGS. 3 and 4 show, respectively, an embodiment of
`the length-encoding stage and the selective protection
`stage of the encoding system of FIG. 2;
`FIG. 5 shows an embodiment of the selective encod
`ing circuit of the selective protection stage shown in
`FIG. 4;
`FIG. 6 shows an embodiment of circuits of an decod
`ing system in accordance with the invention;
`50
`FIGS. 7 and 8 show, respectively, an embodiment of
`the length decoding stage and the other encoded signal
`decoding stage of the decoding system of FIG. 6;
`FIG. 9 shows an embodiment of selective decoding
`means provided in the decoding stage of FIG. 8.
`
`45
`
`30
`
`5,218,622
`6
`encoding section, by describing with the aid of FIGS. 2
`to 5 an example of the encoding system in accordance
`with the invention, and thereafter everything referring
`to the decoding section situated downstream of the
`channel, that is to say the assembly formed by the chan
`nel decoder and the source decoder, with reference to
`FIGS. 6 to 9.
`The encoding system shown in FIG. 2 comprises a
`variable-length encoding circuit 10. This circuit 10 con
`stitutes the source encoder and basically comprises, in a
`conventional manner, an orthogonal transformation and
`quantization circuit, a variable-length encoding circuit,
`and a rate regulating circuit including a buffer memory.
`The encoding system further includes a channel en
`coder 20, which comprises a series arrangement of an
`encoding sub-assembly with selective protection and an
`encoding sub-assembly without selective protection.
`The encoding sub-assembly with selective protection
`includes, more speci?cally, a stage 100 for encoding the
`accumulated lengths of the code words of a block (the
`term block lengths will be used to make the description
`more exact) supplied by the encoding circuit 10, a stage
`200 for the selective protection of information compo
`nent blocks supplied by the encoding circuit 10, and a
`multiplexing stage 300 for the signals supplied by the
`said length and selective protection encoding stages 100
`and 200.
`Information component blocks must be understood to
`mean signal sub-assemblies of the same dimensions,
`which are obtained by subdividing the initially consid
`ered information bit clusters (for example television
`pictures). These information bit blocks, after having
`been submitted to said orthogonal transformation, can
`be classi?ed, by comparing them to thresholds, in ac
`cordance with a greater or lesser activity (connected
`with contours, contrasts, greater or less great unifor
`mity of the blocks), and a signal expressing this classi?
`cation is then transferred by the orthogonal transforma
`tion and quantizing circuit, and transmitted. Similarly,
`the rate regulating circuit includes a feedback loop
`through which a standardization signal is conveyed
`which is also transmitted. These classi?cation and stan
`dardization signals are useful, at the receiving end, to
`effect operations which are the inverse of those used at
`the transmission end, with a view to the recovery of the
`blocks and the recovery of information clusters which
`are similar to the initial information clusters.
`The block length encoding stage 100 shown in FIG.
`3 comprises means (101, 103) for determining the length
`of each block after variable-length encoding, means
`(102, 104) for counting the number of blocks of which
`the length has been determined, and length encoding
`means. Put more precisely, this stage 100 ?rst of all
`includes a circuit 101 for counting the bits correspond
`ing to a block and a block counting circuit 102. An
`end-of-block signal EOB is applied by the orthogonal
`transformation and quantizing circuit of the circuit 10 to
`the block counting circuit 102, the content of which is
`incremented by one unit each time the signal EOB is
`received. The block length determined by the circuit
`101 is stored in a memory 103, and the counting circuit
`101, reset to zero under the control of the signal BOB
`(line RS1), is available for a new block length count.
`vWriting into the memory 103 (line WR) is controlled by
`the signal EOB.
`A decision circuit 104 determines, by comparison to a
`pre-registered number, on the basis of what number of
`
`55
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`As has been described in the foregoing, a known
`technique of protection against transmission errors con
`sists in associating a channel encoder with a source
`encoder. This technique is shown schematically in FIG.
`1, which comprises a source encoder l and, arranged
`between this encoder and a transmission channel 3, a
`channel encoder 2. In a symmetrical manner, a channel
`decoder 4 followed by a source decoder 5 are present at
`the output of the channel 3. In the present description,
`the description will ?rst be given with reference to the
`
`65
`
`Apple Inc. Exhibit 1005 Page 8
`
`

`
`5
`
`25
`
`30
`
`Mr-lhi-l
`
`oo--c>
`
`0-100
`
`'-'OOO
`
`5,218,622
`8
`.
`7
`blocks-and consequently lengths determined—the_
`more than the following signals, corresponding to each
`memory 103 must be read. This circuit 104, which is a
`protection level:
`comparator, is placed at the output of the block count
`circuit 211: 113 bits (protection level i), representing
`ing circuit 102 and supplies (line RD) a read control
`the most signi?cant bits in each block;
`signal for the memory 103 at the instant at which the
`circuit 212: l25 bits (level 2);
`content of the circuit 102 (the number of blocks of
`circuit 213: 125 bits (level 3);
`which the lengths have been determined) is equal to the
`circuit 214: l26 bits (level 4) representing the least
`pre-registered number. This read control signal is also
`signi?cant bits in each block. If the length of a block
`conveyed to the circuit 102 to reset it to zero (line RS2).
`exceeds 489 bits, the additional bits are not encoded nor
`The pre-registered number is, for example, equal to 4,
`protected.
`and reading of the memory 103 occurs when four
`At the output of these four encoding circuits 211 to
`lengths have been determined and stored sequentially.
`214 there are thereafter provided a matrix memory 215
`These four block lengths, which represent a maxi
`for storing the encoded output signals of these circuits,
`mum of 40 information bits when the bit counting cir
`thereafter a matrix multiplication circuit 216 for multi
`cuit 102 is a l0-bit counter, are sequentially applied to a
`plying the content of the memory 215 by the transposed
`length encoding circuit 105. This circuit 105 is a system
`matrix G' of the following matrix G:
`atic linear binary encoder, denoted encoder “in blocks”,
`which has been chosen for its suitability to correct y
`errors for x information components received: the num
`ber x of bits received applied by the memory 103 to the
`encoding circuit 105 being, as has been mentioned in the
`foregoing, equal to 40 at the utmost, the maximum num
`ber of errors one wants to correct for such a number of
`information components received is equal to 2, and the
`binary code then chosen is denoted C(52, 40), 40 repre
`senting the maximum number of bits received and the
`remaining 12 bits being parity bits. The output of the
`encoding circuit 105 constitutes the output of the block
`length encoding stage 100.
`The stage 200 for the selective protection of informa
`tion component blocks, shown in FIG. 4, ?rst of all
`includes a memory 201, which constitutes a circuit for
`classifying the bits in accordance with the sensitivity of
`these bits to errors caused by the transmission channel.
`For code words resulting from a variable-length encod
`ing, this sensitivity is determined on the basis of previ
`ous statistic analyses, the results of which are grouped
`in a Table associated with memory 201. The bits sup
`plied by the variable-length encoding circuit 10 are
`stored in the memory 201 and thereafter read again in
`accordance with a sequence of addresses contained in
`the Table, with a view of arranging these bits in a cer
`tain order (generally in an order of decreasing sensitiv
`ity), which are then applied to a selective encoding
`circuit as a function of the said classi?cation, for exam
`ple a Blokh-Zyablov encoder 202, which has been se
`lected for its suitability to permit a plurality of encoding
`levels in accordance with the bit classi?cation effected.
`In all cases, this encoder 202 is capable of encoding K
`bits at a maximum. If the length L of an information
`50
`component block is less than this encoding capacity K,
`the (K-L) non-used bits cause a reset to zero in the
`information component circuit of length K processed
`by the Blokh-Zyablov encoder 202. If in contrast
`thereto the length L exceeds the capacity K, only K bits
`are encoded. The (L-K) remaining bits are not encoded
`and are multiplexed with the code words produced by
`the Blokh-Zyablov encoder, in the multiplexing stage
`300
`In the present case one has opted for having, for
`example, four coding levels, that is to say a four-level
`selective protection. The encoder 202, shown in FIG. 5,
`then includes, ?rst of all, a demultiplexing circuit 210,
`thereafter, arranged in parallel, four selective encoding
`circuits 211 to 214, each receiving the bits assigned to
`them by the circuit 202. In the example described, the
`encoder 210 has a coding capacity of 489 bits, and said
`selective encoding circuits respectively receive not
`
`The matrix memory 215 comprises 4 lines, equal to the
`number of selective protection levels, and 127 columns.
`This format is the same as that of the matrix, denoted C,
`of the result of said matrix multiplication.
`The signals EOB indicating the end of the block
`already mentioned, provide the write command and
`thereafter the read command of the memory 215. Delay
`circuits 217 and 218 are arranged in the write and read
`command links, denoted WR and RD, respectively, of
`the memory 215 to take into account the duration of the
`selective encoding operations and for synchronizing
`these two commands relative to the signals to be stored
`and thereafter read.
`The output signal of the circuit 216, which constitutes
`the output signal of the encoder 202, is applied to a
`reducing circuit 203, which renders it possible to sup
`press, if necessary, that is to say when they exist, the
`(K-L) bits which have been reset to zero, and the out
`put signal of this circuit 203, which constitutes the out
`put signal of the stage 200, is then conveyed to the
`multiplexing stage 300.
`The mode of operation of the encoder 202 is as fol
`lows. Let k,- be the number of bits for each encoding
`level, wherein i=1 to 4, when four encoding levels are
`used. The numbers in, kg, k3, k4 being associated with
`each one of the respective four levels, there is added to
`each of the k; bits a number in corresponding to the
`parity bits connected with the extent of protection
`wanted for each level. In the example described, the
`following options have been made:‘ ml: 14, m2=2,
`m3=2, m4=1, where the choice of the couples (m,~, 14;)
`must permit the classification of the code words thus
`constituted in the memory 215, arranged as follows,
`wherein M denotes the matrix corresponding to the
`content of this memory:
`
`40
`
`45
`
`60
`
`65
`
`Apple Inc. Exhibit 1005 Page 9
`
`

`
`5,218,622
`9
`for the encoder described here, which has four protec
`tron levels, the code words are obtained by multiplying
`the transpose Gt of the matrix G by this matrix M:
`
`6:
`
`coo-
`
`cot-
`
`._.oQ»
`
`o--o
`
`which results in:
`
`( .
`
`.
`
`. . .
`
`. . . . . . . . ..linel . . . .
`
`.
`
`.
`
`_ ..)
`
`( . . . . ..m2....)( .
`
`. . . . . ..k2....)
`
`.
`
`.
`
`.
`
`. . . ..k3....)
`
`(....m4....)( . . . . .
`
`. ..k4....)
`
`15
`
`20
`
`30
`
`10
`error control codes”, R. Blahut, Addison-Wesley Pub
`lishing Company, May 1984.
`When thereafter a digital signal encoding operation
`has been effected in an encoding arrangement of the
`type as described in detail in the foregoing, the digital
`signals thus encoded, thereafter transmitted and/or
`- stored, can conversely be decoded, in accordance with
`the invention, in a decoding system of the type shown,
`for example, in FIG. 6.
`This decoding system of FIG. 6 comprises a transmis
`10
`, sion channel decoder 40 followed by a source decoder
`50. The channel decoder 40 comprises, arranged in
`series, a decoding sub-assembly with’ non-selective pro
`tection, denoted 4-00, and a decoding sub-assembly with
`selective protection. The decoding sub-assembly with
`selective protection here comprises, more in particular,
`a demultiplexing stage 500 for switching the encoded
`digital signals received by the decoding system, a length
`decoding stage 600 for decoding that one of these en- ‘
`coded s