(12) United States Patent
`Gottesman
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,614,370 B2
`Sep. 2, 2003
`
`US006614370B2
`
`(54) REDUNDANT COMPRESSION TECHNIQUES
`FOR TRANSMITTING DATA OVER
`DEGRADED COMMUNICATION LINKS
`AND/OR STORING DATA ON MEDIA
`SUBJECT TO DEGRADATION
`
`(76) Inventor: Oded Gottesman 791_D Laurel Walk
`Santa Barbara, CA, (Us) 93117
`,
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U-S-C- 154(b) by 0 days.
`
`(21) Appl. N0.: 10/056,891
`.
`_
`(22) Flled'
`(65)
`
`Jan‘ 24’ 2002
`Prior Publication Data
`Us 2002 0101369 A1 A 1 2002
`/
`ug' ’
`Related US Application Data
`(60) Provisional application NO_ 60/264,494’ ?led on Jan 26’
`2001,
`
`(
`
`)
`
`(56)
`
`7
`
`............................................... .. H03l\;[4Z(9)2
`. ....................................................
`'
`.
`I.
`Fleld Of Search ......................... ..
`
`370/241
`
`,
`References Clted
`U_S_ PATENT DOCUMENTS
`
`6,487,686 B1 * 11/2002 YamaZaki .................. .. 341/94
`
`Primary Examiner—Brian Young
`(74) Attorney, Agent, or Firm—Morgan, Lewis & Bockius
`LLP
`
`(57)
`
`ABSTRACT
`
`Encoding/decoding systems and methods for use With data
`signals representing speech, audio, video, and/or other types
`of information, including, but not limited, to EKG, surround
`sound, seismic signals, and others. These systems and meth
`ods encode signal parameters into a plurality of frames, each
`frame having a predetermined number of bits. The encoder
`encodes signals into frames that are of longer duration than
`a transmission (or storage) interval, except in cases Where
`signals may be characterized by an axis other than time, such
`as image or video-coded signals, Wherein the encoder codes
`signals into frames that are larger than the coded segment.
`When no bits are lost during data transmission (or storage),
`the decoder uses the received (or retrieved) bits to recon
`struct segments having a length equal to the transmission (or
`storage) interval. When a frame erasure occurs, the decoder
`uses the received (or retrieved) bits to reconstruct segments
`having a length that is greater than the transmission (or
`Storage) interval‘ This technique reduces the need for
`interpolatiom or extrapolatiombased techniques for error
`Concealment~ The invention can also be used as an enhance_
`ment layer for standard or other prior art coding systems. In
`such cases, an existing coding scheme may operate as a base
`layer, and the present invention can be used as enhancement
`layer for less than ideal communication environments, by
`coding additional look-ahead and/or look-back parameters.
`
`* cited by examiner
`
`11 Claims, 16 Drawing Sheets
`
`INPUT
`SlGNN.
`
`50
`2
`SIGNAL
`
`_
`
`D 4/; I;
`j '
`
`I;
`M
`
`10 2
`CHANNEL ENCODER AND MUX
`52
`2
`
`‘
`
`11
`Z
`
`13
`a
`
`l
`
`so
`2
`
`x”)
`
`I
`
`‘ ENCODER
`
`'
`
`
`
`51 2
`
`LOGIC
`CIRCUITRY
`
`0-
`'
`’
`
`V
`
`,3
`“ _
`V
`
`MU)‘
`
`
`COMMUNICATION _ CHANNEL
`' (OR STORAGE
`DEVICE)
`
`
`
`
`‘ DEMUX AND D ‘ CHANNEL _ SIGNAL
`DECODER
`' DECODER ‘T _’
`X0)
`
`Saint Lawrence Communications, LLC
`IPR2016-00704
`Exhibit 2018
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 1 0f 16
`
`US 6,614,370 B2
`
`FIG. I
`
`INPUT
`5'6"“-
`
`.
`X0)
`
`102
`
`CHANNEL ENCODER AND MUX
`52
`2
`
`~
`-
`6
`D={A‘P'""‘P“
`
`5°
`8
`SIGNAL
`
`.
`
`11
`Z
`
`1a
`Z
`
`50
`2
`
`‘ ENCODER
`
`'
`
`5,
`2
`
`LOGIC
`cmcunnv
`
`'
`
`.
`D'={P~
`" '
`
`'
`
`.
`P-
`" _
`V
`
`uux
`
`>
`
`COMMUNICATION
`CHANNEL
`(ORSTORAGE
`uevsca)
`
`oeuuxmo D SIGNAL
`-> CHANNEL —>
`DECODER
`DECODER
`
`OUTPUT
`slam
`-—>
`_ _
`x(1)
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 2 0f 16
`
`US 6,614,370
`
`SIGNAL
`ENcoOER
`
`50%
`
`05
`
`O6
`
`INPUT
`TRANSPORNIEO
`SIGNAL
`03
`
`TRANSFORMED
`SIGNAL
`ENCODER
`PARAMETER
`EXTRACTION
`DEVICE
`
`o2
`(
`
`TRANSPORNIEO
`SIGNAL
`PARAMETERS 1°
`‘
`
`112
`
`.
`
`INPUT
`'
`-> (ANALYSIS)
`TRANSFORMATION A
`T(n)
`2
`04
`
`o7
`
`PARAMETER
`Egg/282$"
`
`09
`
`COMMUNICATION
`CHANNEL
`ENCODER ___> (OgHS"T%’$-\LGE
`AND MUX
`DEVICE)
`
`OuANTIzEO ANALYSIS
`PARAMETERS
`
`INPUT
`SIGNAL
`0‘ 2
`
`x(,-)
`
`SIGNAL
`DECODER
`
`60''»
`
`___—_— I
`16 "\J
`TRANSFORMED
`17
`SIGNAL DECODER
`J
`
`CODEBOOK TABLES
`
`18
`
`23
`I
`
`OUTPUT
`TRANSFORMED
`SIGNAL
`21
`‘{
`‘f .
`y(I)
`
`OUTPUT INvERsE
`(SYNTHESIS)
`TRANSFORMATION
`
`22
`
`OUTPUT
`SIGNAL
`24
`
`‘f ,
`.
`.
`X0)
`
`TRANSFORMED SIGNAL
`DECODER
`MEMORY
`
`PAST MEMORY
`
`PRESENT PRANIE
`MEMORY
`
`-
`gun
`;
`-
`-
`PM)
`4 '
`- T(n)
`25
`l
`ERROR GONOEALIIIENT ‘
`DEVICE
`*
`
`'19
`
`I
`20
`I
`
`14
`I
`
`15
`
`,
`
`13
`2
`
`DEMUXAND
`CHANNEL ‘
`DECODER
`
`J
`
`12
`2
`
`FRAME
`
`ERASURE/ 4
`ERROR
`DETECTOR
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 3 0f 16
`
`US 6,614,370 B2
`
`SPEECH
`150 N ENCODER
`
`155
`
`102
`8
`
`INPUT
`SPEECH
`LINEAR
`101
`5 _> PREDICTIVE
`ANALYZER
`NZ)
`
`RESIDUAL
`106
`k ENCODER
`‘
`
`PARAMETER
`EXTRACTION
`DEVICE
`
`INPUT
`RESIDUAL
`103
`Q
`
`PARAMETER
`EXTRACTION
`r(i)
`107 N4 MEMORY
`4
`
`_
`All
`2
`104
`
`EXCITATION
`PARAMETERS
`108
`I
`PM,
`
`1o
`
`109
`
`13”“)
`
`$8835;
`AND MUX
`
`11
`
`COMMUNICATION
`CHANNEL
`(0R STORAGE
`DEVICE)
`
`QUANTIZED ANALYSIS
`PARAMETERS
`
`SPEECH
`MM DECODER
`
`116 N
`
`EXCITATION
`SYNTHESIZER
`cooeaoox TABLES
`
`117
`
`11a
`
`EXCITATION SYNTHESIZER
`MEMORY
`
`
`
`OUTPUT SPEECH
`
`124
`l g
`‘A _’
`s(1)
`
`123
`2
`
`EXCITATION
`121g
`
`Y
`PAsT MEMOR
`
`m 132
`
`J19
`,s
`
`
`‘ I(n) ;
`
`122
`
`LINEAR
`PREoIcTIvE
`SYNTHESIZER
`1/A(Z)
`
`' ’A_
`r0)
`
`1228
`4 ,
`
`A
`
`PRESENT FRAME a120 -
`MEMORY
`’ , '
`"5
`4PM") @
`A
`/
`"
`125
`
`4
`l
`
`ERROR CONCEALMENT
`DEVICE %
`
`DEMUXAND
`CHANNEL
`DECODER
`
`I
`
`EQ‘QTREE,
`ERROR
`DETECTOR
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 4 of 16
`
`US 6,614,370 B2
`
`Fifi. 4‘
`
`05:00 ART
`
`38%-I} LGQ%Kfi:HEM3»CDE}EQ 3E3-‘I‘..T§'£I3§\‘I {FULL FRMVEE ERRQR *fl£}E‘dCE.r3aL%*‘éE?*iT}
`
`6&3
`
`,
`
`401
`g.‘s
`’
`
`S-'?E,fa.:°v§Ez{rs~*é}
`
`
`
`.
`
`4 _
`
`Am
`
`5 3
`
`
`
`
`
`
`
`Fs:A6aE'EE§§{{é}Eé.QaR
`
`
`
`6&3
`
`51"’
`
`’§:T"4~_§;
`
`§:TMi
`
`137:”?
`
`$3
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 5 0f 16
`
`US 6,614,370 B2
`
`FIG, 5
`
`5110
`a, 5
`
`513
`
`1
`
`
`
`3 5m
`
`1
`
`i
`
`f6 W
`
`1
`
`- 3%
`
`QUWU?
`
`mm
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 6 6f 16
`
`US 6,614,370 B2
`
`FIG. 6
`
`FULL FRAME LiIiQK-AHEAD CQUEG SEE'TEQN {NO NEE} FQR ERRQR QQN?EALME-N? FER
`
`GNE ERRSED FRAQE}
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 7 of 16
`
`US 6,614,370 B2
`
`Fifi. :7
`
`MU E35,:-1”-‘EL.E =F“"¥?J3sE‘ew%EE %L§3{§Ka‘=’>,HE§%z£3 *3f.}E3E‘E’§ SEEGTASGN {HQ NEEE3 HER ERRQR {lC?¥‘éCE.s°5,E,ME?«§T
`
`FGR E4. EF%fi.$ED ¥F3;'—%E‘u¥ES}
`
`{S .?"1"3
`duo,»- - .. . .- .»V»»»..
`
`{rx+t:4-é‘
`CWED‘ 9.C‘(D$lR'<~é§i5:l’I-‘
`
`71
`
`jig E
`
`
`
`1
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 8 0f 16
`
`US 6,614,370 B2
`
`QCBNQEALEMENT SEGWQN}
`
`F0606
`
`w’- 5-132.
`
`an,“ 393
`
`MM 33?
`
`am
`
`s66
`
`3
`?
`
`66m T M1 6
`5
`'
`::
`§
`5'
`E
`E
`Y
`imTn‘ffa-g FT“
`5; I,‘
`
`WY“
`
`=.
`
`r
`ié
`
`2% B; 2
`ism 016;
`m5
`
`‘i
`
`>
`
`I
`
`,
`
`E
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 9 of 16
`
`US 6,614,370 B2
`
`HELL ?7R§-ME fi3*’CZ=§*=’w§=a?*§§.E.¢‘vaiE§ !a?«§€3*
`
`fififjiié
`
`C2fi="‘EE57 33§ECT%{}?=~%-3% E]
`
`E‘£E.EE} FE}??? ERRQF.
`
`Fifi’.
`
`£1?
`
`‘~i3€%E*e‘i»‘i3E.»-*'%,3l,:’~'4*%Ea"~§':’ 3’-‘SH QNEE EEASEEE F¥3?;’a?z5&?}
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 10 of 16
`
`US 6,614,370 B2
`
`FIG. ff?
`
`MEJLTEPLE Fflfififlifi L§30K—£3HE£3.C>‘ ERNS LQ0i*<*B:3%C?°i {ICJDEE3 SE£3TEfI3E‘«§L’:? {NO NEEC? $5-"(ER ERRQR
`
`C0?~E£3E&L?g€E;NT FGFQ 1%:
`
`§:R.3§3§ES,'-
`
`152%‘?
`
`“$;FERrFRflP£E *’r:«*£;A
`;
`‘39D§5L'
`2
`ccezrcazr:
`'
`z““'*‘**°W"**0
`Lfi’,vi3%~‘¢E%fi.{1S<
`‘
`:
`' " I
`'
`/3
`‘~-'-2**"
`s
`6
`-
`.
`
`>
`
`
`
`5
`
`-'
`;
`CGQEE
`
`§
`L»‘.’.'>f_’JrKfi!%.»i‘.E'{
`I
`.2u«tA.z.w'3as=..>:::fi<
`7
`an.
`
`
`£55-.'J §.i}\C‘~K-‘fififi
`
`.~ 1&0?
`
`166$
`
`W05
`
`
`Lam;Lw:;<
`
`
`__‘,:
`
`3U5:‘E?}~‘?'Rf'~:3§E
`<'w..+-1.6}
`“é§'§m &‘*l¢K=-{f~;-Ki)
`
`,
`‘:~
`2
`;‘””5\f___mm::,rr
`
`
`
`,6
`1313
`
`A.
`
`I‘
`
`750*“
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 11 0f 16
`
`US 6,614,370 B2
`
`FIG. 11
`
`P.
`
`8201
`
`FOR SUPER-FRAME n.
`PERFORM ANALYSIS USING
`LOOKAHEAD (IF SUCH) AND
`QUANTIZE INPUT
`TRANSFORMATION [LINEAR
`PREDICTIVE] COEFFICIENTS
`
`8202
`
`FOR SUPER-FRAME n, ENCODE
`TRANSFORMED SIGNAL
`[RESIDUAL] PARAMETERS FOR
`LOOKBACK (IF SUCH), FRAME
`n, AND LOOKAHEAD (IF SUCH)
`
`203
`
`8
`
`UPDATE TRANSFORMATION
`ENCODER AND/OR
`TRANSFORMED SIGNAL
`[RESIDUAL] ENCODER
`MEMORY, AS NEEDED FOR
`NEXT SUPER-FRAME
`ENCODING
`
`8204
`
`SET n=n+1
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`of 16
`Sheet 12
`
`US 6,614,370 B2
`
`FIG. 12
`
`START
`
`BOI
`
`WAS THERE A FRAME
`ERASURE AT TIME n?
`
`- 302
`
`SYNTHESIZE OUTPUT SIGNAL FOR
`CURRENT FRAME
`
`303
`
`IS THERE ANY CODED
`LOOKAHEAD FROM
`PREVIOUS SUPER-FRAME
`WHICH MAY BE USFUL TO
`DECODE ANY PORTION
`OF FRAME n
`NO
`
`305
`
`ANY PORTION OF
`IS THERE
`THE FRAME THAT IS NOT
`COVERED EITHER BY
`LOOKAHEAD FROM
`PREVIOUS SUPER-FRAME
`OR BY LOOKBACK FROM
`FOLLOWING SUPER-FRAME
`
`NO
`
`IS THERE ANY CODED
`LOOKBACK FROM
`FOLLOWING SUPER
`FRAME WHICH MAY BE
`USFUL TO DECODE ANY
`PORTION OF FRAME n
`
`NO
`
`SYNTHESIZE OUTPUT SIGNAL
`USING PREVIOUS SUPER
`FRAME CODED LOOKAHEAD
`
`30b
`'3
`
`SYNTHESIZE OUTPUT SIGNAL
`FOR THE NON COVERED
`PORTION OF THE FRAME USING
`EXTRAPOLATION OR
`INTERPOLATION OF THE
`PREVIOUS AND/OR FOLLOWING
`PARAMETERS
`
`YES
`
`308
`
`SYNTHESIZE OUTPUT SIGNAL
`USING FOLLOWING SUPER
`FRAME CODED LOOKBACK
`
`V f
`SET n=n+1
`
`I
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 13 of 16
`
`US 6,614,370 B2
`
`FIG. 13
`
`TWO DIMENSIONAL SIGNAL HAVING SUPER-FRAME OVERLAPPING ALONG THE X AND THE Y AXES
`
`----I----
`
`I
`
`:
`orF
`Super-Frame
`E
`:
`E
`k/$11M (Xnn-Van)
`:
`:
`I
`'
`I
`:- _ _ __ . —'
`
`"/‘ 1102 Super.Frame
`I
`(xm yyn)
`'
`. _ . ,._ . |
`
`x—xn,,+Ax
`
`x=xn,1
`
`
`
`1108
`
`1105
`
`Y
`
`1114
`
`1109
`
`1112
`
`1115
`
`
`
`pB8L|B-)|00|SQXBX
`
`1101
`
`Super-Frame
`(x.,.y,.)
`
`Su
`
`r-Frame
`
`8:MM)
`
`y=y+ +Ay -v ----------- --
`
`n 1
`
`:
`
`E
`:
`11o3\-/"1
`y:yn+Ay 1
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 14 0f 16
`
`US 6,614,370 B2
`
`FIG. 14
`
`THREE DIMENSIONAL SIGNAL HAVING SUPER-FRAME OVERLAPPING ALONG THE X AXIS
`
`1 202
`
`\
`
`/
`
`1203
`
`Y
`1 204
`(\
`7'
`Super-Fram
`e /
`x
`
`I
`
`y,
`
`120
`
`Frame
`x,“
`Super-Frame
`x
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 15 0f 16
`
`US 6,614,370 B2
`
`FIG. 15
`
`THREE DIMENSIONAL SIGNAL HAVING SUPER-FRAME OVERLAPPING ALONG THE Y AXIS
`
`Y
`
`A
`
`1301
`Q1
`
`’\’
`=yn+1+Ay 0
`092’ *°
`X‘
`3* ~ 3
`3° *° / 1304
`$6“ / 1303
`<<‘ 63
`1302
`
`> X
`
`Wyn“? "" " 2
`y=yn
`
`TV
`/
`
`y=yn-1
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 16 0f 16
`
`US 6,614,370 B2
`
`FIG. 16
`
`THREE DIMENSIONAL SIGNAL HAVING SUPER-FRAME OVERLAPPING ALONG THE Z AXIS
`
`Z
`A
`
`=zn+1+Az
`
`z=zn
`
`%/~ 1404
`Super
`Frame
`
`Y
`
`w 1403
`
`Super
`Frame
`
`261 “A 1402
`
`7
`
`26-1 /
`
`

`
`US 6,614,370 B2
`
`1
`REDUNDANT COMPRESSION TECHNIQUES
`FOR TRANSMITTING DATA OVER
`DEGRADED COMMUNICATION LINKS
`AND/OR STORING DATA ON MEDIA
`SUBJECT TO DEGRADATION
`
`This Application is based upon my Provisional Patent
`Application ?led on Jan. 26, 2001 and assigned Serial No.
`60/264,494.
`
`NOTICE OF MATERIAL SUBJECT TO
`COPYRIGHT PROTECTION
`
`Material in this patent document may be subject to
`copyright protection under the copyright laWs of the United
`States and other countries. The oWner of the copyright has
`no right to exclude facsimile reproduction of the patent
`speci?cation as it appears in ?les or records Which are
`available to members of the general public from the United
`States Patent and Trademark Office, but oWner otherWise
`reserves any and all copyright rights therein.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`This invention relates generally to data communications
`and, more speci?cally, to techniques for implementing
`redundant data compression in communication or storage
`systems Which are vulnerable to errors. Such systems may
`be used to compress signals such as speech, audio, and/or
`video.
`2. Description of Prior Art
`Many communication systems, such as cellular
`telephones, personal communications systems, voice-over
`Internet protocol (VoIP), as Well as audio or video over
`packet-based netWorks, rely on electromagnetic or Wired
`communications links to convey information from one place
`to another. These communications links generally operate in
`less than ideal environments With the result that fading,
`attenuation, multipath distortion, interference, netWork
`congestion, netWork delay, and other adverse propagational
`effects may occur. Similarly, such less than ideal environ
`ments may also occur in storage systems. In cases Where
`information is represented digitally as a series of bits, such
`propagational effect may cause the loss or corruption of one
`or more bits. Oftentimes, the bits are organiZed into frames,
`such that predetermined ?xed number of bits comprises a
`frame. A frame erasure refers to the loss or substantial
`corruption of a bit or a set of bits communicated to the
`receiver.
`To provide for an ef?cient utiliZation of a given bandWidth
`(or storage space), communication (or storage) systems
`directed to signal communications (or storage) often use
`signal coding techniques. Such signal can be for example
`speech, audio, or video. Many existing signal coding tech
`niques are executed on a frame-by frame basis. For speech
`coding, such frame is about 10—80 milliseconds in length.
`The signal coder extracts parameters that are representative
`of the signal. These parameters are then quantiZed and
`transmitted (or stored) via the communications channel (or
`storage medium).
`If a frame of bits is lost, then the receiver has no bits to
`interpret during a given time interval. Under such
`circumstances, the receiver may produce a meaningless or
`distorted result. Although it is possible to replace the lost
`frame With a neW frame, estimated from the previous or the
`next frame, this introduces inaccuracies Which may not be
`
`25
`
`35
`
`45
`
`55
`
`65
`
`2
`tolerated or desirable in the context of many real-World
`applications. In predictive coding systems, such errors Will
`then propagate to all the future frames. The result is a
`poorly-reconstructed and distorted signal.
`The problem of packet loss in packet-sWitch netWorks
`employing speech, audio, or video coding techniques, is
`very similar to the problem of frame erasure in the context
`of Internet, or Wireless communication links. Due to packet
`loss, a signal decoder may either fail to receive a frame or
`receive a frame having a signi?cant number of missing bits.
`In either case, the signal decoder is presented With essen
`tially the same problem: the need to reconstruct a signal,
`despite the loss of compressed signal information. Both
`frame erasure and packet loss concern a communication
`channel (or storage medium) problem Which results in the
`loss of transmitted (or stored) bits. Therefore, for purposes
`of the present disclosure, the term “frame erasure” may be
`deemed synonymous With “packet loss”.
`
`10
`
`15
`
`SUMMARY OF THE INVENTION
`An improved signal coding technique encodes signal
`parameters into a plurality of overlapped super-frames, each
`super-frame having a predetermined number of bits. These
`encoded signal parameters may be decoded into plurality of
`non-overlapping frames. Redundant information derived
`from an overlapping portion of the super-frames is used to
`reconstruct frames Which have been subjected to frame
`erasure. This technique reduces or eliminates the need for
`prior art error concealment schemes, Which are commonly
`based on interpolation or extrapolation (or both), to recon
`struct an approximation of the signal Within the erased frame
`or frames. The invention can also be utiliZed as an enhance
`ment layer added to standard or other prior art coding
`systems. In such cases, an existing, possibly standard, cod
`ing scheme may operate as a base layer, and the present
`invention can be used as enhancement layer for less than
`ideal communication (or storage) environments.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a hardWare block diagram setting forth a signal
`coding system in accordance With a present embodiment
`disclosed herein;
`FIG. 2 is a hardWare block diagram setting forth a signal
`coding system in accordance With a present embodiment
`disclosed herein;
`FIG. 3 is a hardWare block diagram setting forth a speech
`coding system in accordance With a present embodiment
`disclosed herein;
`FIG. 4 is a prior art data structure diagram for use With a
`prior art signal compression method that could be employed
`in conjunction With the systems described in FIG. 1—FIG. 3,
`in Which the encoder encodes exactly one frame at a time,
`such that, Whenever frame erasure occurs, the decoder
`applies error concealment techniques, based on interpolation
`or extrapolation (or both), to reconstruct approximation of a
`Whole erased frame (n+1);
`FIG. 5 is a data structure diagram for use With the signal
`compression methods disclosed herein, and Which may be
`utiliZed in conjunction With the systems and methods of
`FIGS. 1—3, 11, and/or 12, in Which the encoder encodes a
`super-frame including a frame and some look-ahead
`information, such that the super-frame is longer than one
`frame but shorter than tWo frames, and Whenever frame
`erasure occurs, the decoder decodes a previous super-frame
`and applies error concealment techniques, Which can be
`
`

