3.394.352
`R. WERNIKOFF ET AL
`July 23. 1968
`METHOD ILF AND APPJKHRTUS FOR CODE CUEMUNICATION
`
`Filed July 22, 1965
`
`S Sheets-Sheet
`
`I
`
`
`
`
`
`NUMBERor-'OUTPUTSIGNALSFROMEACHENCODER
`
`
`
`
`
`
`
`INFORMATION
`3OU'.'?C E
`
`
`
`\
`
`x
`
`L“
`
`w<_:oMn~4c: SOURCE ‘SEQUENCE
`
`Fl
`
`‘B
`
`rzoasrzr wean/fi%£F~{-‘ma
`PAUL EPSTEH-J
`WILLIAM F-SCHPIBER
`
`BY
`
`ATTORNEYS
`
`Oracle 1012
`
`Oracle 1012
`
`

`

`3394352
`R, WERNIKOFF ET AL
`July 23. 1968
`!'I!ET'HOD CF AND APPARATUS FOR CODE COMMUNICATION
`
`Filed July 22, 1965
`
`3 Sheets-Sheet E
`
`I '
`
`'
`
`I
`
`c cuuucooerr.)
`°
`
`‘k
`
`FIG. 2
`
`
`
`
`-4 I >5“!
`
`Sources '5‘s’MI30L5
`
`co
`
`ck
`
`:I -
`
`1
`I
`I
`I
`|5LoI=-Es
`IUNCI-h\NGED|
`
`
`
`
`
`
` l NUMBER0|‘-‘OUTPUTSYMBOLSAFTER
`RESETTINQ
`
`x,
`
`X
`X2 5
`
`x
`
`x
`4
`
`f
`POPULATION
`SWITCHED
`
`>35 13
`
`‘I
`
`F|Q.5
`
`INVENTORS
`rcorssrzr wERNII<oFr=
`PAUL EPSTEIN
`WILLIAM E SCHFI.[BER
`ey
`‘7£¢..'.g_.rMd’£¢.-an
`NWORNEVS
`
`
`
`2:
`
`2 r
`
`-P9
`§§
`Eu
`3%
`SE
`:9
`2‘:1
`2
`
`X,
`
`*3
`
`*2
`
`
`
`
`
`
`
`

`

`3,394,352
`R. WERNIKOFF HAL
`July 23. 1953
`METHOD OF AND APPARATUS FOR CODE COMMUNICATION
`
`Filed July 22, 1965
`
`8 Sheets-—Shee‘E :5
`
`0
`F3
`
`_u.>
`
`Ha.LSA$ ON LL_:_Wm0:|
`
`.Lfid.LflO
`
`
`
`
`
`
`
`_:
`'1".
`I!
`>(
`1-
`I‘ u_|
`3u_ :" 33;»
`'* at; g-:3 9
`
`-go *3}:-
`3,
`
`3"’
`
`FIGURE 4
`
`«
`
`
`
`-1'
`
`uuvsmoras:
`ROBERT WERNIKOFF
`DAUL EDSTEIH
`wl um scumsaaar;
`"Am.2NE,2““’?”~“
`
`
`3'
`
`ll 5!‘.
`
` 3 {D
`
`FIXEDVOLTAGE
`
`
`
`
`
`STOPBUFFER,FULL
`
`2
`
`
`
`3|
`
`

`

`3,394,352
`R. wznnn-(OFF ET AL
`July 23, 1968
`METHOD i.'F AND APPARATUS FOR CODE CEMMUNICATIDN
`
`Filed July 22, 1965
`
`8 Sheets-Sheet
`
`«1
`
`SELECT OU'l'PLlT POSITION
`
`.24‘
`
`
`
`
`u w
`
`E
`Q :2
`g 1!‘-
`: 5
`Z n.
`9 %
`2*
`oz 8
`i- 2
`V‘ UJ
`Z :1
`
`FIGURE 4A
`
`INVENTORS:
`ROBERT WE|?.NlKoFF
`PAUL EPSTE IN
`WILILIAM F SCHRIR F3
`
`ATI"Ol2NE‘1’$‘
`
`8u
`
`
`
`\
`
`
`
`Z0
`
`2 L
`
`
`» E
`E:
`SWITCH
`T5
`
`3 E,
`TRANSMITIEK
`g.
`E-\ é
`3 J
`ALTERNATE
`D u]
`OUTPUT
`O I‘—’
`POSITION
`
`

`

`3,394,352
`R. WERNIKOFF ETAL
`J1-I1)’ 23. 1953
`METHOD OF AND APPILRATUS FUR CGDE COMMUNICATION
`
`Filed July 22, 1965
`
`8 Sheet'5—S11eet
`
`5
`
`DECO DE D
`5\’ME>DL
`OUTPUT
`
`FIGURE 4B
`
`INVE rnuzs :
`
`ROBERT WERNIKOFF
`PAUL EPSTEIN
`WILLIAM F. SCHFHBER
`
`A'l"TD13.N EYE
`
`3?
`
`

`

`re:-: El’ AT :=uu_ coum
`
`IN‘rEru§LIf‘r1uC.. Duu.*$E ¢53'
`
`PULSE
`**£2.:=“
`5°
`
`rum. coum
`cg
`
`59
`
`END oF
`PIcTul'tE
`
`VERTICJAL
`sweep
`COUNTER
`
`unrzmnrv
`
`,;$%IégNTM
`
`“
`VERTICKL
`5""EE"‘
`
`TE
`
`E ‘J; I‘
`W“ ‘T3?
`s%:°g3—.%E%
`“'°§D'h-1'-:|3gmH worm J
`"—' BUFFER Courrrall
`Lewcm
`°”
`“
`'
`-a
`,
`as
`34
`II ‘L
`
`‘B
`
`TUBE
`XAMNED
`
`F|C_.5
`
`—
`3,. 212-..'n.a..nfl-ca
`Arron.-uvs
`
`wx-'£zvm/P;
`ROBERT WEIZNIICDFF
`PAUL EPSTEIN
`\l.m_|_mM 5c|.4|'gE|{-_!,E[z‘
`
`"I
`
`‘:1Lo
`
`E‘H!
`N
`5
`
`°°
`29
`E
`5;
`g
`
`Q.’
`
`
`
`
`
`ROH.'n‘:'IlNI13Mi.1:J':lI'.1{J3H05Sl"I.LVHVdd\"cmJ9COHEN
`
`
`
`zs*a‘vs<.:‘2W13id°>"~H='M'39961'£z"["'l'
`
`
`
`
`
`

`

`CLOCK
`‘PULSE
`
`O ' END PICTU E.
`1"? ' _
`
`[ac
`
`
`
`E9513‘aaKtnrP3I‘l'.:l
`
`as
`U‘3U
`:-
`1
`3
`E‘
`r
`
`\‘HVd'.I'Vd'UHVJ0EIOI-|.l.3W
`
`
`.‘i0I.[YiJII{IE‘I?l?l'J33:I;r;)H03an;
`
`
`
`996:‘£251"!‘
`
`
`
`
`
`'rv.L3:Iso>IINH.'=IM'u
`
`Z99'f"5£'E
`
`, NEnA1u"_
`IOU
`
`START "2
`
`QTUP
`
`I05
`
`528 1 RESET
`FINLSH LINE
`I-ce.‘3‘é‘ca5A~'?au “"°""“%'EFf* =:.
`H
`CDUN
`IZDNTAL
`_lI- =~~=wT
`—
`
`
`
`0H
`
`
`
`TOR.
`
`QEMO-Dun‘.
`Ton
`I
`I
`D
`WPUT
`
`bl nalgg-'risT2rt
`‘W 1-
`SYNC
`DETECTOR
`
`I07.
`
`D3
`
` '
`
`"
`
`Com’
`wygyragy
`rzonenr \lJEI'?.N|i(DFF
`PAUL EDETEIN
`WILLIJKM KCHREIBER.
`
`‘Y z?I—I-uI'-.Ira-H ir-use
`,¢ 1-for HE ‘rs
`
`

`

`3.394.352
`R. WERNIKOFF ET AL
`July 23. 1968
`MEIHOD -1’-"' AND APPAFMTU5 FOR CODE COMMUNICATION
`
`Filed July 22, 1965
`
`B Sheets—Sheat 8
`
`
`
`C.’
`m
`$-
`+- 2'
`§§
`ga
`:rfl
`3
`u-
`
`LU
`§+“!
`5&5}
`E
`
`E3
`Sr.‘
`5 E
`g%
`
`""
`
`£3
`“*7
`L5
`L:
`
`-
`
`/NVENTORI
`RoaeRT\MHUumDFP
`PAUL Epsrrem
`NILLIAM r. scnmafin
`av fi%é4.a4'fi£ua,
`.4zrorexvEv5
`
`O
`1
`
`0W
`
`B’
`L11 0
`_.
`3 gt;
`w 2:
`51%q
`A 8
`
`3
`0
`
`:93
`
`‘£4
`2283
`333E
`;~::e
`33:3’
`ll-l9!-.1
`IP53
`
`figmg
`a
`2
`‘I
`
`

`

`3,394,352
`United States Patent Office
`Patented July 23, I968
`
`1
`
`2
`
`3,394,352
`METHOD OF AND APPARATUS FOR CODE
`_
`C0l\rIMl.lNICA'I'lDN
`Robert Wcrniltotl, Cambridge, Paul Epstein, liroolrbne,
`and William F. Scbreiber, Lexington. Ma.ss._. afiigrtors
`to Electronic Image Systems Corporation, Boston,
`Mass, a corporation of Massachusetts
`Filed July 23, 1965. Ser. No. -$14,189
`35 Claims. (Cl. 34tl«—l‘12.5)
`
`ABSTRACT OF THE DISCLOSURE
`
`The methods and apparatus disclosed minimize the
`number of symbols to be transmitted, and hence the trans-
`mission time, in a communication system, by determining
`the most cflicient code for encoding sequences of message
`symbols and transmitting the symbols in that code. Deter-
`mination of the most eflicient code can be accomplished
`by applying the message symbols to a plurality of encoders.
`counting the numbers of symbols of coded representations
`of successive message symbols produced by each encoder,
`and comparing the numbers to determine the particular
`code that introduces the smallest number of symbols of
`coded representation consistent with distortionless mes-
`sage transmission. Tagging symbols are transmitted to per-
`mit reconstruction of the original message symbols from
`the transmitted coded symbols. In an application of the in-
`vention to facsimile transmission run-length coding is em-
`ployed.
`
`The present invention relates to methods of and appa-
`ratus for code communication, being more particularly,
`though not in all cases exclusively, directed to clficient
`coding for inhomogeneous sources of information.
`The problem of processing information-to-be-communi-
`cated so as to enable a minirnum number of symbols to be
`transmitted with -reliable recovery of the information has
`long challenged the art. In devising his telegraphic code
`more than a century ago, Samuel F. B. Morse generally
`assigned the shortest code symbols to the most frequently
`used English alphabet letters in order to economize on
`the transmission time of niessages. Had Morse optimized
`the assigning of the shorter codc symbols to the more fre-
`quent letters. this would have produced about it fifteen per-
`cent saving in transmission time over assigning symbols of
`equal
`length to all
`letters. For greater saving. however,
`could have been effected by assigning code symbols. not
`for individual
`letters, but
`for pairs.
`triplets or other
`grouping of letters that in normal text occur much more
`frequently than others. Within recent years, indeed Claude
`Shannon has estimated that the ninxirnnm saving in trans-
`mission capacity that can be obtained through optimum
`ecodirtg of English text is about seventy-five percent when
`statistical dependenccs between successive letters of text,
`carried out to one hundred letters. are considered.
`When the symbols issuing from the information source
`are statistically dependent upon one another, so that cer-
`tain groupings of symbols occur more frequently than
`others. efficient coding requires that the symbols be con-
`sidered not singly but in groups. The number of elements
`of which the group must consist is dictated by the range
`of substantial statistical dependence. It might amount to
`ten or twenty letters in English text, and to several thou-
`sand bits in pictorial transmission. The size of the code
`"book in which groups of source symbols are assigned
`code symbols increases fantastically as the group is made
`larger
`(the number of entries
`in the code. book is
`2?"'_='.!fJ5.9DD,U00,|JDD,t]t}0 for groups of
`ten English
`letters. and it is the square of that number for groups of
`twenty letters) and this growth soon becomes an insur-
`mountable practical limitation to optimum coding. There
`
`this problem.
`are no non-singular codes that circumvent
`An optimltm code is matched as closely as possible to
`the statistical peculiarities of the population or set of se-
`quences to be encoded. A code designed to match the letter
`frequencies of English text, for example, becomes quite
`incflicient when it is applied to J. different population or
`set of sequences, such as a foreign language. Whenever dis-
`similar populations are ruined {for example, for the pur-
`pose of obtaining a single set of letter frequencies applica-
`ble to English and to a foreign language simultaneously]
`the frequencies of the letters tend to equalize: and any
`operation on sequences that cqualizes probabilities reduces
`the possible compression, In the limit.
`indeed, if an in-
`formation source is as likely to produce one symbol as
`another. and if successive syntbols do not depend on
`previous ones, then no compression whatsoever is possible.
`The reduction of transmission time by means of coding
`is thus possible only to the extent
`that the statistics of
`the strings of symbols produced by information sources
`differ from independence and equiprohability. The recipe
`for the optimum code is fixed in a deterministic. mathe-
`mulical way by the precise probability distributions that
`describe the information source.
`While it
`is dilficult to reconcile language text. televi-
`sion, moving pictures,
`facsimile.
`telemetercd data. ctr...
`with the ntathcntntical idea of a homogeneous population
`with a fixed, immutable and known frequency iiistribtttion,
`yet this abstract concept underlies all prior coding t|‘.e:Jry'.
`In accordance with Shannon's theorem, an information
`source is contemplated that produces sequences of sym-
`bols {but not just any sequence} that may be regarded as
`ruudoilt samples from :1 homogeneous population tvitlt
`ltnown and immutable frequency distributions of all or-
`ders (i.e., for pairs of symbols,
`triplets,
`.
`.
`..
`it-tttplcs).
`The term “homos_:,cneotIs"
`(the technical word is "er-
`godEc“|
`implies that any sufficiently long sequence from
`the source is very lilmly to be representative of any other
`source sequence.
`Adherence to this framework has, however, resulted
`in prior—art coding and compression systems that fall far
`below the ultimate transntission cfficiency. The reason is
`that tbc niathcmatical framcworl-.' on which they are based
`liI'.'It‘.'5 not sulficicntly resemble reality. In accordance with
`the present invention, on the other hand, as pragmatically
`determined from actual experiment.
`it
`is not assumed
`that
`the population of symbols {letters of text, or ele-
`ments of television or facsimile pictures, for example) is
`a homogeneous source in the sense of information theory:
`but. rather, that inhomogeneous sources are involved re-
`quiring a novel coding logic that has been found in prac-
`tice to more than double the average compression at-
`tained by prior—art systems implementing conventional
`coding theory, and with less equipment. In addition, the
`coder for inhomogeneous sources, underlying the inven-
`tion, results in a transmission time that never exceeds the
`uncoded time and sometimes is fifty times smaller.
`An object of the invention. thus.
`is to provide a new
`and improved method of and apparatus for code com-
`munication that is not subject to the abot-e—descri bed dis-
`advantages of prior—art coding and compression systems,
`predicated upon conventional coding theorems: btlt that,
`to the contrary, provides for greater transmission-time
`efficiency and with less complicated and costly apparatus.
`A further object is to provide a new and improved Scan-
`ning transmission and reception system for such purposes
`as facsimile or other conununication. all generically re-
`ferred to as “picture" scanning and the like-
`Still another object is to provide each of a novel code
`transmission and reception apparatus.
`Other and further objects will be made apparent herein-
`after and are more particularly pointed out
`in the ap-
`pended claims.
`
`10
`
`20
`
`25
`
`30
`
`-ill
`
`-15
`
`50
`
`55
`
`00
`
`E5
`
`70
`
`

`

`3,394,352
`
`5
`
`ll)
`
`-.
`
`3
`4
`The invention will now be described in connection with
`. Cn.
`each of the different encoders or coders C9. C1, C1 . .
`the accompanying drawings, FIG.
`IA of which is a
`In view of the fact that all possible source populations are
`schematic block diagram of a portion of a transmitter
`not known.
`it
`is useful
`to include one encoder Co that
`useful with the invention;
`performs pure, uneoded transmission; its output is identi-
`FIG. IE is a graph illustrative of the performance of
`cal with its input. We shall call this the null encoder. As
`the system of FIG. IA;
`each successive source symbol enters a given encoder, the
`FIGS. 2 and 3 are similar graphs of modified perform-
`encoder output (which may differ from all the rest) will
`anee;
`be of several different
`types. The output may be "no"
`FIG. 4 is a block diagram of a preferred generic en-
`symbols (if that particular code works on blocks or source
`coding and transmitting system embodying the invention:
`symbols, and the end of the block hasn't been reached
`FIG. 4A is a block diagram of the output
`lOt'rn.llIi[tg
`yell: ‘hr it may he one symbol [as in the null encoder C9
`system of FIG. 4;
`and others}; or it may be many symbols (as in a coder
`that has reached the end of a block or of a run of source
`FIG. 41-!
`is a similar diagram of a preferred generic
`decoding or receiving system for use with the transmitting
`symbols). In FIG. 1B, accordingly. there are plotted the
`system of FIG. 4, FIGS. 4, 4A and -13, as a unit, together
`numbers of symbols issuing from each coder as successive
`constituting a complete system employing the invention;
`source symbols enter it from the source S.
`FIGS. 5 and 5A are block diagrams of the transmitting
`If the population statistics are truly stationary. each
`and receiving sections. respectively. of a preferred fac-
`coder will be characterized by an average strnightlint:
`simile or similar scanning system using the novel
`tech-
`behavior whose slope at determines the compression (or
`niques of the invention as a species of the generic con-
`expansion] produced by that code. The null encoder Co
`cept of FIGS. 4. 4A and 4B: and
`has unit slope if the input and output alphabets are the
`FIG. 5B is a circuit modification that may be employed
`same. because it puts out one symbol for each successive
`with the system of FIG. 5.
`input symbol. If the input and output alphabets are differ-
`Considering for purposes of illustration an information
`ent, the one at the input having A, letters and the one in
`source that produces sequences drawn not necessarily
`the output AD letters, then the previous statement is still
`from one homoge neous population, but possibly 1' rom sev-
`correct after all ordinate values have been divided by log
`eral different populations. some known and others perhaps
`A;/log An. In the sequel.
`it is tacitly assumed that the
`not yet identified, and considering that the source may
`alphabets are equal or that the indicated normalization has
`switch from one population to another at random and
`been done. particularly since a change in alphabets does
`without stopping; that the dilfe rent populations are used in
`not change the channel capacity required for message
`unknown. and maybe even in variable proportions; and
`transmission and hence does not affect ctficicncy.
`that switching from one population to the next occurs at
`Coder C1 in FIG. IA may. as an illustration. produce on
`random times. an E)ti]l'tI]‘|iE of the method underlying the
`the average fewer symbols than enter it; thus. it produces
`present invention may be constructed as follows. For pur-
`-a. characteristic shown in FIG. IE of slope m,<.l. Coder
`poses of illustration only. it may be considered that this
`C‘..., on the other hand, may produce on the average more
`operation occurs when different-language messages are
`than one symbol per
`input symbol, producing a slope
`successively transmitted from United Nations Headquar-
`w,,>l. These statements apply to the average behavior of
`lers.
`the coders. shown as the dash lines in FIG. 1B. The actual
`Since it is known how to gain at useful compression in
`number of output symbols put out by each coder for each
`any one language (or. more generically, population). it
`input or arriving source symbol
`is, of course, a random
`is proposed to construct an apparatus that elfectivoly has
`variable whose value depends on the specific source sym-
`a collection of encoders, one matched to each language
`bol that entered the coder (these symbols are themselves
`(or population}. Then, as the source switches around
`random variables} and on the source symbols that entered
`from one language {or population} to the next, the ap-
`the coder earlier. The actual number of symbols issuing
`paratus automatically follows and, at each instant. rises
`from each coder, as represented by the solid lines in FIG.
`the code best suited to the output of the source. Fach time
`13. thus. is a random walk or step—eurve about which the
`the coder switches codes, it sends a special signal to the
`most that can be said. in general, is that it is monotonic
`receiver indicative of the code of the following message.
`nondecreasing.
`so that
`the receiver can apply the corresponding dc-
`when the SDttt'CI: S abruptly Switcltcs populations‘ 55
`coding procedure and recover the original message. The
`that the source sequence has entirely dilierent statistics, the
`problem is. however,
`to enable the coder to determine «
`dash-line curves of FIG.
`113
`that describe the average
`when the source switches populations. The coder must
`behavior of the coders will abruptly change slope. since a
`determine this as soon as possible. so that it may switch
`coder which formerly was quite efficient to-<1} may now
`codes promptly before any great
`loss in transmission
`be very inefticient fw>ll. Automatic code-switching can
`etficiency has been incurred.
`be based on detecting changes in slope in the average
`What makes the problem difiicult is that the conditions
`behavior of the coders (ie.. the ratio of Dulpttt to input
`of this oversimplified illustration, in which it is possible to
`symbols or the number of output symbols per unit of real
`think of the source as switching around among a finite
`time) and such operation in the system of the invention is
`and definite number of discrete populations, are not often
`for some purposes feasible; but it is preferred, because the
`realized in practice. It is more usual to Find real sources
`average behavior is not known with any acceptable ac-
`changing their behavior in a continuous way. and to find
`curacy unless the source persists in its new hehavior for a
`the statistics of the corresponding source sequences assum—
`very long time, not to rely upon mere slope detection.
`ing a continuum of values; thus there does not exist. even
`What is really available, as opposed to merely assumed.
`in principle. a unique. well—defined time at which codes
`is the actual output front each coder: i.e.. the solid-line
`should be switched. The present invention provides the
`step curves of FIG. 1B. The randomness of these curves
`solution both for the simple case of switching among
`makes the ntousttrement of slopes unreliable. and masks
`discrete sources and for the more important and realistic
`the precise point at which the switch in populations oc-
`case of gradually changing source statistics; but the meth-
`curred: and there
`in fact. no such point with real
`od and apparatus of the invention are more clearly under-
`sotlrccs, whose population parameters cltange gratluttlly.
`standable if initially described in terms of the simpler case.
`rather than abruptly. Thus any code-switching systems
`Since it is not known which population the source is
`based on slopes or other population averages. such as
`currently drawing its sequence from, according to the
`entropy. would at best merely be crttde npproatimatlons.
`present invention. the message sequence from the informs»
`lion sottrce is fed simttltnnoottsly to all cncortlers. Titus.
`ln ttccnrilttncc with the ]"tT|.‘rt.'l‘Tt.’I.l lortn of the prcsettt
`invctttion. tltt:t'cl'oic. lltc L"tJ(it.‘~5\v'-iit.‘i‘liI'lg.!
`lupin: is i‘1l\CLl, not
`in FIG.
`IA.
`the sequence of infornuution source symbols
`.\'1,
`.1";
`.
`. Km .
`.
`.
`is shown ictl
`from the sottrcc S to 3;, on .tlt.'ilI‘tIL'l. c‘UJ‘ta'lt't.I\.‘lS iiitc tivctulgc slopes or on t..tnstIp-
`
`L‘! GI
`
`30
`
`-ll]
`
`50
`
`.
`
`

`

`3,394,352
`
`5
`ported assumptions about physical] sources, but on the
`final goal of the coding system, which is to transmit as few
`symbols as possible without distorting the information
`produced by the source. Attention is thus focussed on the
`symbol counts at the outputs of the encoders; and at any
`given time.
`that encoder is chosen which leads to the
`fewest transmitted symbols. This operation can be imple-
`mented in a manner now to be described.
`it must
`Each time the transmitter S switches codes,
`convey this fact to the receiver; that is. the transmitter
`must tell the receiver which code it will be using next.
`The accomplishment of this function requires transmitting
`a few symbols, representative of the name of the new
`code. if the transmissions are in binary alphabet, then it
`takes one symbol to identify one out of two possible
`codes;
`two symbols to identify one out of four possible
`codes‘. three symbols for eight possible codes; and so on.
`Each additional symbol doubles the number of codes
`that can be identified. With a quaternary alphabet, one
`symbol identifies one of four codes; two symbols, one of
`sivtteen codes: and so on. Each additional symbol quad-
`ruples the number of codes that can be so identified.
`Since, in most applications, it
`is unlikely that a practical
`system would have more than a dozen or two different
`codes, it never takes more than -three or four symbols
`to identify the new code. The receiver. however, is con-
`fronted with a continuing stream of symbols and it will
`not be able to distinguish between ordinary message
`symbols and code-switching instructions unless special
`provision is made to provide such instructions in an un-
`ambiguous manner. This may be done by inserting in the
`nicssage stream a ttniquelydecipherable tagging word
`which is the same in all codes and -which informs the re-
`ceiver that the irnmedi-ately following symbols define the
`new code. To eficct this requires a few symbols. say ten
`or so. The switching signal.
`therefore, may consist al-
`together of fifteen symbols or so,
`this being short com-
`pared with most intervals or source homogeneity. Since
`some transmission time is consumed by sending instruc-
`tion or tagging words, however, the number of transmitted
`instruction or lagging symbols must -be noted.
`In fut:-l. in accordance with the invention. it is the trans-
`mission cost of the instruction or tagging symbols that
`supplies the discriminant for the code-switching decision;
`that is, codes are switched precisely -then, when what is
`saved in transmission cost by replacing the old code -with
`a new one just exceeds the cost of sending the instruction
`or tagging word -that announces the change.
`Assume that the information source S is allowed to feed
`source symbols to the encoders, as in FIG. IA. and that
`there are buffers.
`later described,
`inserted 'l3el.\»\-1‘:Bl'I
`the
`encoders and the transmitter output so that time is al-
`forded before it tlecision is made as to which coder output
`is to -be
`transmitted. As successive source symbols :1.
`X;
`.
`.
`. etc., enter the coders,
`the number of symbols
`coming out of each coder is counted. presenting an out-
`put -that,
`if plotted,
`is of the type shown in the graphs
`of FIG. 113. If, for purposes of explanation, the graphs
`are temporarily thought of -as smooth lines. as shown in
`FIG. 2, rather than as random walks or steps.
`then, as
`the source syrrzbuls x1, 1:,
`.
`.
`. ctl:., enter the coders
`C0. C1 .
`.
`. etc., the graphs represeative of output sym-
`bol counts will begin to diverge from each other. If com-
`pression is at all possible, one or more coder lines (for
`example, Ck in FIG. 2) will be below the null—codcr
`line CD, so-labelled.
`Assume that, as a convention, the receiver always pre-
`supposes that transntissions commence uncocled (i.e., using
`the output from CL.) unless the very first received word is
`a code-instruction or tagging word. The transmitter, be-
`fore sending any thing, first examines the outputs from the
`various coders as they enter the later-described buffers
`that prccctlc the output register, with the following ob-
`jcctivc.
`
`ID
`
`15
`
`20
`
`30
`
`35
`
`40
`
`C2!.'_.1
`
`60
`
`70
`
`. etc.,
`
`-the .-smallest
`
`6
`.
`.
`.t‘r_a
`In Ilic sotIt't.'c scqucncc I1,
`source—st1l1-script u is sought sttcb that
`(1)
`Ckl.r_,. .r_}<Co(.1',. .tr_,}——2H
`for some it‘. where H is the number of tagging symbols
`that rlttlst be transmitted -to change codes,
`it {initially
`zero} is the number of source symbols that already have
`been transmitted. and C‘g(.r.,, Jr.) is the number of sym-
`bols that must be transmitted by coder C3, to represent
`all source symbols starting with .ir,_,1 -and ending with
`.r,. It costs H symbols to start transmitting in C,, instead
`of Cg: but,
`if the first
`fl. source symbols are transmitted
`with the C.. code, then a minimum of 2H—H=H sym-
`bols are saved. Even at .r,,, the line for C3 veers up
`sharply and C., begins to cost more than Cg per unit
`input symbol, therefore, the transmitter can switch back
`to Cu [an operation that costs another H symbols] and
`still not
`l1:Ivc
`lost any-thing with respect
`to uncoded
`transmission.
`Thus, the code-switching logic of the invention issues
`a command that initiates transmission of a t:ode—instrue-
`-lion word identifying C1,, and of those symbols in the
`C, output buffer which correspond to the first it source
`symbols. While transmission is taking place,
`the code-
`switchiug logic allows enough new source symbols to
`enter the coders so that the logic can decide what code
`to use next before the transmitter has finished sending
`the symbols of the previous block. The object here is to
`keep the transmission line fully loaded at all t'u-nes. This
`requirement defines the minimunt computation rate for
`the switching logic. and it also defines the rate -at which
`source symbols must be supplied to the coders.
`is
`it
`To decide what code to use in the next step,
`noted that the cumulative number of symbols that the
`coders would have sent for the first
`at source symbols
`is now quite immaterial. What matters is how many sym-
`bols pcr source symbol they produce from .r_, on. Then:
`is subtracted from each line of FIG. 2,
`therefore,
`its
`value at .r,,. resulting in the graph of FIG. 3.
`it has as-
`Now the system is initially in the C,‘ code.
`sumed its new value. and -the system will stay with this
`code unless a new Cl
`is reached such that
`
`(2)
`Cii-rs. -\'.}<Cvt-ti. A'..J—2h’. for some i
`If this happens, the system transmits the symbols between
`:r,,1 and Jr,
`in code C]. If this does not -happen before
`the C3. output buffer fills up, then transmission continues
`in code Ck. The C3, buffer is emptied, all the other buffers
`are cleared. and the above procedure is repeated with all
`the coder output lines new originating from that source
`symbol which would have caused the C1, buffer to over-
`flow if the system had not just then stopped the search
`procedure.
`The method of code selection outlined above is simple
`and effective. but it occasionally results in a transmission
`cost higher than what is incurred with uncoded transmis-
`sion. A preferred method of code selection that never re-
`sults in transmitting more symbols than are required for
`uncoded transmission might be tabulated as follows:
`
`Cori:-r logic ivhcn diserimtrtrmr rqtrats EH
`
`Let M represent
`bulfers.
`
`the maximum capacity of coder
`
`Step I.—Thc value of it is initially zero as is the value
`of I in Steps 2. S and 7. Proceed to Step 2.
`Step 2.—Search for the smallest source sequence sub-
`script as such that conditions {3) and (4) are both satis-
`fied for some values of k:
`
`¢~—K$M
`
`C'1._-l.t,,. .r,l :'C'1(.r,, .t',,] -—2H'
`
`(3)
`
`(4)
`
`If no such value of an is found, proceed to Step 1; other-
`wise proceed to Step 3.
`Step 3.—Using the ct value and k value found in Step 2.
`
`

`

`7
`determine whether or not condition (5) is satisfied:
`
`(‘g_{>"\: -\'.. l:'-C'nl-\'s. -\'. 1-“
`
`(5)
`
`It condition (5) is satisfied, proceed to Step 4; otherwise
`proceed to Step 5.
`Step -'?.——-Using the El value and is value found in Step 2,
`transmit a code-instruction word,
`transmit
`the next
`at
`source symbois in code Ck. set the value of i in Steps 2,
`S and 3' equal to the value of It and proceed to Step 9.
`Step 5.—Using the at value found in Step 2, determine
`whether or not condition (6) is satisfied:
`
`5
`
`ll}
`
`Cllilxlt 'ra)i:C0{'.:1r Xe’
`
`{5}
`
`if condition (6) is satisfied, transmit the next 0. source
`symbols in code C1 and proceed to Step 9; otherwise pro-
`ceed to Step IS.
`Step t5.—Transmit a code-instruction word for code
`C.,, transmit the next a source symbols in code Co, set the
`value of i in Steps 2, 5 and 7 equal to zero and proceed
`to Step 9.
`Step 7.——Deterrninc whether or not condition (‘it
`satisfied:
`
`is
`
`Cit-lav -"it .- H l 5C0 UK: It ilk!)
`
`(7)
`
`20
`
`3,394,332
`
`8
`script at such that conditions {H} and W) are both satis-
`fied for one or more ‘values of .'r:
`
`m—:t:rt-I
`
`(|;l_t‘_,. .\',_.)<C.;l'.\'\_. x, J —2rr
`
`ts)
`
`(9)
`
`If no such value of at is found, proceed to Stop 3; other-
`wise proeecd to Step 5.
`Step 3.—Tl'tJ.I‘t!-l'I1it M source s_\,-mbols in C.-_.. Proceed to
`Step 4.
`to the total number
`the value til It equal
`Step -3'.—Sct
`of source scqtlcttcc symbols that have now been trans-
`mitted. Proceed to Step 3.
`Step 5.—Using the value of El. found in Step 2 and using
`the preferred value, relative to .\ and at ol' the set of values
`of it
`four‘.-d in Step 2.
`l.|'ilI‘I‘3:l’Ill
`:I code-instr'ttction word,
`trtmsmit
`the next
`t1 sotircc syrltbols in Ch. and set
`the
`value ofi in Steps‘ 7. S. 9,
`l2 and 13 equal
`to the pre-
`ferred value of 1:. Pi occed to Step 6.
`to the total nttmber
`Step 6.—Sct
`the value of It equal
`of source symbols that now have been trnrismltted. Pro-
`ceed to Step 7.
`5:'c‘,t¥ 7.—-Search for the srnallest sottrce sequence sub-
`script nt such that conditions {Ill} and ill} are both satis-
`fied for one or more values of L:
`
`is satisfied. transmit the next M source
`If condition (Tl
`symbols in code Cl and proceed to Step 9; otherwise pro-
`ceed to Step 8.
`Step &.—Transn1it :1 code-instruction word for code C9.
`transmit the next M source symbols in code C.,, set the
`value of i in Steps 2. 5 and 7 equal to zero and proceed
`to Step 9.
`Step 9.——Set the value of A equal to the total number
`of source sequence symbols that have now been trans-
`mitted. Proceed to Step 2.
`Using 2H, rather than H. as the discrimination level is
`ultra-conservative; its virtue being that it allows lossless
`return from any code to C, in case it turns out,
`in the
`interval following the decision intervl, that the chosen
`code and all the other codes suddenly become more inelfi-
`cient than uncoded transmission. Another way to obviate
`this danger is to monitor the interval following the de-
`cision intervttl before making a firm decision. When this
`is done, the discrimination level can be lowered from 2H
`to H. without comprising the property that the system of
`the invention never transmits more inefficiently than un-
`coded.
`
`The requisite steps for this operation may be tabulated
`as follows:
`
`Coder logic whet: discrintinortt cqttolr H’
`
`Let M represent the capacity of the coder buffers. and.
`as before. let C’.¢[it.. I“) be the number of symbols that
`must be transmitted by the kth coder to represent all the
`source symbols starting with .r,_., and ending with .v_.
`The object of the following logic is to identify that coder
`whose use results in the fewest
`transmitted symbols.
`Occasionally it will happen that two or more coders result
`in equally few transmitted symbols for at particular seg-
`ment of source symbol sequence; the logic then selects a
`specific coder by applying some arbitrary rule to resolve
`the ambiguity. an example of such an rule being, "choose
`that coder whose subscript k is least." Any number of
`other rules are admissible. In the coding logic presented
`here, occasional use is made of the term. “the preferred
`value. relative to X and n. of a set of values of it," which
`term is defined by the following rule:
`from among the
`set of coder subscripts
`it
`find the subset
`for which
`tI]t.\'_\. .t‘.l
`is least: from among the subset of values R thus
`found. find the least value of in
`Step J’.-—Tl‘Ie value of It,
`the total nurrlbcr of source
`sequence symbols that have been tr:tnsmitt'.-d_.
`is initially
`zero. Proceed to Step 2.
`.‘itt'_tt
`:.——SL‘llI'|..'ll
`lnr lltc h.~l‘IliIllt"\l.
`
`.*xL’qlls!Ilt.‘\.' wh-
`
`.'\t.JtIIL't.:
`
`as-r\_’;.’|r:"
`
`C'1.;l.t.. .r,)<C'.t.\'.,.t__)—H
`
`(10)
`
`([1]
`
`30
`
`if no such value of ix
`wise proceed to Step 9.
`Step 3.-—Dt:l'.,'1'rl1it’«|t whether or not condition {l2} is
`satisfied:
`
`is found, pI'CIC'CCI.l to Step 8: other-
`
`(II!
`Cil-tn -l‘t.1\tl:'C'.Jl.t',. .14.”)
`If condition (121 is satisfied, transmit the next M source
`symbols in C; and proceed to Step 6; otherwise transniit
`rt code-instruction word for Co transmit the next M source
`symbols in Cu and proceed to Step 4.
`Step 9.—Using the value of LI. found in Step 7, search
`for the smallest source scqttcncc :~'ltl1:r.‘ri[!l
`rt suclt
`that
`conditions (J3) and (M) are both satisfied for one or
`more values of k:
`
`-ill
`
`.'t'——lt4,s'.'l—RE.-'14’
`C'x{'r-*3 .r_,J.’-C]