aJ
`
`,-I N0. 3.wuIctt Iwt
`
`-
`
`.55: JOURNAL or‘aouo-s'rA'r: ctnottrts. VOL 26. No. 3. MARCH 1991
`
`L11‘
`
`Ill-li.T..S.}tn El-Icltodc,
`: 3.5:. d-pen in «tee.
`and the II‘. deuee In
`INS {mm the Untveu
`TllI_NO1.lIB|']|IId.L
`= Wotltint II the Uni-
`tl levels of-terpoo:ihl+
`”flbI'I1'I.fl|'lEmf
`nt"J lo the Lnbcmon
`UlIl'|I¢‘lIiI'r III Titan.
`1 temtett and ma.
`
`-
`
`A’Chip Set for Lossless Image Compression
`Irnran Ali Sltalt. Olu Axtwunti-Assam. and tam Johnson
`
`3il t
`E.53
`II-51$!
`olnpilltflllulptllllllluulll-lIIIol'
`7.tMpttatIm[d.ThtnptrtteutnnuttettueItr--tteullInl|I-
`rllIfl.thndlInI‘IIetIIlhIIIuttHbeblp|.|.|dIItll.luuue
`put-IttfiloIwu&%.
`
`'
`
`l. IN'|'RODUc‘l'l0t-t
`the
`S APPLICATIONS of Gill!!!
`ilflllfl Dfllllifetate.
`ooetormfinandnutmlnlmthetmapedhube
`a:moInoomtnotIptultlem.LnuleniIon.pcompruslnnted't-
`niquu pmvldo I penenl-pupou-. nalutinn fun of mangan-
`rnhte. The oompmnd Image is stored cu tnnentltted In
`typicallylmtltunlulltltesputeotlestthsnhelfthetimeol
`the cuisine]. Louhu oootpteaion can be Icliieved by I
`tnntfotm ptneea hallowed by entropy ending. We hm
`dniznnd mo application-spI:¢i.fi¢ itttcgntlad clmtit: (HE'S)
`to perform the .5‘ tnttslotttt [1]. I21: I hierattitlcal transfor-
`tnntion.
`and I dun Itotrtpreuot/dttcamprenor
`for
`!.:n:pol—Zlv etttruw audio: [51 [6]. The chips my be used
`indetaontlently or togethat for itattne compression. One of
`the applications of such I chip Ill ll in the medical recs
`environt-nettt [7]. The l.l.|Dl'llIlllII and chip ucltilecluroi will
`be delctibed. Sumo oi‘ the important perfionmttec parame-
`ter: will Ibo b-I tlllcttued.
`
`II. S-Ttthttsrotttt Pttocusoa
`1'lt¢p|int[pnlob,locll\tdod'lhntnnsfotmpmonsIl|ln
`uchieveupecttnlditttllnttlonolnsivensourcetipnnltttclt
`lllll molt ol its etttttu it concentrated In I subset of the
`eoeflleionu in the ttlntlottn dotmin. If the signal touroe
`ettltt'ht'u it high dance of cot-teiatiott between suooenlve
`sunples. then it follows that lot I given trtnsflorut the tignal
`enemy il cottoenmlod in I ttlnuw Ipectnl none. In pne-
`tlee. the lnttttomtn norntllly applied to image eodl.n.| Ind:
`off pnckitti ldecorrelntionl cllficlet-tey with itnplententatlon
`complexity. The 3 lrulfiolm il mttp-ul.|Iion.ttl.ly Illnple. Ild
`Illwidea I reasonable Induction olteduudancv In tho intttu.
`The tlecorteletlon lndtteetl by the S trutnlat-tn was themati-
`cllly analyzed by Lu: [I]. In [3]. thin um experimentally done
`by computing the math-ottlet euttopy
`N
`5‘ ' :.P'r1°l:t(.Pt)
`
`hlnnultxipl mollvnd Aunn 11'. 19%: rflhd November l2. 1990.
`I. A. Shall I'll wen FIIHII Llbolaloriu. North Arturitau Htilb
`Corporation. Btindlfl Mltut. NT ID610. HI ll now llllll Phlllpc lu-
`snteh Ltlzot-Itotiee. Sill M Elodltaven. The Netlterihntls.
`O.
`.I\H\VllflIlr.I\llllIl and I. Johtuon In with Philip! Llbotuoriet.
`North At-nerltan Philip: Cotpontlon. fltlareiifl Manor. NY IDSIO.
`IEEE 142: Ntttubnt HNIMJ.
`
`the trutttorm In I set of 15
`ttetme end that sppl;-tat;
`computed mttosnph (Cltl imtpee N calm to the numbet
`of tttgittzattmt limit. and p, the tztub-bllltr of occurrence It
`Vat observed that the uterus ellllflll‘ 0‘ “ll ifllvfilfl Will‘
`tltduoed {tom 8.! to 4.6 It. The S tnn.tform_‘u not Pflffi-‘I 01'
`ettutt no the Knrhuoen-boevo tnttafnntt. but it am: I mood
`Ind:-off between perfinrntenoa and simplicity of 'imnlemflI-
`mien. The trmlornt also provides at man: for hietm‘-hill
`inane teptesetttatlott. Ind has been med tat some lmue
`etthnntnmenu [S1
`
`A. S~'.l'iwt.tfon-It Algorldltil
`The S Innsfot-tn ltthefladantndtnhsfottn rut 2x2-plxzl
`intanehloolt|.ToapplytJte.SttI.n:Iorttt.nnimnmlflIusth.we
`a sieeof znxzm platelsor ho apitrnprluuly pnddfll.
`Ila. lt.c.ttttd duethepixelslntltelxzltlocltusltown:
`.a
`.5
`.e
`.4‘
`then the ta-turd u-utttonu ooefnutenu at aim bvtlh
`E-¢+b+c+d
`Ag,-I-b+.:-6
`Ay-o+lt-c-ti
`(1)
`A,-at-5-e+d
`where E is the nuooooffieiettt and the A coefllcients repre-
`tent hot-lxtantnl. vertical. and dieponal spatial. frequency nom-
`ponentt. oi’ the image.
`-
`11:: S‘ tnaufiomt ptuvltlee a flIll.1'|I
`lo hientelticully de-
`euntpoee:Ia._txe|tttue.‘l'oeehievetltis.I.lte zxzlstoeluot
`the lntqe are tnnetttt-nted_nnent-din; to (ll. reettltltt; In [our
`Iuhilnllol. one lot emit coelliclent. Eich of the Iulthmpes
`hat half the Ipntlll retolndon of In original. ‘nth transfor-
`tlllliotl tIt.i.flI most ct! the energy of the 1x2 Diul block tall!
`the E cooElit:l:111:tMll the tttstt-thntimt lot the A intent: is
`narrow and reqatl.ru liner bits lot coding. pcnnifliug better
`ontopteulon. To ieltieve ltientehlcnl decomposition of an
`ltnue. the lower spaniel-teootntion 2 bone at each my I:
`further tnntlctnted while the three A in-tapes ue entropy‘-
`ooded fat stony: ot trettttttluion. This docotttpottilion step
`can be tnccenlvely applied until : lull: louse of much lower
`resolution is achieved. This result: in I tapretentatiem coo-
`tlttlngonbuia intue. foilowetlbylayertofcoded A images
`of ihcteutnc spatial resolution (tee Fil. 1). To tuconurucl
`higher resolution Imus. the E it-nnse at a given later is
`teomnltitted with in corresponding aft according to the
`Inverse tn.t-Mort-tt equations.
`In our implementation of the S ttantlorrn. the forward
`ll‘I.I1Sfnl'Il‘I
`is computed by a slightly modified set ofe¢l1Ifl-
`
`UJIS-WZGIJ,-’°1/Dfilm-D'4‘J?50l. W O l99l IEEE
`
`Page 122 of 437
`
`Page 122 of 437
`
`

`
`
`
`IEEE JOURNAL OF SOI.lD-STATE CIRCIJIIS. VOL Je. ND. 3. Mo-IRCKID1:
`a
`
`
`
`intensity vlltlee. The block Tribllf pmvides :'.sl:tI|,|.|un
`pixel
`between inlerilll and external bum. The PCB bineict in-tplg.
`merit the data transfer ntntneol between the pipeline regu.
`ION.
`The pixel port consist: of two 1!-is ninl buses for lhg
`ruler linen {mill and [ad] with aeeerltpanyina pipeline
`control Jlmais. Thus.
`this pol‘! behave: II ileouttectee In
`two mflrlilll pipeline source: (forward transform) or in my
`branching pipeline oulptltl (Inverse Innlfetml. l.tn¢£l:a.|i1r, tin
`mefflcieui port bchlwl in I similar flnhinn. HnI'e1ler._ Ite-
`clulethecleltinaliumufthl Earl-dthe Av eneificiennua
`netalwayIlheutne(A'amtntheeetier),wernalhritnv;
`three pipeline anureu (units) and uneciated etmtrule. ‘nu
`[E,A,]hun la 1-i build: to I-eenrnmndarn the lnrurvlluelef
`the A, coefficil. Sintiiarly. the [ilg,Ag] bu I115 13 ‘Wide.
`1‘L1Ite multiplexing elf the 1:lpel.i.n:
`i.np1tt/output buses and
`the inherent
`two-pltaae eoenpumion u! the S u-nrrsfunn
`enable the device In mlintain I needy me or npentlnrt at
`the sweet duel:
`trequ
`in either forward or in-vet-re
`mode. The PCB’! on the
`put: Ind ili.I.I'p‘I.lI’e oltlie device
`ensureiltnttheeeuelctll-nehrunizatinrtnnhednulrnmet
`lntltelI!oIo§icaJpi|)elineI:rtIncheelI|tlu'Itlteed.11Ie
`mictnptueennr PM Provide: a 4-2: bidireetinnai dl.l'a.bu|
`and animal Jinnah.
`lninrvtard n'lude,ihepixelporli.IIhe inputlolliedevlco
`vrhiletheeuefllcienlporti:tlteouIpuz,I.ndlhelowuhaIfof'
`the dale path h inactive. The efl'ect.l\le internal pipeline
`letental is fuur clock crelee. Only‘ the Ital! leedblck. pill: is
`aetivesndliul-edeileI';'othereydetoinnpiernenIal'Irn~ataue
`butterfly cntnpntatian. It takes two clock cycle: to aequite all
`iortrp'uteisinlhenmri:.urd:iruiwoc9:iutonrttputthe
`lent eeeflieienu. Tim the toll! input-to-manna: leteltelr ll six
`cyc|eI.[uilrt¢rIemot.ie.aiIeiententanttherimpnthnre
`operative.
`l.ll.|ZflIKILI:lIl,| an additional ad: to the pipeline
`latency. [iIIhllflIl.lIi.¢l.llpI.Ili’cilhedeVleel|.!Il.l ennffinient
`pnunlvlllietheeutnntilthepinnlpnrthgainnloeioet
`cyclelarerequitedlnfullyloednfl fnt.Ireqe!fl¢ieI1n,wIIich
`are then tranelerted oliet lite lt:lrl.|er feedbackpllll. £32, to
`the input-sun swirclt it Reduet‘. The nntnnt item the
`proneaattritpatseti through the inweritallntlhetlnta path.
`Again two t.-yeien are required no output the reeamtrueted
`viult
`'
`‘ho I-it ptngratnrnaitle registers define the noel-nine
`meduutdpannenreanunerlenflnutheeflmipu
`rnndee nfq'.lerII.lnlrt dlthe tlcvlnc: forward tniufiorm, inverse
`trana!nm1,lorwIrdbIP0ll.lndlJrvenebypa-.'l'hehrpIan
`mode: are pruvitied uurtnltle direct tnnafnroipiatelt through
`the tllip.
`OneoflIInIeatlchI.ilIIeattheaeleetetltnntppn~rtd'lu-
`noa1'u:n.'i"hnmnIrnlai|n.nlat:inck. naeynndzeueuahlethn
`device to be placed into the principal. diagnnnlic. or reset
`state. Upon newer-up nr 1 tenet condition. the device in
`nutnnurieully planed into the lorwatd truutnt-ea mode of
`operation.
`_ M min; one prneeaanr. fleedbaelt dull UIJ-ice. and little
`ntttllipietitag of the pipeline I/O, we have been able In
`achieve an eiiieiertt V15! implementation. yet one that natu-
`rnily fit: the raster i'o1-nut of scanned images. The chip is
`bund on 3 standard eeil design. in It L5-tell! CMDS double-
`rnetai process.
`it will be available packaged It I 84-Din
`!‘LCC component trperalitlt al 5 V rI:quirin| no more than
`_6iJi] mw at
`Ii] MHz. At this clock lrequenttt. the chip can
`sustain a processills rate 0120 mi1iiort,pjxe.is per scenad.
`
`'
`
`I:-[e+.t+c+d]/4
`5,,-[(n+.-.)—(a +d)],'z
`Av-ii-=+bJ—(c+d}]/2
`(2)
`A,-a—e—e+d.
`Given the tnnltoml eneifleiettn. the Oflllllll pilei: can be
`obtained by the invene trnnnfnt-nt realized by
`
`c -{(2-11+ r[s2[) + am
`5 -[[2-11+ lr[;2]) -I2]/'2
`e -[(z- e'l+ .l='[.t2]) + lay:
`a -[(2-41+ F[d2.]) — dz]/2
`when the lltlerrnediale variables :1. til, :2. and oil are
`
`(31
`
`:1-[(1-lZ+ r|n..]) + .i.,],r2
`d1- [(2-:+rlayl)—eu]/2
`:2 - [(2-A. + 1-'iAai)+ AD]/2
`(‘ll
`‘fl"l(3'5lIr""l3oD'5al/3
`nndtltefuncxhe Fl-lretunutlte inn: siutriileantbitnliu
`Il:ttn1ent.1'hlIfnlnIcllhI6eflIIull.rIn.lfeIrn eqttltlonwu
`ehetentnenrurntnnttnnnynuntlerangenttttnplnelntnany
`Eirnage rernaitutiteume t-eprdiunofthenurniterot
`hien:ehiu1lleeurnpotitionI(otreeeutrlretiens)In image Lt
`rubj¢ette.'l'hereitneinnei_ah:tifiernthr'ubeenmn ti-tn
`ieaat-t1sI1il5eut-iaitia£nrntatitniaeI.rrledintItentIte:ennffi-
`eienta.3ytne.an.tnfthell1-|i'uraetinnintheiuvetuetrnns-
`fnrntellratilhleaueteeellledtolheirfltllteeeiulinnplier
`lflluvenmputntbmoivinthettiteninelnintheottainai
`liflllelledllililedioe bitlfpfliflve ln'Ie|erIl, tIteEcDefli-
`eienturii.|reIrtIinebiu(pnd|iveLutegnrl,theA anday
`eeeffieieeuwilleaeltheb-I‘-1 biufitianed i.nteger:.an¢ithe
`a,eneuIninrtla+2hiu(:i|udinmurl.
`
`B. 5-nI‘ll.Ilf¢'fll CM: Auilltmlwn
`Fig. 2 shall the Itnhileetnle of the .|'-trutafotrn pipeline
`prneeuot[SPlPE)ei1ip. The device has three pom for
`Pl1°lI.'mcEflt:ieI1u. and the tnierwrroeeaaer-interfntx. Data
`Irlnlfer ihmulh the pill! and nnetlicinrnt porn is nnntrnllen
`W I self-rerulntu; eyrteitrnnntu pmtneol {PCB}. The proces-
`sor
`nl ene array of four aritltn-letir: unit: that imple-
`ment nddttien, subtraction. tnultiplltatien. and division by 2.
`"No feedback tine bltaenifili anti‘!-'52) amine this aI1:!litee-
`lure optimum for the cmnputltlorl of both the liurwani as
`well at the irtvene Iruufinrut. The short fnedbaek nut. FBI.
`enables 100% utilization of the ptoeeunr. In inverse mode.
`the block Mu: &.
`l..in:titer_e|uureI correctly reconstructed '
`
`Page 123 of 437
`
`Page 123 of 437
`
`

`
`‘me
`
`..--;.-~ .
`
`._
`
`.. ,_
`
`i
`
`.:im-..-'_
`
`_ ,t1.M-“rd: CHIP SISITOR LOSSLBS IMIAGE. COMPRESSION
`
`plpolnn
`sltllral
`
`Ft‘. 2.
`
`stenptilled 5 tneelertn pipelim pt-oeoaor (SPIFE) etchitecutte.
`
`III. Dams Cutttt-tustsovt Dacqueltusan
`The data compressor/doeotltpnesor (DCD) uses 1 version
`of ma l.etnpel-Ztv (L-ZJ eompmatnn -tsnrmun is]. £91. The
`L—.z ulgotithm repisces input string: with code words, creat-
`ing a eornpretted output. A node table, containing the dot:
`string‘ that each node represents. is ootI.It:I'ttt‘.ted bleed on the
`data enqountered during compression. During decompres-
`sion. the some code lnbie 1| retreated from-tlte sequence of
`code words. In the table. strings are tepnetented by the uncle
`tor I shorter string plus an additional data word. During
`encoding. a string of a single element will alums be found.
`The next longer string represented by lltlt siting plus the
`next dltl. word will he Iettltiscd for. This mucus continues
`recursively until the ioruer string is not found in the tibia. In
`this case. the longer string is entered into the settle and the
`code for the shorter string in ttlnmtitted.
`While encoding. in truurniniort is made after every fnilttrc
`and is Iccumpttnied by the creation of it new code-tnhie
`entry. This knowledge in tiled bit the decoder. Each time the
`decoder re£eiv¢_s n node. it nukes I ontruponding entry no
`its tutti: by appending the tint eltnncter of the currently
`received code to the pmriotst code and assigning 1 new code
`word to it in the oode ttthis. At the some time, it outputs the
`string corresponding to the current woe. Ilium opet-sting
`jun it stop behind the encoder.
`Ziv and Lempel [SI hue derived upper bounds for the
`oompression ratio attainable with full a pried knowledge of
`the data by fitted code-.tnh1e schetttes. They have then pm-
`mood to show that the efllcienctr of their node with no
`it priuri knowledge of the data ttpptoachet thou: bounds.
`
`A. Solutlrttfltt L-Z5¢¢rt':Pt...RflWh|'llmrti'
`When ineneodittg. n ttewdetaword is received, I prefix is
`nppended to it, and tlteoode tebie isseuehetl for leads
`word reptucnthtg tltil otrltbhtndott. In the DCD. W WNW‘
`theoodewordsi:.etoi6h'.I.hdheneehevatoIenIt:.hthrott;h
`64K toestions. Hashing [mi-[I31 was etuvtwed to perform
`the high-speed senrch and retrievnl.
`
`B..h"e.dt-irtg
`I-Iuhins it I technique
`designed to speed the nation] at‘
`ctmunnt.-tstedttnthniney K[1Di.TiterInneotx in-mlllltf
`extmncty tum; honoe Kannothedlree-ttytnodusn index
`ouddreutottndthednta.Onccotnputetatunetionf(KJ.
`tlseh|.ehfuJ!¢Ki0fl.1fltI¢h1It|IeIt!t:Iti0ItofKnndthe
`sssocisteddatninthetnhie.‘I'heh|thttIectionPruvidest
`napping {tons this tune range of K to I antler range. Such
`antappingisnptttn:'qtte;tntstefltIno!Ieentntcinbe
`mapped onto the tune ioentlon. This it called 1 oolliiion.
`The difference between ituitin: eehentei line in the III? 1110?
`ruohre oollisionl.
`The schemes mute on moment for pertotmanee. The two
`main categories of _{.'0IIil§0I'I tnloiution Ire “I:-||aIlII|J‘Il" Ind
`"open addressing." in cheinim. I link is med It each tebie
`entry to point to it chained list ot edditionoi entries in an
`overflow rnesrtn-111' that had been tnttpped elitist to the same
`location. in open nddretsing. the additions! entries are placed
`within the tune table by some predefined ntethod. In chain-
`ing. the mapping is presented. While in OPGII ldiimlifli. “"9
`mapping it lost.
`
`Page 124 of 437
`
`Page 124 of 437
`
`

`
` ‘
`
`IEEE JOUII-NA.L OI’ SOLID-STATE. C‘lllCU|'l‘S. W31. 25. ND. 3». MARLTH I39]
`
`1-to
`
`
`
`I13. 3. Averqe nrendaerntnemry prebaa vatrau merttnry required {in
`sirasbtutl.
`
`lit the “open a.dilr'eI:t':r|" due of bathing achetrter. uni-
`latm hashing has been rbcrtnt
`to be optimal
`[12], while
`easleeeert haaiI.i.n|
`is IIIDVIII. Ofllllllnl H1] in the "ciIa£n!lt|"
`other at huhlnr schemes. We aiaalyzed the pet-forrnence of
`nine rtirterent taaitlsinn remhtdon achemes: 1lnear(LtN. [10]).
`nlliforrn lu.u2. I101. I121}. nueieaend {Co.C-12. I101. [11l3- Ind
`separate chaining (Sr:1,Sc2.5cJ.Sel,
`I10],
`I111.
`I131). We
`dirt not
`t.-enaider
`the enrnn-teniy used performance
`rrtes.sure——nttmher of memory pr-nhea versua load-teeter
`(traction of the table filled)--as an important men?-IN. since
`the new load factor is diflerem aeheurea represents difleru
`em asteurttrettnen:t:rrrettulredand.rtenee.'tanetaa'uod
`measure of relative performance. The perfarmlnee measure
`eetrsedarutbeaveruemtntberofnternnryptnlterlnr
`teecttttingaa-ucr:eaaenti_aEallu:eaaaftrtn:rio1-tnrtrrrnt
`Rltmofvunplvrvi-i,'flreurrtenmeefthe anely-rirluhmtm in
`Etc. 3. From the eerfet-nanne and tntplernentatiert point or
`view. separate chaining I (Sell irll meet attractive. In chain-
`ing. the eddteae of the uwrtlw nnwtrery implicitly connlna
`the code word Ileoctlledwilhlhlreyandwedo rtuttleed to
`:atore it. thus saving rrsetrrrrsy.
`
`c. Memory smttgaretetureexryznttdrtpatirtiag
`3|!!!-‘G lht IIIIPPIIII waa presented by ehelning. the eddreea
`of the keyjit-ea information about the her and only a arealler
`lIanofitneeattrhelered.Fore:entple.lftrtehuh
`l’u.n:tionlaadivia.|nIt.thenthetpaoeienteanIreua:dealhe
`addreseend the remainder ahnreal aa the ebbrevluted key.
`
`D. Has‘: Function:
`
`The D=I'fOll'I'lIl|C= 0'’ tn! huhlu scheme depend: on the
`hub function. A need hath function spread: all the input
`key: umiarmlr screen the nttnnery range. Mrtitiottttt eon-
`urainta were plead due to the desired use of abbrnlatett
`Wt’! Ind maple Etardwara. A bull function haaed on Ilium’
`|'|'II|f'v| Tmllliniieatinn Ina developed. which satisfies all the
`above constraints. The hath lunetiort end abbreviated key
`generator car:it ennsirt cl an array of s.ttct.ustve-on gates
`WMEPI mmhiflfl bite of the input key to form the hash
`hanction and abbreviated key,
`
`'
`
`
`
`I-Dl.‘ll1'E88
`
`lflk .
`Fla. 4. Merle: etunbar of eulriet in earth Iddreat (eheaen Iran ma-
`I
`
`It is convenient to re1Ireaenr the generator: as matrices
`(Hui) oi ONE’: Ind a:ru3'l. Ind the igrjrul hey. ltaah func-
`tion. and ahlrreviltetl heat as vectors (hi?) of ante‘: and
`zEl.D'l. With this repreeenratirm. the get-teralare for the huh
`ftrttclion and ahbretriated key may he expressed '11
`(5)
`5 - HI?
`(6)
`i’ - AF
`where binary multiplication '5 performed by Art1>irt|'orl bits.
`and binary addition is perforated by e.xt:r.t:srvs min; of bill-
`II the hash function eeneretnr nnttltt H ‘ta ra.ndon1.|y created,
`the neetrltin; heal: llrnctiert lrea pod prepertiea. The diffi-
`ntlnr is in treating an aranehhed abbreviated key generator.
`We emnblne (5) and (6) into one equetlen and obtain
`
`(7)
`
`|:l-lf.‘l*-
`as last; as the etlnblned matrix
`A|"|
`il lnver-trhle. III! cflrllllnlliolr oi hllll filntfliolt it and Ibhl'B-
`viated key a uniquely represenra the orlslnal key it at
`requlred,sint:eictrtaybeetatrpuhedfrnnri:andeeaahnwn
`
`below:
`
`,1
`
`can
`lt|-
`~-lat
`Tide allow! us to create a eorrrlalned peetrdanndnm matrix.
`restricted to invertible rt1at1'lr:e, which will result in n gener-
`ator having good sratietlui rttwertim fer the hurt function
`and valid abbreviated ken.
`Once the enmbined matritt la determined. it me}? be seps-
`reled into the indltrlduel rraetrlm H and A to generate the
`hash ftrnclion and Ihbrwiated key. respectively.
`Eartemive software dmulationa urine mpreaenrattve data
`were pert‘-nrmetr to select the binary rrnrritt. Fig. 4 than the
`eveme number of entries at each memory‘ location for the
`chosen rnsu-ix. It shows the ttnifortn mending at the irtllul
`key: srtrusa the memory range. Simulations eunflnn out
`theoretical
`results of less than L2 probes per key. A: a
`contrast. Fig. 5 show: a different matrix used as the hash
`function. It is ell!’ to see that mernury utilization is not ea
`unifnnn. resulting In many "clusters" of over and under--
`
` .__
`
`Page 125 of437
`
`Page 125 of 437
`
`

`
`
`
`
`
`utilized locations. This huh function requires rnote than
`[our probe: in resolving each key.
`Since all
`the algebra involved in the above binary upm.
`tit:-its is modulo two. the lurtlurrte Ir sharpie. consisting only
`of zxctmtvz-on plea.
`Additionnl memory savings are obuinod when the main
`memory marlin: only it link field. This field points to the
`overflow rnerrtonr containing the bar. the inrpllttit oode word.
`and further link fields. Refer to FEI. 6. K it hultvad to the
`link table lmlin rnernorr.'I by tlte hash Ettnction. If there it no
`linlt at tlttt location. .tltert we have I hilure end a link I:
`created to the next mileblu erttr location in the overflow
`memory where K is inserted. Ortstlttt other lurid. it there il a
`little at Ilm'locrtion..we follow it and loolt for K in the
`chained list of the overflow memory.
`A diradtrantaie or the reduced main memory sclterne la
`lhlll a rninitnurn of two meteor!’ recesses is required to find
`each K. This problem can be oltercome by plp£Hl1|I1.| the two
`ICEEIIEI.
`.
`
`
`
`“tnMICROHDEBSDIJKHGDRY IITLIFACE
`
`HP-Pnlfl‘
`K.!1'_CI'lD.hTA_.'llEfl)i PORT
`TAO-|l!HJ|.IJ'D Full‘
`
`at 1.
`stwuttcrocottnrxaturlm.
`
`Simulation: [3] have lbulm that the L-Z II[Ol'ilIl.Ill‘fl3l1l-
`prerre|aniuta¢ehyatIcnorot2to3.witltnvennert:'lnl-
`lengtluofbettreen 3and4.1'hotnfure,trhileoe|rchinsllora
`pn-.fl.t-dun eornbinnion. ruuceu will occur lhree timer or
`often as hilute. with tho knowledge. we can anticiplte It
`prefix oefouthereuehllrooolvodlndwecnnbomnet-1
`about 7595 of the time. I! we anticipated Incorrectly. I'=_
`ditteglrd the incorrect
`link Inrl use the out anticipated _
`prefbr. T311: bIt:!lttrIc.HD| method llloul efficient pipeflnlnl
`oftlre mainlliuklmd overilm-‘(test Induode wotdlnremonr
`Iwesset to improve weed.
`
`F. Cirtprtrtznitrrmn and Fatwa
`'l1teDCDel-tipeoruiruoftwe-16-hFIFO‘s.reodee
`(Including enoodef. decoder, LIFO luoefiry for deoodlnll
`node-word unentlon block. and I II-llb-hvel mntrollotl. I
`reprelter. and a rniu-otrroeeuor interface section (Fig. 7}.
`The bidirectional FIFO’! In In smooth the htmnt flu fllf-I
`inherent
`in the compression and
`I 9'03"“-
`Durirt; coding. the decoder is idle. Ind during tiewdlfltt 3313
`encoder is idle. ‘Rte bidirectional rt.-meter converts n_rl:l:le
`width codes to I rm output width during eotnpteutoo or
`vice Venn in deeodiru. The mieruotoeeasor interiaee pro-
`vides control and dlunottie: of the DCD.
`The cadet: is shown in FL: 3. The code-Ward generation
`block (cw bloclt) is common to both Gfll73dlJ'I[ and dfl70l'.lllI.I.
`The eodec int: a hierarchical control structure. Each at the
`block: has various low-level state machines to mike local
`
`E rllrarithrrt Impfenrutlarrbn Mtfl .HI.ltHl'l.[
`When the idea of pioelirlins main and overflow nrentory
`were: is encoded to the L-2 algorithm, 3 pownllll prob-
`lem arises. The rlwirt memory cannot be Ioceascd without the
`prefix and the prefix will not be Inlhblu without lCDelsil'I|
`and resolving the search in the overflow ntemory. However.
`inherent pmpetties of the algorithm do allow us to pipetine
`ll.
`
`Page 126 of 437
`
`Page 126 of 437
`
`

`
`‘tau
`
`‘
`
`IEEE roustmu. or SOLID-STA1'fiCllt{.‘l.ll'l'S. vol. at. no. r. t-siutctr mt
`
`decisions. The high-level state rnschine.hi1evel.sni.. monitors
`the blocks end controls all oonsmurtiestlons with the outside
`world under interrupt control. Breaking the control into I
`hicrsrcifl enlblcd sir:npli.Mn¢ the state machines and provid-
`ing a urtifonn view of the processing (encoding or decoding)
`to the outside world. This spproscis. however. made synchro-
`nization of various events more cosnpllcatcd. which was
`resolved after extensive simulations of the hardwtsre.
`Use of the DC!) chip requires trln estemsl memories to
`store tables. One memory is
`IJSKXIG ll or RAM plus
`lzsxxl is of resettsble memory. The second memory is
`64Kx.'i: bnfRs\M.TIseDCl3ltssress:tanddcich:inputs.e
`iiidiwfiiififlll ‘I311 I‘-‘DH. I bidirectional code port. a micropro-
`cessor interface. and I direct mentor? sccess port for diag-
`nostics. ‘1'he.dI1I eon consists or s 154: bidirectional port
`and three pipeline control signals. The pipeline control sis-
`nsls are handshake siutsls tn ucilitele synchrotron: transfers
`to and from the
`t)uringcodlng.theDt‘.‘Dwillaeceptdstastsword traits-
`fer rate of appmnimetely 1.5 MR2.-During decoding. _lltc rats
`lsh.iIller.Il:out8MTr‘Iz.'l'l:eaet1ss.lntuIr|ierttrl'I:late bluuscd
`bytheDCDiI9IIllIIlltsns.hle.'l'hecodeporrennsistsola
`16-h htdlsectinnsl post and three pipeline control signals.
`The insurer rare at the code port is llmieed by the transfer
`rate at
`the dsta- port and the actual compression rstlo
`achieved. The rnssietuer number elcede hits used by the
`DCD is props-atttnssltle.
`The chip has sixteen 84: control registers visible in the
`ptostsrnmer. All the transfers are under synchronous micro-
`processor protocol cnntrnL The registers control the direc-
`lionioompress Ot&al1't||tBnJ,tllIlII.1lI'IiiIc1'oft‘htl sndoode
`hits. and the first sliocatsrl code word (sliows for keeping a
`range of reserved code words). Till? Ibo provide for insert-
`ing and sernoviiu code words in the code streets. The
`cstensaleodie-hookrtnsneriesranheseeessedlythe DMA
`cl’ 1 start sddrul ill the control segkten [useful for disp-
`nostlcs). The output code words csp be packed into any
`nstnriser oi hits (He) in the repsclier. wltlclt it pmsramnsed
`using control registers. 'l1re DCD can be programmed to flu
`an interrupt under vsrinsts conditions (for example. on re-
`ceiving e renewed codeword creeeousttering an error). 11::
`chip can also be operated in I shulevstep mode for diagnos-
`tics. The DC!) on be programmed for automatic reset when
`sheusdebooklsfuil.orcnsrcnrtlin1retvithoutttssil.inssny
`new table entries. The DCD is s srsrtdssd cell design. imple-
`mented in Sipeetlce’ 1.5-um CMOS lecltnolo-gy.
`Tito DCD lID0l'lI'|‘llfibl8'fll‘IIl.cxiIllll]ullI'lpfeIIiDfl soft-
`ware, rwrrpuu Ind lznorrtp,
`linund on UNIX and VMS
`systems. The speed and oorttpatililllty of the DCD makes it
`I-KIM ‘W wflilmession in dist/tspe storage and satciiitef
`micron-eve/IAN eermnunloseinn Imerns.
`
`IV. TI-is Cosmmstnu Ssrteu
`Fig. 9 shows s diagram or an insane compression/decom-
`pression system (CD8! employing the chip set described
`above. The configuration shown assumes that
`the CD5 is
`part of a letter inure processing system with a common
`i.n'ls3e system but for control end imlpe transfer. However.
`simpler ones are possible. The figure shows only the princi-
`Pll em Pltils or the CD5. Apart from the srms and DCD
`chips iincludlnl external memories {or the code tables). the
`CD8 conIains1tiree_fF_lFO's. a local in-tau hutfer (LIB).-an
`notional quantiser..and e controller. ‘No date interfaces
`
`accomplish Lise transfer of pixels and coefficients. We have
`designed such s srltem around the VME. bus as s two-bmrd
`set. i.e.. SPIPEXLIB board and DCD/qunntizcr board.
`The quantizer is optional and is provided for spplleations
`pemtilting lousy ootnprtssion. All FIFO’: are needed in
`either mode of the CDS. Two or the FIFO‘: operate as s
`multiplexer or demultipleser oi their inputs: the third oper-
`stes in srrsigltt input/output mode. The LIB is lsrgo enough
`to hold the fires E huge of the largest imsgle size the system
`is delittned fer. e.e.. tor a 2lDc2.K-plsei image. the LIE holds
`1 million piseis. The LIB substantially reduces the traffic on
`the image Iyslclll hits for hierarchical compression or decom-
`pressicrt or large images with men)‘ decomposition levels.
`In compression, phtels from the original image stream into
`the CDS end up dcmultlplened by the pixel FIFO into two
`tester stresnss. i.e.. the [o.h]- -- end [e.di-'- lines or the
`image. subject to pipeline syncttrnnizslinn principles. Then
`the SPIPE ttlrrsforrsrs the image. ‘Ilse E coefficiertts are sent
`to the LIB where they
`internally or-cruised as two raster
`streams—tht.tt the LIB be
`use sstsro Fll-‘0‘s' Meanwhile.
`the A‘: are huflered up in the coefficient E-‘l'FD. The enchi-
`clent FIFO snolripicmcs the A's that pass Iiunush the quan-
`wear and the DCD. The output of the DCD is buffered up in
`the code FIFO and is
`that
`transmitted over the image
`system bus to its final destination. Tltls sequence cnntirtues
`until the entire origins] in-tau hgs been processed, l.e., level
`I of the hicrllclty |t.I.s been completed In this phase,
`the
`isnspc system bus ishuslest, having in support simultaneously
`piselandeodetnnsters. Itthellnihimseeistnbe further
`decomposed, Le..forleveI2.the Llllpreiridestltetworsster
`streams [st.b]---
`sud [r:.n']---,
`thus tile pixel FIFO is
`insctive.1'lteenntpressbnio1lowstltessmesequenccss
`iscinre,httt oostthe L[Bi.shnt.hssourwttnd aslnkforf.
`sulsinssgandtll-eonls'1rui‘l'leontireirns¢eI'J'I|£I=IlvIIIi-I
`that or code tssnslers. Further tilerssehicsi decomposition
`steps may be aclsieued until the nrisilest lmsps_is in the LIE».
`At this point, we lsnlre the option of direcfl! lwttirlng the
`smallest
`losses from the LIE thml-Isis the pisel FIFO or
`passing it to the DCD for coinpreerion.
`lntelfi
`In decompression. we first
`load up the smallest
`either directly into the LIB tlsrnush lite pixel FIFO or after
`passing it through the DOD for decentpressiert. To recon-
`struct the nest higher resolution image, the coded n’s stream
`Into the DC!) and are decotnpreseed.'dernuiIipIes:ed by the
`ooeffltzient FIFO. combined with the sinsllest image from the
`LIB. end inverse-tr-stsrionncd hy the SPIPE. In this phase,
`the Llflls holltssottroa and ssinkoltimdsel. and rheonbt
`t1-stfle on the image system hus is that or coded A's. Once sll
`the A's for this layer are processed, the higher resolution
`image is resident in the LIB. At title point. the itttspe may be
`directly accessed throulh the pixel FIFO or dwndirig of a
`higher resolution image may he initiated. The reconstruction
`process proceeds as before until the full-rrcsolulion image it
`achieved. Al the fins! level. the pixels are directly pulsed
`throuph the pixel FIFO to the system bus so that in this
`phase the image system bus Irsmc is made up of both ended
`A's and reeeststruetml pixels.
`The above system has heen designed around the industry-
`stsndard VME bus. For this implementation. the LIB ac-
`eomrnodatcs I million planets, the pixel FIFO consists of two
`[K-word bullets. the coefficient FIFO consists at one 2K
`and 4K word buffers. and.
`the node FIFO of it
`lK-Word
`hufler; Several Dl-iA_ channels are provided to speed)-ID
`transfers in the lnnsse system bus. Although uttty one D-CD
`
`Page 127 of 437
`
`Page 127 of 437
`
`

`
`SHAH at el:D-H1‘ set} '1-out
`
`mace COMFIIBSSIGH
`
`M3
`
` --e-a---......--..-.- .-.-----.----n-.--..-.-..-_.--
`
`rev. Muueumwameuamummmmu-emmsruzmnmauum
`
`devicciuhmvnL||Fi|.9,itispcIIibhI1ohIvaupUoth:cuLf
`the nppttcatinn require: the A‘: to be sent-ately command.
`Isnppozed la treating than u 1 trlpiet.
`
`V. R.a:uL1‘e
`In [31 extensive sirnuhttnns wen perbrmed int data oom-
`prcssion using the S tmuhm end Ltmpel-zlv coding. ‘me
`nnin result: :1: Iumuuliud heat. The S tnnstmm I¢|'lll'-
`ally tedtteed the cntrmy only about ll effectively us fits!-
`otder DPCM. For III: 15 computed redltunph Wilma: used.
`theuroth-urderennnnwuteduced nnnnevenutrom
`8.8to-t.6b.TIti:ienouurp1ie£n:.u:heflJt:nLnute5
`I1-ansformeteentemehv IIIIPI-¢.1Iflt]ll'aI1dl.11[lV¢»t!'IDDd
`Iepu-ntiun between the frequency bend: (the 2 end the A's).
`ll, howwer. bathe edvmtalenllhmie implemanmion and
`hientchlenl tum: decomposition.
`.
`Thcahovel!imagu.uchtI1thmod|inalwordai::oflU
`b/piuLIvcrecuc|cdbyLhcL—Z|1prithmxflerhein;S-
`II'lnsIuI-Ined. An evenieoulwreuim nth uf2.09 (Iron: 10
`Maine! down to 4.18 b/vi!!!) we: achieved. ‘nuts. for these
`intesemlhecunprestinnperfotmneewuverydue mute
`mductlolt of the tenth-order canopy la‘ the S tnmiutm
`flllfll an man at 5.5 b/pin! to 4.6 hf|gbnL
`
`_
`
`itatitiEamgag5%E§§E:atE.3‘!RE-='Ef:32;;EEEi?!E
`
`9ae“§§“egggT"€§§g§§§:i§Egg?3,-gfigg5%;gig}:*3%?’§%1:???ii§%‘*i%
`
`[4]
`
`I51
`
`I61
`
`I71
`
`VLCGIEMIWN
`The dnocflbedtwflflhiplinrmlhehadaofuhlglt-tpeed
`lossleu image compmllonfdacomvtnsiou system. The S
`truuform. besides damrntlntiu Ihl inane. Mwida I. came-
`nlent method at ltiermtthal Imus deeotnpoeflloa. ‘me date
`commence/deeomprcnor {C is I rent and enldent Incub-
`raentatinn or the L-Z nlprithm.
`Such a system reduxl Itanne remliremenu in Itlghvspced
`image mhivel and dmbue appiicutlotte end reduce: the
`transmission time of dlglnl
`lflllltl our communication
`channels.
`
`tition. and A. Miran for his support.
`
`AcauaowLencIuaH1'
`The authors would like In flunk It Appleptc, I-I. Hlume.
`Ind 1'. Wendie: tar very useful technical dilcutlium, J. Stun
`and G. Hyland for help in mloul Stile: cf VLSI iuwletuen-
`
`I
`
`utlltor of various
`
`
`
`Page128of437
`
`Page 128 of 437
`
`

`
`IEEEJOUIINAJ. OF 50l.l.D3'TA"l'E C'lRC1.|!'|"5. VOL 25. NOJ, NAIIGI-I LWI.
`
`
`Smear Member (If the Resunzh Siafl ll Inn Johan tuagimuhn 3.3..‘-.'.I-2. dglpua
`
`
`
`
`
`
`
`
`OII Aflfllni-Aalnl ru::‘rved Ih: B5. deans:
`roar.
`hum Ranmtm Pblyiechnie Iwiluta.
`xifl plI1I'u:| bun aha University o.fSc1':nue and
`NY. In 1915 and the M.SJ:'.E. demo hum
`Tochlldoqr. Ghun, in 1913 Ind the M5.
`swam: Lluiwniny. Symun-.. NY. in I9?!-
`dune in aaetrical gngineerins from Lchigh
`Ulviunity. Buthlzhem. PA,
`in 1917. Until
`Hc hu held position In Praise: Lnder ll
`lfl|_ ha 0|: unmilnd in UI: Elcatficll EMF
`P1_|il|.D1' Hwum CATV nnd Ozneul Elu-
`nu:-m Pl1.D.11r0|n-In 1: unigh.
`tnc-HaiIcurr¢uflvaP«:5oc1h-lInII¢1‘II
`Philip: LI-bomorlu. Bliuclilf Mmw, NY.
`He mush: Phyiici it ill: University of Sci-
`when ha il illxivud In VLSI Iitnll amm-
`
`
`cnae Ind Tefllndon. Ghnn. until he join-and
`P|I.||_h=Il.Aboru.ariuiaJ9§O. Hsilnowa
`laa and mlema. Ha lm appllog for and
`
`
`rewind pmnu In the ma ufmlctupuowr
`
`
`.BfiI.r¢lHMI.wf.NV.Hu|1.uhc:nimuhedII1
`Iar:1nI|m,vi:kona'Imhllng,d|umu|pnuiou.I1hid5;iLIlIi;nnl
`~ puiumznlsnimnu.
`moaning.
`V1.51. commuter uchmuun. ml mbruprupusor nntanu rmuuh
` ncth-ides.
`
`Page 129 of 437
`
`Page 129 of 437
`
`

`
`still Picture
`compression
`standard
`Gregcw 14
`\:*.'a!1ac:—
`
`Page 130 of 437
`
`Page 130 of 437
`
`

`
`
`
`
`
`"e.-.._._.rmi-=_sp-is-..—-e--' (
`
`civctnccs over the past decade
`in rnanv aspects oI' digital
`lechnulog_t'—especiall‘v‘dtWices for
`image acquisition, data storage. and
`bitmapped printing and display-