throbber

`
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`____________________
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`_____________________
`
`LG Electronics, Inc.
`Petitioner,
`
`v.
`FastVDO LLC
`Patent Owner.
`
`
`Patent No. 5,850,482
`_______________
`
`Inter Parte Review No. ____________
`
`___________________________________________________________
`
`U.S. Patent No. 5,218,622 to Fazel et. al.
`
`Exhibit 1006
`
`

`

`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
`
`

`

`US. Patent
`
`June 8, 1993
`
`Sheet 2 of 4
`
`5,218,622
`
`
`CIRCUIT
`
`
`
` SELECTIVE
`ENCODING
`CIRCUIT
`
`ENCODING
`
`Apple Inc.
`
`Exhibit1005
`
`Page3
`
`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 decodin

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket