United States Patent
`Immink et a].
`[45] Date of Patent: Feb. 19, 1985
`
`
`
` i
`
`
`
`
`
`
`
`
`
`
`
`
`
`[54]
`
`[75]
`
`[73]
`[21]
`
`[22]
`
`[51]
`[52]
`
`[58]
`
`[56]
`
`METHOD OF CODING BINARY DATA
`
`Inventors: Kornelis A. Immink; Jakob G.
`Nijboer, both of Eindhoven,
`Netherlands; Hiroshi Ogawa;
`Kentaro Odaka, both of Tokyo,
`Japan
`
`Sony Corporation, Tokyo, Japan
`Assignee:
`Appl. No.: 286,982'
`
`Filed:
`
`Jul. 27, 1981
`
`Int. (21.3 ............................................. HOSK 13/02
`US. Cl. ...................................... 375/25; 375/106;
`340/347 DD
`Field of Search ..................... 375/18, 19, 25, 106,
`375/112; 340/347 DD; 360/40, 48; 371/55, 57;
`358/13
`
`References Cited
`
`UtS. PATENT DOCUMENTS
`3,631,471 12/1971 Griffiths ...................... 340/347 DD
`3,810,111
`5/1974 Patel
`........ 360/40
`
`3,995.264 11/1976 Ouchi ................. 371/55
`1/1977 Van Duuren ..
`. 340/347 DD.
`4001041
`
`4,020.282
`4/1977 Halpern
`375/34
`
`
`5/1978 Weir et al
`4,092,595
`375/17,
`
`4,229,808 10/1980 Hui ......
`360/48
`1/1982 Henry .......................... 340/347 DD
`4,309,694
`Primary Examiner—Robert L. Griffin
`
`Assistant Examiner—Stephen Chin
`Attorney, Agent, or FirmmLewis H. Eslinger; Alvin
`Sinderbrand
`
`[57]
`
`ABSTRACT
`
`A system for block encoding words of a digital signal
`achieves a maximum of error compaction and ensures
`reliability of a self-clocking decoder, while minimizing
`any DC in the encoded signal. Data words of m bits are
`translated into information blocks ofni bits (n1>m) that
`satisfy a (d,k)-constraint in which at least (1 “0” bits, but
`no more than k “0" bits occur between successive “1"
`bits. The information blocks are catenated by inserting
`separation blocks of n2 bits therebetween, selected so
`that the (d,k)—constraint is satisfied over the boundary
`between any two information words. For each informa-
`tion word, the separation block that will yield the low-
`est net digital sum value is selected. Then, the encoded
`signal is modulated as an NRZ-M signal in which a ”1"
`becomes a transition and a “0" becomes an absence of a
`transition. A unique synchronizing block is inserted
`periodically. A decoder circuit, using the synchronizing
`blocks to control its timing, disregards the separation
`blocks, but detects the information blocks and translates
`them back into reconstituted data words of in bits. The
`foregoing technique can be used to advantage in record-
`ing digitized music on an optical disc.
`
`13 Claims, 10 Drawing Figures
`
`
`
`[19]
`
`{11] Patent Number:
`
`4,501,000
`
`LSI Corp. Exhibit 1032
`Page 1
`
`

`

`U.S. Patent
`
`Feb. 19,1985
`
`SheetlofS
`
`4,501,000
`
`F i G. M
`.mmm
`BDi—-—|
`A
`BD]
`
`i 1
`
`4 56 731 2
`
`‘
`
`‘
`
`B11
`
`BB:
`
`Fi G.
`
`71531
`
`15 12 3 4 5678910111213 1516 12
`‘ WF
`._
`
`_
`
`.[OICEIIOIOMOIOHOIOIUIOH[0101.]-
`
`FIG.
`
`_2A
`851—2
`
`.BC;
`,
`
`,
`
`85H
`
`BBi
`
`85M
`
`F-BCi-1-+—BCi—‘+*BCI+1"'
`F—DBC.‘ -——‘l
`
`~F/G.> 28
`
`
` (I)
`(Z)
`(
`)
`(4
`BCJ +BCJ' —'+—BCJ‘3—+—BQ
`
`BBC}
`
`LSI Corp. Exhibit 1032
`
`Page 2
`
`LSI Corp. Exhibit 1032
`Page 2
`
`

`

`U.S. Patent
`
`Feb. 19,1985
`
`Sheet20f5
`
`4,501,000
`
`
`
`LSI Corp. Exhibit 1032
`Page 3
`
`LSI Corp. Exhibit 1032
`Page 3
`
`

`

`US. Patent
`
`Feb. 19,1985
`
`Sheet3of5
`
`4,501,000
`
`F7/C3.
`
`4
`
`L0000000000100000000OJOIOW001I
`SYNPI
`SYN132‘“!
`
`BYNS
`
`,2I-lf-‘é“i 22
`
`,
`
`FIG. 6
`
`w
`
`.
`
`24
`.IllllllllllllIII".
`'25
`
` :||||||||||||
`-2<z
`:
`SQ
`
`C6
`C14
`
`FIG.
`
`7
`
`I
`SYN
`I
`
`51B
`
`BC4 855 865
`{551303
`35’ 552853 3565
`
`LSI Corp. Exhibit 1032
`
`Page 4
`
`LSI Corp. Exhibit 1032
`Page 4
`
`

`

`U.S. Patent
`
`Feb. 19,1985
`
`Sheet4of5.
`
`4,501,000
`
`FIG.
`
`5A
`
`="'—"é
`
`
`
`_
`.
`
`Z
`
`.
`
`C1 C2
`
`C1
`-
`.17—0
`CZ
`I
`’17-:
`E3
`(355.171 'l—IIB-l )
`C4
`:D _Ir"=)
`C5
`17—3 -I 18-2
`-
`C’ I 1 —)
`_
`C101
`17-4
`15-3
`C5 . _
`_ > ’ " 204
`C2
`.175
`[54"14 20-5
`“17—6
`15-5
`|
`‘
`206
`C5
`E
`[‘6'
`I
`20-7
`:
`15—7 } I
`{
`:
`15‘5
`
`20—!
`
`,. 20—2
`20—3
`
`20-8
`
`LSI Corp. Exhibit 1032
`
`Page 5
`
`LSI Corp. Exhibit 1032
`Page 5
`
`

`

`US. Patent
`
`Feb. 19,1985
`
`Sheet 5 of 5
`
`450L000
`
`F7(3.
`
`5E?
`
`14131
`
`
`
`
`
`
`
`
`
`
`
`L1'
`.1
`
`.------unumm-numm-l-m-nA
`
`
`mnnnnnunmflmug—ammmm—mmmmnmm_-_Mnnnnnnnn—E—Emm:Eunflnuummn13_.
`_3InIIIIIIIIIIIIIIIIIInIII4nIImmIIIIIIIIIIIIIImIIIII—nI-fl-
` _6IIIIIIIIIIIIIIIImnnmmImamnnIIo
`
`.2fining-53:33.5“nnmm-A
`_..m-nnnn-E-E-nnun-un-mulunuunflfl
`
`E...-Em—umA-E.nAmAAA6-...—m-AmA..A-.m—AAAA
`.5IImmImnIIIIIIIIIIIImInmIIIIIIIImmIIII1
`
`m“nan—Emma—nun—mmnnmn.mnmn__m=_fl-“w
`
`inn-EE-EmmA-1m.-flu.AA__
`IIImmmuIIIIIIIIII—-ImAu—AmAmmIInnIInuIIIIIIIIIIIII.I—II
`
`IIIIIIIIIIIIII«Imam-IIIImuIII'II
`MImIquIIIIIIIIIIIIImIImIIII
`IIIIIInIIInIIIIIIIIIIImmmInmmIIEIIIIIIImnInnIIInIIIIIImmmImmmnnmm
`mammanmmmmmmmmmmmmmmmammmmmmmmmagmmmmmmmmmmmmmmmm __m_E
`
`
`1I
`.
`
`
`
`
`m2.!A
`mmmmflnIIIImmmmUIm
`
`
`
`
`
`
`
`
`LSI Corp. Exhibit 1032
`
`Page 6
`
`LSI Corp. Exhibit 1032
`Page 6
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`4,501,000
`
`1
`
`METHOD OF CODING BINARY DATA
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`This invention relates to a system for encoding binary
`data words into a converted digital code for transmis-
`sion and thereafter decoding the received digital code
`into the original binary data words. In particular, this
`invention relates to a method of encoding words of ‘0
`binary information into encoded information blocks
`having separation blocks disposed therebetween to min<
`imize the overall DC component of the transmitted
`digital code. The invention is also directed to apparatus
`for decoding such a coded signal, and to a record me-
`dium carrying information so encoded.
`2. Brief Description of the Prior Art
`In digital transmission systems and in magnetic and
`optical recording/playback systems, the information to
`be transmitted or to be recorded is presented as a se-
`quence of symbols. These symbols collectively form an
`alphabet, which for binary data is a binary alphabet
`consisting of the symbols “1” and “0“. One symbol, for
`example the “I”, can be recorded in accordance with
`non-retum—to-zero-mark (NRZ-M) code as a transition
`between two states of magnetization in the case of a
`magnetic disc or tape, or between two states of intensity
`or focus in the case of an optical disc. The other symbol,
`the “0", is recorded by the absence of such a transition.
`As discussed in greater detail below, certain system
`requirements in practice impose constraints on the
`order in which these symbols may occur.
`Some systems are required to be self-clocking. This
`implies that the sequence of symbols to be transmitted
`or to be recorded should have sufficient transitions so
`that a clock signal, which is required for detection and
`synchronization, can be generated and regulated by the
`sequence of symbols alone.
`A further requirement may be that certain symbol
`sequences are forbidden in the information signal, as
`these sequences are intended for special purposes, for
`example as a synchronizing sequence. If the synchroniz—
`ing sequence is mimicked by a sequence in the informa~
`tion signal, the information signal destroys the unambi-
`guity of the synchronizing sequence and, consequently,
`renders the synchronizing sequence unsuitable for its
`intended purpose.
`It may further be required that the transitions not
`follow too closely after each other in order to limit
`intersymbol interference.
`In the case ofmagnetic or optical recording, the latter
`requirement may also be related to the information
`density on the recording medium. For example, if the
`predetermined minimum distance between two consec-
`utive transitions on the recording medium, and conse~
`quently the minimum time interval (Tm-n) correspond-
`ing therewith of the signal to be recorded is increased,
`the information density is increased substantially to the
`same extent. Also, the required minimum bandwidth
`(Bmm) correlates to the minimum distance T,,,;,, between
`transitions, i.e., B,,,,-,,= l/(ZTmm).
`In addition, the DC component of the sequence of
`symbols should be kept as close to zero as possible,
`preferably at zero, because information channels are not
`normally responsive to direct current and any DC com-
`ponent of the transmitted or recorded signal is likely to
`be lost.
`
`65
`
`2
`A method of encoding data to satisfy this requirement
`is generally discussed in D. T. Tang and L. R. Bahl,
`“Block Codes for a Class of Constrained Noiseless
`Channels”, Information and Control. vol. 17, hr. 5, De-
`cember 1970, pp. 436-461. Therein are discussed block
`codes based on so-called (d,k)-constrained q—nary
`blocks of symbols arranged to satisfy a d-Constraint and
`a k-constraint:
`
`(a) d-constraint—two “l"-type symbols are separated
`by a run of at least d consecutive symbols of the “0"
`type; and
`
`(b) k—constraint-the maximum length of a run of
`consecutive symbols of the “0” type is k.
`For example, if a stream of binary data is considered
`as consecutive sequential blocks (or words) each having
`m data bits, the words can be encoded into correspond-
`ing code blocks of n information bits, where n>m.
`Since n> m, the number of possible code blocks (2”) far
`exceeds the number of different data words (2“), and
`only those code blocks need be used which satisfy the
`d—eonstraint and the k—constraint. 1n other words, if the
`d- and k-constraints are imposed on the code blocks of
`n information bits to be transmitted or recorded, the 2'"
`different words map onto a corresponding 2"1 blocks of
`information bits out of a total possible number of 2" such
`blocks. Thus,
`the mapping of data words into code
`blocks is carried out so that only those code blocks are
`used that satisfy the k~constraint and d-constraint.
`Table I of Tang and Bahl shows how the number of
`different code blocks of information bits depends on the
`length of the block (n) and the requirement imposed on
`d. For example, if there are eight code blocks of infor~
`mation bits having a length n=4 and minimum distance
`d: l, and the data words to be encoded have a length
`m=3, then all the eight (:23) data words can be repre-
`sented by the respective eight code blocks of n=4 infor-
`mation bits. In these blocks, two consecutive “I”-type
`symbols in the blocks of information bits are separated
`by at least one “0"-type symbol. For this example, the
`coding is as follows (<———>), where the double-headed
`arrow indicates mapping of one word onto the corre-
`sponding code block and vice versa:
`OOOMOOOO
`COL—60001
`0104——»0010
`011«—>0100
`100<———>0101
`lOI<——+IOOO
`1 ICE—+1001
`Illa—.1010
`
`When linking-up, or catenating consecutive code
`blocks of information hits, it is in some cases not possi-
`ble to satisfy the d-constraint without taking further
`measures. In Tang and Bahl, it is proposed to include
`separation bits between the blocks of information bits.
`In order to satisfy the d-constraint, one block of separa—
`tion bits comprising d-bits of the “0"-type is sufficient.
`In the above-mentioned example, where d: I, one sepa-
`ration bit (a single “0") is therefore sufficient. Each
`three-bit data word is then encoded into a code block of
`five (4+ 1) channel bits.
`This coding method has the disadvantage that the
`contribution of the low frequencies (including DC) to
`the frequency spectrum of the stream of channel bits
`can be rather high. A further disadvantage is that the
`construction of the coding converters, i.e., the modula-
`tor and demodulator and in particular, the demodulator,
`becomes rather complex.
`
`LSI Corp. Exhibit 1032
`
`Page 7
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LSI Corp. Exhibit 1032
`Page 7
`
`

`

`3
`In A. M. Patel, “Charge-constrained Byle-oriented
`.(0,3) Code", 1.3.114. Technical Disclosure Bulletin, Vol.
`19, Nr. 7, Dec. 1976, pp. 2715~27l7, it has been pro-
`posed to limit the direct-current imbalance of (d,k)—con-
`strained codes by linking the code blocks of channel bits
`by using a so-called inverting link or a so—called non-
`inverting link, as appropriate. By use of these links, the
`contributions of a particular code block to the DC im—
`balance occur so as to offset the DC imbalance of any
`preceding code blocks, to keep the net DC imbalance at
`a minimum. However, if this technique is applied to a
`(d,k)—constrained coding scheme, care must be taken so
`that
`the inverting and/or non-inverting links satisfy,
`rather than conflict with, the d-constraint and the k-
`constraint when the code blocks are catenated to form
`a code sequence that also has a minimum DC imbalance.
`In other words, blocks of separation bits should be
`selected to satisfy the d- and k-constraints, as aforesaid,
`and also to reduce the net DC imbalance.
`
`OBJECTS AND SUMMARY OF THE
`INVENTION
`
`It is an object of the invention to provide a coding
`scheme for binary data which will produce a code satis-
`fying the above (d,k)-constraints and while keeping the
`net DC imbalance at a minimum.
`It is a more specific object of this invention to provide
`a coding scheme suitable for use in the recording and
`playback of digitized audio information.
`It is another object of this invention to provide a
`coding scheme which provides a coded digital signal
`having improved bandwidth characteristics because
`low-frequency portions of the signal spectrum are kept
`small.
`
`It is yet another object of this invention to provide a
`coded digital signal wherein the minimum distance
`Tmm between consecutive transistions is small, so that
`the minimum bandwidth Bmm (= l/2Tm,-,,) for the digi-
`tal signal is also kept small.
`It is a further object of this invention to provide a
`coding scheme in which the bit packing density is maxi-
`mized without sacrifice of reliability, and which pro-
`vides a code decodeable in a self-clocking decoder.
`According to one aspect of this invention, a method
`of encoding data for transmission is provided, wherein
`the original data are considered as words of m bits. The
`data are converted into channel blocks formed of infor-
`mation bits of n; serial bits followed by respective sepa-
`ration blocks ofa predetermined number of bits, where
`m>m, and in a stream formed of a sequence of such
`channel blocks, a d—constraint and a k-constraint are
`satisfied, wherein consecutive bits of one type charac-
`terized by a transition are separated by at least d bits of
`another type characterized by an absence ofa transition,
`while no more than a maximum of k bits of the other
`type occur between successive bits of the one type. In
`the method of this invention, the words of m bits are
`received and converted, or mapped into corresponding
`information blocks of m bits. Next, a set of possible
`separation blocks for use between successive informa-
`tion blocks is generated so that
`the information and
`separation blocks together satisfy the d—constraint and
`the k-eonstraint. A superblock is then initially formed
`which includes a plurality ofthe successive information
`blocks catenated with respective possible separation
`blocks. The total DC imbalance of the initially formed
`superblock is determined and those possible separation
`blocks which yield a superblock having the least total
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4,501,000
`
`4
`DC imbalance are selected. A subsequent superblock is
`then formed from the initially formed superblock, but
`excluding therefrom the first information and separa-
`tion blocks thereof, and from the next successive infor~
`mation block and another of the possible separation
`blocks. The total DC imbalance for the subsequent
`superblock is determined. Thereafter, possible separa-
`tion blocks yielding the least total DC imbalance of the
`subsequent superblock are selected. Finally, the steps of
`forming a subsequent superblock, determining the DC
`imbalance thereof and selecting the separation blocks
`thereof yielding the least total DC imbalance for the
`successive information blocks and associated separation
`blocks are iterated. Preferably, synchronizing sequen»
`ces are provided periodically in the stream of coded.
`blocks, each formed of two synchronizing blocks which
`also satisfy the (d,k)-constraints, but which are readily
`distinguishable from any sequence of bits in the channel
`blocks.
`
`According to another aspect of this invention, a de-
`modulator is provided for converting the encoded sig—
`nal back to data words of in bits, comprising a detector
`for detecting the synchronizing sequences, a separating
`circuit for processing the channel blocks and separating
`the information blocks from the separation blocks, and
`timing circuitry for controlling the timing of the sepa-
`rating circuit in response to the detection of the syn-
`chronizing sequence. Then, the separated information
`blocks are furnished to a converter to be converted
`therein into the data words of in bits.
`According to yet another aspect of this invention,
`there is provided a record medium, such as an optical
`disc on which a digitized music signal is recorded. In-
`formation structure is recorded thereon comprising a
`sequence of channel bit cells within which a transition
`represents a binary digit of one sense and the absence of
`a transition represents a binary digit of another comple-
`mentary sense. The distance between any two succes-
`sive transitions is no greater than a maximum length of
`(k+-l) bit cells, while being no less than a minimum
`length of (d+ 1) bit cells. Synchronizing blocks are
`included at regular intervals on the information struc‘
`ture, each formed of not more than three transitions,
`consecutive ones of which are separated by a predeter-
`mined number of not more than (1: +1) bit cells, prefera-
`bly equal to (k+ 1) bit cells.
`In an embodiment of this invention, by way of exam-
`ple, the data words have a length of eight bits, each
`block has a length m of fourteen information bits, and
`the separation blocks are formed of three bits. Alterna~
`tively, three out of four separation blocks can have a
`length of two bits, and the fourth can have a length of
`six bits.
`
`Accordingly, as only 256 words are to be mapped
`into 16,384 possible information blocks, the (d,k)—con-
`straints can be easily satisfied. Further, catenation of
`channel blocks formed of the information blocks and
`the associated separation blocks is achieved while satis-
`fying the (d.k)—constraints and keeping the net DC im—
`balance at a minimum.
`
`These and other objects, features, and advantages of
`this invention will become more fully apparent from the
`ensuing description of preferred embodiments of this
`invention, when considered with the accompanying
`drawings.
`
`LSI Corp. Exhibit 1032
`
`Page 8
`
`LSI Corp. Exhibit 1032
`Page 8
`
`

`

`5
`
`4,501,000
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`6
`the (d,k)»constraints require that be—
`As aforesaid,
`tween two consecutive bits of the “1" type, which cor-
`respond to a transition, at least (1 consecutive informa-
`tion bits of the “0" type which correspond to the ab-
`sence ofa transition, must occur. Also, two consecutive
`bits ofthe “1" type are to be separated by not more than
`a maximum of k bits of the “0" type. It can be shown
`mathematically that for n1=14, d=2, and k=10, there
`are 277 possible combinations of bits which will satisfy
`the (d,k)—constraints. Thus, when encoding words of
`eight data bits, of which they are 23:256 combinations,
`the d-constraint and k—constraint can be readily satisfied
`by using blocks of 14 bits
`The catenation, or linking together, of successive
`blocks B1,- of information bits is not possible without
`further measures. This is true because the (d,k)-con-
`straints must be satisfied, not only witin any particular
`information block B1,, but also over the boundary con-
`necting two such blocks B1,: To this end, separation
`blocks 88,, each consisting of at least one bit, can be
`included between two successive information blocks
`B1,: It can be easily seen that if a sequence of at least (1
`separation bits of the “0” type is used between succes-
`sive information blocks B1,,
`then the d-constraint
`is
`satisfied. Furthermore, to ensure that the k-constraint is
`satisfied over the boundary between successive infor-
`mation blocks BIi, the separation block BS,-can include
`at
`least one bit of the “I” type in those instances
`wherein the bit distance between the last “1" of one
`information block Bliand the first “I” of the next suc-
`cessive information block BI”; would otherwise ex-
`ceed the maximum value it.
`In general, the blocks BS; of separation bits include
`n2 bits, so that a channel block BC; consists of m+n2
`bits. In the example illustrated in FIG. 18, n2=3.
`The above example, wherein m=8, n1=14, and
`nz=3 will be used throughout the remainder of the
`description, unless otherwise indicated.
`As mentioned previously, the purpose of the d—con—
`straint is to ensure that the transitions (corresponding to
`“1” bits) do not follow too closely upon one another.
`Appropriate selection of the value (1 will
`lead to
`achievement of an optimum information packing den-
`sity. Also, the selection of k at a value which is not too
`large,
`in this example, at k=lO, permits the encoded
`signal to be self clocking. This is, if the k-constraint is
`observed, the timing of the transition of the waveform
`WF can be used to control the synchronization of a
`local clock in the decoder.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIGS. 1A and 18 are charts showing illustrative bit
`sequences for explaining an embodiment of the coding
`format according to this invention.
`FIGS. 2A and 2B illustrate further bit sequences
`according to embodiments of the channel coding
`scheme of this invention, in which direct current imbal-
`ance is reduced;
`FIG. 3 is a flow chart explaining an embodiment of
`the method according to this invention;
`FIG. 4 illustrates a sequence of synchronizing bits for
`use in the method according to one embodiment of this
`invention;
`FIG. 5A shows an embodiment of a decoder in accor-
`dance with this invention for decoding the data bits
`which were coded in accordance with the method
`hereof;
`FIG. 5B is a logic table explaining the operation of
`the demodulator of this embodiment;
`FIG. 6 shows a portion of the decoder provided for
`detecting a sequence of synchronizing bits; and
`FIG. 7 shows a frame—format of information struc-
`ture of an encoded signal according to this invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`With reference to the drawings, FIGS. 1A and 1B
`illustrate the general scheme of this invention for encod-
`ing words of binary data (FIG. 1A) into a sequence of
`channel words of binary bits (FIG. 1B). As shown in
`FIG. 1, the original data are considered as a sequence of
`eight—bit serial words BD;-1, BDi, etc. As shown in
`FIG. 1B, for each data word BD; there is generated a
`corresponding coded channel block BC,‘ formed of a
`fourteen-bit information block BI; followed by a three-
`bit separation block 138,-. In this example, the eight—bit
`data word BD; of the form (10011011) is transformed
`into the information block 131,- having the form
`(10000100100001). A three—bit separation block BS,- is
`included, as aforesaid,
`to ensure that
`the (d,k)-con-
`straints are not violated, and also is selected such that
`the DC imbalance of the resulting encoded signal
`is
`minimized.
`
`Also, as aforesaid, the “1” data symbols in the coded
`channel blocks BCicorrespond to a transition occurring
`at the onset of a bit cell, while the “0” symbols corre—
`spond to the absence of such a transition. Consequently,
`a waveform WF, as shown in FIG. 1B, is provided to be
`transmitted or to be recorded on a magnetic or optical
`medium. Each bit cell has an interval duration T.
`In general, the data words BD; consist of m data bits
`and each such word BDicorresponds to one of 2’" possi-
`ble bit sequences. Also,
`in general, if a small d-con-
`straint and a small k-constraint are to be satisfied by an
`encoded signal,
`the bit length m of the information
`blocks BI,- must be selected large enough so that there
`are at
`least 2’" possible combinations of “I" and "0”
`symbols which will satisfy the (d,k)—constraints Conse—
`quently, the information blocks BI; have a bit length of
`in bits of sufficient size so that there are at least 2’"
`satisfactory combinations of bits which can be utilized
`for coding. In this example, where m=8 and n|=l4,
`only 256 words need to be selected from a total of more
`than l6,000 possible information blocks B15, and the 256
`possible 8—bit data words BD; can be mapped, one-to-
`one, into a corresponding set of 256 information blocks
`81,- satisfying the (d,k)-constraints.
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Generally, it is arbitrary which of the 277 satisfactory
`information blocks Bliwill correspond to the respective
`256 possible data words 8D,, the principal consider-
`ation being that the encoded signal must be unambigu—
`ous.
`
`In addition to ensuring that the (d,k)—constraints are
`satisfied, the separation blocks Bsishould be selected so
`that they will act to minimize any direct current imbal-
`ance. It should be recognized that for some catenations
`of information blocks 31,-, a unique format for the sepa-
`ration block BS; is necessary to satisfy the (d,k)-Con-
`straints, but for the large majority of such catenations,
`there are several formats of the separation blocks BS,’
`which can be used. The number of alternative separa-
`tion blocks BS,- which can be used in a catenation of
`successive information blocks BI; and BI,-+1 is referred
`to as the “degree of freedom” of the separation block
`BS,~. This degree of freedom can be used to advantage in
`minimizing the DC imbalance.
`
`LSI Corp. Exhibit 1032
`
`Page 9
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LSI Corp. Exhibit 1032
`Page 9
`
`

`

`4,501,000
`
`5
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`7
`The existence of the DC imbalance can be under-
`stood by consideration of the waveform WF represent-
`ing the encoded signal. The information blocks 31,- as
`shown in FIG. 1B are transmitted or are recorded on a
`recording medium, for example in the form of a non-
`return-to-zero-mark (NRZ-M)
`format. As aforesaid,
`with this format a “l" is represented by a transition at
`the beginning of the relevant bit cell, while a “0” ap—
`pears as the absence of such a transition. The bit se-
`quence of the catenation of information block BI,. and
`separation block BS,- has the form of the illustrated
`waveform WP, and it is this waveform WF which is
`transmitted or recorded. The waveform WF will have a
`direct current imbalance to the extent that the positive
`portions (i.e., those portions following an upward tran-
`sition) exceed the corresponding negative portions (i.e.,
`those portions following a downward transition). If, for
`example, the levels of the waveform WF are at values of
`+1 and —l, the imbalance is then Just equal to the
`running integral of the waveform WF.
`The measure commonly used for the DC imbalance is
`the digital sum value (DSV). In the example of FIG. 1B,
`the DSV is +6T, where as aforesaid, T is the length of
`one bit interval.
`When such sequences are repeated, the DC imbal- 25
`ance will increase. Generally, the DC imbalance will
`result in a base line movement, and will reduce the
`effective signal-tomoise ratio. Consequently,
`the reli-
`ability of the detection of the recorded signals is im-
`paired.
`Accordingly, the separation blocks BS,- are selected
`so as to minimize the DC imbalance. This is achieved
`generally according to the following scheme. A partic-
`ular word BD; of data bits is supplied, and such word
`ED; is converted into a block of information bits B1,:
`This can be done by means of a table stored in a ROM,
`or can also be achieved by processing the data word
`BDithrough a battery of logic gates. Thereafter, a set of
`possible channel blocks BCiof (m + n2) bits is generated,
`each such channel block consisting of the information
`block BIiand one of the possible separation blocks B8,:
`In general, there are 2'll possible combinations of “l"
`and “0” which can be used for the separation block 88,-.
`However, in this case, where a til-constraint (d =2) must
`be satisfied, and n1=3, only four possible separation
`blocks need be considered (000, 001, 010, 100). Conse-
`quently, in this example, four different channel blocks
`BCiare considered. Then, for each of the possible chan-
`nel blocks. it is determined whether the channel block
`in catenation with the next adjacent channel block will
`satisfy the d—constraint and the k—constraint. Thereafter,
`the DSV for the channel block BC,- is calculated.
`For those channel blocks BCiwhich satisfy the (d,k)-
`constraints, that block BC; is selected which will serve
`to reduce the cumulative DSV. In principle, it is possi-
`ble to select that channel BC, whose DSV is closest to
`zero. However, it is preferred that that channel block
`BCibe selected for which the accumulated DSV of that
`block BC; with any preceding channel block BC, will
`cause the absolute value of the accumulated DSV to
`decrease. Then, the selected channel block BC,- is trans-
`mitted or recorded.
`It should be appreciated that in the method of this
`invention,
`the separation bits, which are already in-
`cluded for other purposes, can now also be used rather 65
`straightforwardly for limiting or reducing the DC im-
`balance. Because the method of this invention does not
`intervene in the transmitted signal, but effects changes
`
`8
`only in the separation block Bsiwithout extending into
`the information blocks 131,-,
`this method imposes no
`additional burden on decoding apparatus for receiving
`the transmitted signal or for playing back the recorded
`signal. In other words, the demodulation ofthe played
`back recorded signal (or the received transmitted sig-
`nal) only relates to the bits in the information block B1,,
`and any data patterns occurring in the separation blocks
`BS,- can be disregarded during decoding or demodula-
`tion.
`
`FIGS. 2A and 2B illustrate variations of the signal
`encoded according to this invention.
`FIG. 2A shows, schematically, sequences of channel
`blocks BC;_|, BC,-, BC1+1,
`.
`.
`. These blocks are each
`formed of an information block and a respective separa-
`tion block BS;-2, BSi_i, B5,, or B81“. Each informa-
`tion block consists of a predetermined number m of
`information bits, and each separation block Bsiconsists
`of a predetermined number n2 of separation bits. Thus,
`each channel block consists of (n|+n2) bits.
`In the encoded signal as illustrated in FIG. 2A, the
`DC imbalance is determined across several blocks, for
`example, across a superblock SBC; formed of two suc-
`cessive channel blocks BC,- and BC,-+1. The DC imbal-
`ance is determined in a manner similar to that described
`for the embodiment of FIG. 1, except that the possible
`channel blocks BC,; BC;+1 for each superblock SEC,-
`are all considered in combination with one another to
`determine which possible separation blocks BS,- and
`BS,-+1, each of n2 separation bits are to be used. That
`combination which minimized the DC imbalance is then
`selected. This variation has the advantage that the re-
`maining DC imbalance has a rather uniform character,
`as the separation block BS; and BS,-+1 are determined
`jointly.
`An advantageous variant of this method has the dis—
`tinctive feature that the superblock SBC; (FIG. 2A) is
`shifted one channel block only after the DC imbalance
`has been minimized. This means that each block BC;,
`which is part of the superblock SBC,-, is processed and
`that
`the subsequent superblock SBC1+| (not shown)
`contains the blocks BC1+1 and BCi+z (not shown) for
`which the above-described DC-imbalance-minimizing
`operation is performed. Thus the block BCHI forms a
`part of both the superblocks SBciand SEC“. 1. It is then
`possible that the initial choice for the separation block
`SBI+1 differs from the ultimate choice thereof as made
`in the superblock SEQ-+1. As each separation block is
`assessed several times (twice in this example), the DC
`imbalance can be reduced considerably, and the signal-
`to-noise ratio can be improved markedly.
`FIG. 28 shows a further variation in which the DC
`
`imbalances determined for a superblock SBCj, which, as
`shown in FIG. 23, includes four channel blocks BC}”,
`8%”, BC/m, and BCJW. Each of these channel blocks
`includes an information block of in information bits as
`well as a separation block ofa predetermined number of
`bits. However.
`the number of separation bits in the
`respective separation blocks B51“), 851(3), 851(3), and
`88]“) is not the same for each channel block. In this
`example, the channel blocks BC/lll through BCJO) have
`two bits while the separation block B514” associated
`with the final channel block 8C1“) has six bits. The DC
`imbalance is determined in a manner similar to that
`described above for the version of FIG. 2A.
`In addition to the advantages already mentioned,
`which advantages also apply here, the version of FIG.
`213, which includes one relatively long block of separa—
`
`LSI Corp. Exhibit 1032
`
`Page 10
`
`LSI Corp. Exhibit 1032
`Page 10
`
`

`

`9
`tion bits, increases the'number of degrees of freedom
`available within the final separation block BS/‘U, and
`thereby increases the power ofthis method for reducing
`DC imbalance. More specifically, any remaining DC
`imbalance in a sequence of channel blocks each of
`which has an equally-long separation block (for exam-
`ple, of 3 bits) will be larger than the rem