`
`US 6,614,370 B2
`
`3
`based on interpolation or extrapolation (or both), to recon
`struct an approximation of a portion of the erased frame
`(n+1);
`FIG. 6 is a data structure diagram for use With the signal
`compression methods disclosed herein, and Which may be
`utiliZed in conjunction With the systems and methods of
`FIGS. 1—3, 11, and/or 12, in Which the encoder encodes a
`super-frame, consists of a frame and some look-ahead, such
`that it is tWo times longer than one frame, and Whenever
`frame erasure occurs the decoder decodes a previous super
`frame and does not require any error concealment tech
`niques for the reconstruction of the erased frame (n+1);
`FIG. 7 is a data structure diagram for use With the signal
`compression methods disclosed herein, and Which may be
`utiliZed in conjunction With the systems and methods of
`FIGS. 1—3, 11, and/or 12, in Which the encoder encodes a
`super-frame, consists of a frame and some look-ahead, such
`that it is k times longer than one frame, and Whenever frame
`erasure occurs the decoder decodes a previous super-frame
`and does not require any error concealment techniques for
`the reconstruction of k erased frames;
`FIG. 8 is a data structure diagram for use With the signal
`compression methods disclosed herein, and Which may be
`utiliZed in conjunction With the systems and methods of
`FIGS. 1—3, 11, and/or 12, in Which the encoder encodes a
`super-frame, that consists of a frame and some look-back
`and look-ahead, such that it is longer than one frame but
`shorter than tWo frames, and Whenever frame erasure occurs
`the decoder decodes a previous super-frame and applies
`error concealment techniques, Which are commonly based
`on interpolation or extrapolation (or both), to reconstruct
`approximation of a portion of the erased frame (n+1);
`FIG. 9 is a data structure diagram for use With the signal
`compression methods disclosed herein, and Which may be
`utiliZed in conjunction With the systems and methods of
`FIGS. 1—3, 11, and/or 12, in Which the encoder encodes a
`super-frame, consists of a frame and some look-back and
`look-ahead, such that it is tWo times longer than one frame,
`and Whenever frame erasure occurs the decoder decodes a
`previous super-frame and does not require any error con
`cealment techniques for the reconstruction of the erased
`frame (n+1);
`FIG. 10 is a data structure diagram for use With the signal
`compression methods disclosed herein, and Which may be
`utiliZed in conjunction With the systems and methods of
`FIGS. 1—3, 11, and/or 12, in Which the encoder encodes a
`super-frame, consists of a frame and some look-back and
`look-ahead, such that it is k times longer than one frame, and
`Whenever frame erasure occurs the decoder decodes a pre
`vious super-frame and does not require any error conceal
`ment techniques for the reconstruction of k erased frames;
`FIG. 11 is a softWare ?oWchart setting forth a speech
`encoding method performed in accordance With a preferred
`embodiment disclosed herein;
`FIG. 12 is a softWare ?oWchart setting forth a speech
`decoding method performed in accordance With a preferred
`embodiment disclosed herein;
`FIG. 13 is a data structure diagram of a tWo-dimensional
`signal compression method in accordance With a preferred
`embodiment disclosed herein for use in conjunction With the
`systems and methods of FIGS. 1—3, 11, and/or 12, in Which
`super-frames have overlap Ax along the X axis and overlap
`Ay along the Y axis. The encoder encodes a super-frame
`including a frame and some X axis look-ahead information,
`as Well as some Y axis look-ahead information. This encod
`ing is accomplished such that, along the X axis, as Well as
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`4
`the Y axis, the super-frame is longer than one frame, but
`shorter than tWo frames. Whenever frame erasure occurs, the
`decoder decodes a previous super-frame and provides error
`concealment techniques, Which can be based upon interpo
`lation or extrapolation (or both), to reconstruct an approxi
`mation of a portion of the erased frame along each axis;
`FIG. 14 is a data structure diagram of a three-dimensional
`signal compression method in accordance With a preferred
`embodiment disclosed herein for use in conjunction With the
`systems and methods of FIGS. 1, 3, 11, and/or 12, in Which
`super-frames have overlap Ax along the X axis. The encoder
`encodes a super-frame including a frame and some X axis
`look-ahead information, such that along the X axis the
`super-frame is longer than one frame but shorter than tWo
`frames, and Whenever frame erasure occurs, the decoder
`decodes a previous super-frame and applies error conceal
`ment techniques, Which can be based on interpolation or
`extrapolation (or both), to reconstruct an approximation of a
`portion of the erased frame along the X axis;
`FIG. 15 is a data structure diagram of a three-dimensional
`signal compression method in accordance With a preferred
`embodiment disclosed herein for use in conjunction With the
`systems and methods of FIGS. 1, 3, 11, and/or 12, in Which
`super-frames have overlap Ay along the Y axis. The encoder
`encodes a super-frame including a frame and some Y axis
`look-ahead information, such that along the Y axis the
`super-frame is longer than one frame but shorter than tWo
`frames, and Whenever frame erasure occurs, the decoder
`decodes a previous super-frame and applies error conceal
`ment techniques, Which can be based on interpolation or
`extrapolation (or both), to reconstruct an approximation of a
`portion of the erased frame along the Y axis; and
`FIG. 16 is a data structure diagram of a three-dimensional
`signal compression method in accordance With a preferred
`embodiment disclosed herein for use in conjunction With the
`systems and methods of FIGS. 1, 3, 11, and/or 12, in Which
`super-frames have overlap AZ along the Z axis. The encoder
`encodes a super-frame including a frame and some Z axis
`look-ahead information, such that along the Z axis the
`super-frame is longer than one frame but shorter than tWo
`frames, and Whenever frame erasure occurs, the decoder
`decodes a previous super-frame and applies error conceal
`ment techniques, Which can be based on interpolation or
`extrapolation (or both), to reconstruct an approximation of a
`portion of the erased frame along the Z axis.
`
`DETAILED DESCRIPTION OF THE PRESENT
`EMBODIMENT
`
`Refer to FIG. 1, Which is a is a hardWare block diagram
`setting forth a signal coding system in accordance With a
`preferred embodiment of the invention to be described
`hereinafter. A signal, represented as x(i), is coupled to a
`conventional signal encoder 50. Signal encoder may include
`elements such as an analog-to-digital converter, one or more
`frequency-selective ?lters, digital sampling circuitry, and/or
`an input transformation (denoted by
`Irrespective of the speci?c internal structure of the signal
`encoder 50, this encoder produces an output in the form of
`a digital bit stream D. The form of a digital bit stream D, is
`the encoded data of x(i), and hence, includes “parameters”
`(denoted by D={T, I31, .
`.
`. ,FM} Which correspond to one or
`more characteristics of
`Since
`is a function Which
`changes With time, the output signal of the signal decoder is
`periodically updated at regular time intervals. Therefore,
`during a ?rst time interval T1, the output signal comprises a
`set of values corresponding to parameters D={T, I31, .
`.
`.
`
`

`
`US 6,614,370 B2
`
`5
`,FM}, during time interval T1. During a ?rst time interval T2,
`the value of parameters D={T, I51, .
`.
`. ,FM}, may change,
`taking on values differing from those of the ?rst interval.
`Parameters collected during time interval T1 are represented
`by a plurality of bits (denoted as D1) comprising a ?rst
`frame, and parameters collected during time interval T2 are
`represented by a plurality of bits D2 comprising a second
`frame. Therefore Dn refers to a set of bits representing all
`parameters collected during the n-th time interval.
`The output signal encoder 50 is coupled to MUX 10 and
`may or may not be coupled to logic circuitry 51. MUX 10
`is a conventional digital multiplexer device Which in the
`present context, combines the plurality of bits representing
`a given Dn onto single signal line. D” is multiplexed onto
`this signal line together With or Without a series of bits
`denoted as D”, produced by logic circuitry 51.
`The output of multiplexer 10, including a multiplexed
`version of D” and D”, is conveyed to another location over
`a communications channel (or is stored on a storage
`medium) 11. At the receiving end of the channel, the
`received (or read from storage medium) signal, is fed to the
`demultiplexer DEMUX 13, that processes it to retrieve D”
`and D‘n. The D” and D” are then processed by signal
`decoder 60 to reconstruct the output signal
`Suitable
`devices for implementation of decoders for signals such as
`speech, audio or video decoder are Well knoWn to those
`skilled in the art. Signal decoder 60 is con?gured to decode
`signal Which Was encoded by the signal encoder 50.
`FIG. 2 is a hardWare block diagram setting forth a signal
`coding system in accordance With a present embodiment
`disclosed herein. A signal is fed to input 01 of an input
`(analysis) transformation 02. The transformation 02 may or
`may not be derived from the input signal. The transforma
`tion 02 may or may not be quantiZed. If the transformation
`02 is quantized, then its parameters are placed in signal line
`04. The transformation’s output is the input transformed
`signal 03 (denoted by y(i)). The selection and operation of
`a suitable transformation decoder for signals such as speech,
`audio or video, or other types of signals, is a matter Within
`the knoWledge of those skilled in the art.
`The input transformed signal on line 03 is input to a
`transformed signal encoder 05. The transformed signal
`encoder 05 consists of parameter extraction device 06, and
`may or may not consist of parameter extraction memory 07.
`Parameter extraction device 06 is equipped to isolate and
`remove one or more parameters from the input transformed
`signal. The parameter extraction device 06 may be imple
`mented using a parameter extraction memory 07 for storing
`the extracted values of one or more parameters. In the
`example in FIG. 2, several parameters are extracted from the
`transformed signal, denoted by P1(n) 08, .
`.
`. , PM(n) 09. Note
`that the parameter extraction device 105 could extract a
`feWer number of parameters or a greater number of param
`eters than that shoWn in FIG. 2.
`All parameters are processed by channel encoder and
`MUX 10, Where all or some of the parameters are processed
`by its logic circuitry 51. All original and processed param
`eters are multiplexed together using a conventional multi
`plexer device, MUX 52. The multiplexer signal is sent out
`over a conventional communications channel (or stored to
`storage medium) 11.
`The communications channel (or storage device) 11 con
`veys the output of the channel encoder and MUX 10 to a
`frame erasure/error detector 12. The frame erasure/error
`detector 12 is equipped to detect bit errors and/or erased
`frames. Such errors and erasures typically arise in the
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6
`context of practical, real-World communications channels
`Which may employ Wired and/or Wireless electromagnetic
`communications links (as Well as in the context of storage
`media Which utiliZe optical, magnetic, or semiconductor
`devices) in less-than-ideal operational environments. These
`communications links and/or storage media are represented
`schematically in FIG. 2 as communications channel 11.
`Frame erasure/error detector 12 is coupled to a DEMUX
`and channel decoder 13. Frame erasure/error detector 12
`conveys the demodulated bitstream retrieved from the com
`munications channel (or storage medium) 11 to the DEMUX
`and channel decoder 13, along With an indication as to
`Whether or not a frame erasure has occurred. DEMUX and
`channel decoder 13 processes the demodulated bitstream to
`retrieve parameters T(n) 22, and P1(n) 14, .
`.
`. , PM(n) 15. In
`addition, the DEMUX and channel decoder 13, or the error
`concealment device 25, may be employed to relay the
`presence or absence of a frame erasure, as determined by
`frame erasure/error detector 12, to a transformed signal
`decoder 16, and/or to an output inverse (synthesis) transfor
`mation 23. Alternatively, a signal line may be provided,
`coupling frame erasure/error detector 12 directly to trans
`formed signal decoder 16 and/or to an output inverse
`(synthesis) transformation 23, for the purpose of conveying
`the existence or non-existence of a frame erasure to the
`transformed signal decoder 16 and/or to an output inverse
`(synthesis) transformation 23.
`The physical structure of the transformed signal decoder
`16, for decoding of signals such as speech, audio, video or
`other types of signals, is a matter Well knoWn to those skilled
`in the art. Functionally, the transformed signal decoder 16,
`examines a plurality of parameters T(n) 22, and P1(n) 14, .
`.
`. , PM(n) 15 and fetches one or more entries from codebook
`tables 17 stored in transformed signal decoder 16 to locate
`a table that is associated With, or that most closely corre
`sponds With, the speci?c values of input parameters input
`into the transformed signal decoder 16. The table entries in
`the codebook table 17 may be updated and augmented after
`parameters for each neW frame are received. In such case,
`neW and/or amended table entries are calculated by trans
`formed signal decoder 16 as the output inverse (synthesis)
`transformation 23 produces reconstructed signal output.
`These calculations are mathematical functions based upon
`the values of a given set of parameters, the values retrieved
`from the codebook tables, and the resulting output signal at
`the reconstructed signal output 24. The use of accurate
`codebook table entries 17 results in the generation of recon
`structed signal for future frames, Which most closely
`approximates the original input signal. The reconstructed
`signal is produced at the reconstructed signal output 24. If
`incorrect or garbled parameters are received at transformed
`signal decoder 16, incorrect table parameters Will be calcu
`lated and placed into the codebook tables 17. As discussed
`previously, these parameters can be garbled and/or corrupted
`due to the occurrence of frame erasure or bit errors. These
`frame erasures or bit errors Will degrade the integrity of the
`codebook tables 17. A codebook table 17 having incorrect
`table entry values Will cause the generation of distorted,
`garbled reconstructed signal output 24 in subsequent frames.
`Transformed signal decoder 16 is equipped With memory
`used to store parameters from present frame 20, and from Q
`frames 19 that proceed frame n. If no frame erasure has been
`detected by frame erasure/error detector 12, then the
`extracted code vectors are computed by transformed signal
`decoder 16 on line 21. If a frame erasure is detected by frame
`erasure/error detector 12, then the transformed signal
`decoder 16 can be used to compensate for the missing frame.
`
`

`
`US 6,614,370 B2
`
`7
`In the presence of frame erasure or bit errors, the trans-
`formed signal decoder 16 will not receive reliable values of
`decoded parameters T(n) 22, and P1(n) 14, .
`.
`.
`, PM(n) 15,
`for the case where the frame n is erased. Under these
`circumstances,
`the transformed signal decoder 16 is pre-
`sented with insufficient information to enable the retrieval of
`code vectors from the transformed signal decoder memory
`18. If frame n had not been erased, th