Note: Descriptions are shown in the official language in which they were submitted.
12~4876
DESCRIPTION
DATA COMPRESSION SYSTEM AND
METHOD FOR AUDIO SIGNALS
BACKGROUND OF THE INVENTION
Systems which include means for converting
analog signals to digital form, then compression
filtering and Huffman encoding the signals for
recording or for transmission to a remote location,
together with playback or receiver means which
include a Huffman decoder, a digital reconstruction
filter and means for converting the decoded and
filtered digital signals back to analog form are
shown in U.S. Patent No. 4,449,536 issued May 22, 1984,
and in an article by U.E. Ruttimann and H.V. Pipberger
entitled "Compression of the ECG by Predlction or
Interpolation and Entropy Encoding", IEE Transactions on
Biomedical Engineering, Vol. BME-26, No. 11, pp. 613-623,
Nov. 1979. A similar system is shown in an article by
K.L. Ripley and J.R. Cox, Jr. entitled, "A computer System
for Capturing Transient Electrocardiographlc Data", Pro.
Comput. Cardiol. pp. 439-445, 1976. Wi-th the
present invention, the average bit rate of an
..
1224876
analog-to-digital converted audio signal, such as a
music, electrocardiogram, or electroencephalogram
signal, is reduced sufficiently to allow for digital
transmission thereof over low-grade transmission lines
and/or recording and playback of a worthwhile quantity
of signal using a relatively small amount of recording
medium and employing known digital recording and
playback techniques.
SUMMARY OF THE INVENTION
Audio signals, such as music, to be transmitted,
or recorded, are converted to digital form by analog
to digital converter means. The digital signals then
are supplied to a digital compression filter to
generate digital, compressed signals. The compressed
audio signals are supplied to an encoder, such as a
truncated Huffman encoder, for encoding the same. The
digital output from the encoder is recorded by use
of digital recording means, and~or transmitted to a
remote receiving loca~ion. At a playback unit or
receiving station the encoded signal is decoded by a
decoder, and the decoded signal is supplied to a digital
decompression filter. The output from the decompression
filter is converted to analog form by digital to analog
converter means to provide a reproduction of the audio
signals. A digital compression-decompression filter
combination is used which minimizes the average bit
length of the recorded, or transmitted, digital signal
words. The transfer function of the digital compression
filter means includes zeros on the unit circle in the
Z-plane, and the transfer function of the digital
decompression filter includes poles on or inside the
1224876
unit circle in the Z-plane at the same angular positions
as the zeros of the compression filter. Zeros and poles
of the compression and reconstruction filters,
respectively, are limited to angular positions of 0,
+41.41, +60, +90, ~120, and 180. Compression
filter operation is performed without truncation, or
round-off,whereas decompression filter operation is
with truncation, or round-off. The resultant system
frequency response for analog signals is high-pass
which may include one or more small high frequency
notches, For music signals, the resultant filter has
a low frequency cut-off of between 0-15 Hz to accommodate
audio frequency signals which range, approximately, from
15 Hz to 20,000 Hz.
An unstable compression-decompression filter
combination results when the decompression filter
transfer function includes poles on the unit circle
of the Z-plane. For such arrangements, transfer of
the output from the Huffman encoder may include use
of an error-checking code and error detecting means
for detection of errors in said transfer to the
Huffman decoder An error signal is produced in
response to the detection of an error in such
digital signal transfer, which error signal is
supplied to the decompression filter for use in
momentarily mov:Lng the poles of said filter
inwardly, inside the unit circle thereby enabling
the system to recover from said signal errors.
The above-described error signal detection
and inward movement of the poles of the transfer
;
1 ~24~i7~
function in the 7,-plane of the decompression filter
in response to error detection also may be used in
those systems having stable compression-
decompression filter combinations to accelerate
recovery from signal errors.
Instead of using an error checking code and
error signal detecting means in those systems which
include an unstable compression-decompression
filter combination, the system may be operated to
periodically transfer a series of actual signal
values from the A/D converter to the reconstruction
filter thereby periodically "reinitializing" the
reconstruction filter when errors have occurred.
In the case of music signal compression,
transmission of actual signal val~es every~ say, 6
to 16 milliseconds would be adequate. The number
of successive actual signal values reguired to be
periodically transmitted is dependent upon the
order of the decompression filter; the number of
actual signal values sent being equal to said
order.
BRIEF DESCRIPTION _ THE DRAWINGS
The invention will be better understood from
the following description when considered with the
accompany:ing drawings. ,[n the drawings, wherein
like reference characters refer to the same parts
in the several views:
Figs. lA and lB together show a block diagram
of a data reduction system; a digital recording and
transmitter section being shown in Fig, lA and a
playback and receiver section being shown in Fig.
lB;
1~4876
Fig. 2 shows a waveform and graphic
representations of signals appearing at various
locations in the data compression system shown in
Figs. lA and lB;
5Fig. 2A shows the frequency response of high
frequency deemphasis and high frequency emphasis
filters which are included adjacent the input and
output, respectively, of the data reduction system;
Fig. 3 is a graphic representation of encoded
difference signals showing the format employed for
encoding those difference signals which are outside
a predetermined signal range;
Fig. 4 is a graph for use in showing the
relationship between the probability that a digital
sample signal value will occur within a certain
quantization level and the size of the quantization
level;
Fig. 5 shows zeros of a second order
compression filter transfer function on a unit
circle in the Z-plane;
Fig. 6 shows a plurality of z-transform zero
positions which may be employed in the compression
filter embodying this invention;
Fig. 7 is a graph showing the frequency
response of three different compression filters
having ~eros on the unit circle of the z-transform
at some of the positions identified in Fig. 6;
Fig. 8 is a block diagram showing details of
a compression filter of the type which may be used
in the present system;
Fig. 9 is a table showing a truncated lluffman
code of a type which may be used in the present
invention;
Fig. 10 shows the zero-pole pattern of a
compression-reconstruction filter con,bination which
1~24876
may be employed in the present system which results
in a stable system without the need for error
detection;
Fig. 11 shows the frequency response of the
compression-reconstruction filter combination
having the ~ero-pole pattern illustrated in Fig.
10;
Figs. 12A and 12B are similar to Figs. lA and
lB, respectively, but showing a system which
includes a check bit generator and error checking
means for use in momentarily moving the poles of
the reconstruction filter inwardly when a bit error
is detected;
Fig. 13 shows a zero-pole pattern of a
compression-reconstruction filter combination in
which poles of the reconstruction filter are
momentarily moved inwardly to accelerate recovery
from transients;
Fig. 14 is a block diagram showing details of
a reconstruction filter which may be used in this
invention;
Fig. 15 shows the zero-pole pattern of
another compression-reconstruction filter
combination which may be used in systems embodying
the present invention; and
Fig. 16 is a graphic representation of
Huffman encoded signals present in a system wherein
actual digital signal values are periodically
transferred to the reconstruction filter to
periodica:Lly reinitialize the same.
Reference first is made to Fig. lA
wherein the digital recording and transmitting
portion of a data compression system is shown
comprising an analog to digital converter (A/D
converter) 20 for conversion of an analog audio
12Z4876
signal f(t) into digital form, the nth sample from
the analog to digital converter 20 being identified
as fn. At A of Fig. 2, an analog signal 22 is
shown which comprises an input to the analog to
digital converter 20. For purposes of illustration,
the audio input signal may comprise a music signal
which ranges in frequency from approximately 15 to
20,000 Hz. The form of the analog to digital converter
output, shown at B of Fig. 2, comprises samples
fn 1 through fn+i of equal length words. The analog
to digital converter 20 operates at a sampling rate
established by control signals from a timing and
control unit 24 supplied thereto over timing line 26.
As employed herein, line 26 from the timing and
control unit 24 represents a plurality of timing
circuit outputs, one or more of which are supplied
to the system elements for proper system timing and
control. Inputs also are supplied to the timing and
control unit over line 28 for control thereof by
signals from various other system elements. The
A/D converter 20 operates in a conventional manner
at a fixed sampling rate and with a fixed word length
output. For purposes of description only, and not by
way of limitation, the A/D converter may operate at a
sampling rate of 44KHz and with a 14 bit word length.
The output from the A/D converter 20 is supplied
to a linear digital compression filter 30 through
a digital filter 23 which deemphasizes the high
frequency portion of the digital audio frequency
signal from the A/D converter 20 to reduce the
signal entropy. The frequency response of filter
23, together with the frequency response of a
digital filter 75 included in the playback and
12~48~,
receiver portion of the system is shown in Fig. 2A.
For simplicity, the digital output from filter 23,
as well as the digital input, is identified as fn.
Obviously, an analog filter having a similar
S frequency response may be included at the input to
the A/D converter 20 in place of the digital filter
23 at the output therefrom.
For present purposes, the digital compression
filter 30 is shown to include an estimator 32 and
subtracting means 34. The estimator 32 provides an
estimate of fn here identified as fn based upon
actual samples occurring both before and after the
sample fn to be estimated. Estimators for
providing such estimated fn values are, of course,
well known. A difference signal ~ n is produced by
the compression filter 30 comprising the difference
between the actual signal input fn and the
estimated signal value fn by subtraction of the
estimated value from the actual value at
subtracting means 34, as follows:
n = fn ~ fn (1)
In Lhe graphic signal representation of the
compression filter output shown at C in Fig. 2,
difference signals a n~ ~ n+1~ ~ n+2~-----
~n+i are shown. In accordance with one feature ofthis invention, arithmetic operations of the
digital compression filter 30 are performed without
truncation or round-off whereas arithmetic
operations of an associated digital decompression,
or reconstruction filter, described below, are
performed with truncation, or round-off. As seen
in Fig. 2C, the compression filter output comprises
12~487fi
untruncated compressed signals which are18 bits in
length.
It here will be understood that the present
invention is not limited to use with the illustrated
compression filter in which the output ~ n comprises
the difference between the actual signal input fn and
an estimated value ~n' Other compression filters
may be used havingdifferenttransforms in which the
compression filter output ~ is not a direct
function of the difference between the actual input
fn and an estimated value thereof, ~ . The use of
the term "difference" signal values ~ n is intended
to also identify the output from other suitable
compression filters.
The compressed signal values ~ n are
supplied, through switch 35, to an encoder 40
employing a truncated Huffman code for encoding the
same. Huffman encoding is disclosed in U.S. Patent
No. 4,396,906, issued August 2, 1983, entitled
"Method and Apparatus for digital Huffman Encoding"
by Charles S. Weaver, which patent ls assigned to
the same assignee as the present invention.
Brieflyt the Huffman encoding -technique makes
use of the fact that the compression filter reduces
the entropy of t:he signal output, ~ so that there can
be a reduction Ln the total number of bits in the
Huffman encoded signal over the input signal. A
single code word is assigned to infrequently
occurring diffexence signals, and supplied as a
label for the actual difference signal value A n.
In Fig. lA, the encoder 40 output is designated
h( A ) and, at D in Fig. 2, the values h( A n)~
224876
h( ~ n+1) etc. represent encoded values of ~ n-
A n+1~ etc. The most frequently occurring value of
A n (here zero) is encoded using the shortest code
word. A truncated Huffman code is disclosed in
U S. Patent Ilo. 4,396,906 which is
readily implemented using a simple encoder and
decoder. The encoder 40 output comprises code
words for the most frequently occurring values of
~ n~ together with a combined code word label and
actual value of the compressed signal ~n for less
frequently occurring values of ~ n. For purposes
of illustration, if the compressed signal value
exceeds ~3 then the 0ctual compressed signal ~ n
together with a code word label is produced at the
encoder output. At Fig. 3, wherein several encoded
compressed values are shown, it will be seen that
the encoded value for ~ n+2 comprises a label
together with the actual compressed signal A n+2~
wherein ~ n~2 comprises an infrequently occurring
compressed signal value; that is, some value
outside the rsnge of ~3.
The encoded signals from encoder 40 are
recorded and/or transmitted to a remote receiver.
For recording, the encoder output is connected
through a switch 48 to a recording unit 50 for
recording of the encoded difference signals,
labeled h( ~ n) signals. With the switch 48 in the
other, broken line, position, the encoder output is
supplied to a buffer memory 52 and thence to a
digital modem 54 for transmission over transmission
line 56. In certsin embodiments of this invention,
check bits are generated for recording and/or
transmitting along with encoded compressed signals -
h( e, n). In some embodiments of the invention,
digital input signals fn sometimes are supplied to
1~4~376
11
the input of the Huffman encoder through switch
means 35, which signals serve to initialize, or
reinitialize, the associated digital reconstruction
filter described below.
Recorded encoded digital signals, such as
those recorded at recording unit 50 of Fig. lA are
reproduced using the system shown in Fig. ls, which
system includes a playback unit 6Q. Recorded
encoded digital signals from the playback unit 60
are supplied through switch 64 to a decoder 66 for
decoding the truncated Huffman encoded signals. At
the decoder 66, the Huffman code words are converted
to the original compressed signals ~ n. Where the
Huffman code word comprises a labeled actual
compressed signal, the label is stripped therefrom,
and the actual compressed signal without the label
is supplied to the decoder output. Encoding and
decoding means which may be used in the present
invention are described in detail in the above-
mentioned U.S. Patent No. 4,396,906. Coding and
decoding are discussed in greater detail below
under the heading "Encoding-Decoding".
The compressed signais ~ n from the decoder
66 are supplied to a linear reconstruction, or
decompression, filter 70 through a buffer memory
72. The decoder output signals are produced at
slightly varying rates, and the buffer memory 72 is
included to accommodate the input rate requirements
of the reconstruction filter 70. The reconstruction
filter 70 converts the compressed signals A n to
equal length sample signals fn(out) which closely
match the input sample signals f to the
compression filter 30. As noted above, one
feature of this invention involves compression
~2'~4876
12
filtering without truncation and decompression
filtering with truncation. In Fig. 2F, thl
truncated reconstruction filter output fn(out),
fn+1(out) etc. is shown to comprise words of 24
bits. Without truncation, the reconstruction
filter would be required to handle word lengths of
approximately 36 to 40 bits which, for consumer
products, is not now feasible at reasonable cost.
~easons that suitable data compression with minimum
distortion is obtained using a compression-
decompression filter combination wherein
compression filtering is effected without
truncation and decompression filtering is effected
with truncation will become apparent hereinbelow.
A digital to analog converter (D/A converter)
74 converts the signal samples fn(out) from the
digital reconstruction filter 70 to analog form,
for reproduction of the analog signals. A digital
filter 75 which emphasizes the high frequency
components of the signal output is included in the
connection of the output from the digital
reconstruction filter output to the D/A converter.
The frequency response of the filter 75 is shown in
Fig 2A, adjacent the frequency response of the
input filter 23. For simplicity, the same symbol
fn(out) is employed at the input and output of the
filter 75. Obviously, an analog filter having a
similar frequency response may be included in the
output from the D/A converter, in place of the
digital filter 75. A receiver timing and control
unit 76 supplies timing signals to the various
receiver elements over line 78 for proper timing of
the receiving operation. Also, control signals for
the unit 76 are supplied thereto over line 80 from
various elements of the receiver for control
4~37~;
13
thereof.
For transmission without recording, the
encoded signals are transmitted over line 56 (from
Fig. lA to Fig. lB) to a digital modem 82 at the
receiver. The modem output is buffered by buffer
memory 84, and the buffer memory output is supplied
through switch 64 in the broken line position to
the decoder 66 for decoding and subsequent
processing in the manner described above.
QUANTIZATION OF ANALOG MUSIC SIGNALS
For purposes of illustration, and not by way
of limitation, a music analog signal is considered
for an input to the present system of this
invention.
The entropy of a binary analog to digital
(A/D) converted x bit long sample is
H(q) = ~ - Pi log2Pi (2)
~ =l
where there are 2X possible values of the sample
and Pi is the probability that the ith possible
value will occur. Let the size of the quantization
level be q and, for simplicity, assume that the ith
quantization, which gives the ith value, is from
q(i-l) to qi. Then, as seen in Fig. 4, signal
before analog to digital conversion will fall in
the range q(i-l) to qi. In Fig. 4, the shaded
area is the probability that the signal f(t) falls
into the ith quantization.
Now, assume further that the size of the
quantization level, q, is small compared to the
standard deviation, ~ , of the analog music signal.
1~4876
14
If the A/D converter word length is increased by
one bit, the quantization size is cut in half and,
as shown by dashed lines in Fig. 4, two
quantization bins are formed from the original bin.
For small q, the areas on either side of the
vertical dashed line will be almost equal whereby
the probability that f(t) will fall into one of the
two new bins is approximately Pi/2. Therefore, the
contribution of the two new bins to the entropy of
the n+l bit long word vary nearly is
r P P jl
-2~ ~ log2
f Pi
= -21 2 (log2pi-l)
= - Pi log2Pi + Pi (3)
The entropy of the (x+l) bit long word is
2X 2X5 H( 2 J =~ ~ Pilg2Pi + ~ Pi = H(q) + 1 (4)
i=l ~=
From the above, it will be seen that as the
bit length is increased, the increase in entropy
will converge to one bit for each bit added to the
word length. The argument when the first
quantization bin is centered about zero (the usual
case) is slightly more complex, however, the result
is the same.
The Pi and entropies have been evaluated by
numerical integration with various ratios of 6 to
q for the Gaussian distribution. Table 1, be]ow,
of calculated entropy increases at different ratios
of ~ /q, shows that the entropies increase very
4876
closely to one bit each time q is cut in half or
when the word length is increased by one.
Table l
CAI.CIJLATED INCREASE IN ENTROPY AS
5QUANTIZATION SIZE IS RE`DIJCED
6 Entropy
q (bits)
0.5 0.58
1 1.16
2 1.93
4 2.82
8 3,77
16 4.75
32 5,73
15COMPRESSION FILTERING OF
QUANTIZED MUSIC SIGNALS
The average word length of a Huffman encoder,
such as encoder 40 to which the output from the
compress:ion filter 30 is supplied is bounded as
follows:
H(q) < average word length < H(q) + 1 (5)
If a coefficient in the equation(s) that is
used to realize the compression filter has a non-
integer value the quanti~ation level at the filter
output will be reduced; i.e., the minimum
difference between possible output values will be
decreased and H(q) w-.ll be increased. For example,
1~4876
16
consider the following two cornpressor equations to
implement the compressioll filter transform.
~ n = fn ~ 2fn-1 ~ fn-2 (6)
and
n fn - 2fn_1 + 2 D~+lfn 1
+fn 2 - 2-m+1fn 2 +2-2mfn_2 (7)
where m is a positive integer.
The Z-transform of Eq (6) has two zeros at
(1,0) and Eq (7) has two zeros at (1-2-m, 0) in the
Z-plane. The ~ n in Eq (7) will have values
spaced a distance of 2 2mq. When m is large, the
6 from both filters will be approximately equal
but the ~ /quantization level ratios will differ
by a factor of 2-2m. Therefore, the entropy of Eq
(7) will be approximately 2m more bits than the
entropy of Eq(6), and after Huffman encoding the
average bit length will be approximately 2m bits
longer.
It will be noted that multiplying the right
side of Eq(7) by 22m returns the quantization level
to q, but the standard deviation is increased by a
factor of 22m so that the ratio is unchanged.
Filter Weights Versus Word Length
A general form of a compression filter
difference equation is
Q
n = ~ aifn-j+l
i =l
where ai is a constant. If ai can be represented
by a finite length binary number, it can be
expressed as
12~87fi
17
ai = ~-~ bij2i , (9)
where bij = 0 or +1 and j can have positive or
negative values. Any negative j and a non-zero bij
means that fn 1 is shifted right and added; jO
bits must be added to the least-significant end of
the arithmetic word, where jO is the most negative
j with non-zero bij.
The Z-transform of Eq (6) is
G(Z) = (1 _ 2z-l + z-2) = (1 _ z-1)2 (10)
which can be represented by two zeros at (1,0) in
the Z-plane as seen in Fig. 5. The frequency
response at fO of an all-zero digital filter [e.g.,
Eq(6) or Eq(7)] is the product of the distances
from the point exp (j2~T fT) to each of the zeros
and the gain constant [equal to 1 in Eq(10)], where
f is the frequency and T is the time between
samples. Thus, the frequency response of Eq(10)
i s : .
R(fo) = d2 (11)
If there are n zeros at (1,0),
R(fo) = dn (12)
These compression filters reduce the entropy for
the following reason: if the A/D sampling rate is
44 x 103 samples per sec, the point (-1,0) on the
unit circle corresponds to a frequency of 22 KHz.
The centroids of the music spectra usually will be
less than 1 KHz, so that most of the spectral
points correspond to points on the unit circle that
lX~487~i
18
are near (1,0). The vslue of d (and dn) will be
much less than one, and the integral of the
spectrum value time dn as B function of e
(where ~ , 2q~ f) will be less thsn the variance of
the input spectrum (R~l). A reduced var~ance means
a reduced entropy.
The value of d is greater than one when
~ >60 (f ~ 7.33RHz) so that spectral components
sbove 7.33 KHz are amplified by dn for filters with
all of the zeros at (1,0). There is a value of n
such that increasing n above this value amplifies
the total energy above 7.33 R~z more than the total
energy below 7.33 RHz is attenuated. This value of
n minimizes the output variance and the entropy
because the input and output q are the same when
K = 1. This can be seen as follows:
G(~) =K(l _ z-l)n
n
=K ~ n! (-1) _ z-i (13)
~__ i! (n-i)!
i=no
eK~ aiz i
i =O
where the ai are the constants that are used in
Eq(~), and K is the gain constant. The ai are
integers that can be expanded [as in Eq (9)]
without negative j and, therefore, q is not
reduced.
Note that different values of R do not change
the ratio ~ /q or the entropy when K is a power of
two, because the input word is only shifted. Thus,
the n that minimizes the entropy for R ~ 1 also
minimizes it for other R and the minimum entropy is
obtained when K is a power of two.
1224876
19
Two other zero positions on the unit circle
that do not reduce q sre at (-1,0) and (the
complex pair) at (0,1) and (0,-1). The Z-
transforms are:
G(Z) ~ (1 + z~l)n
[n zeros at (-1,0)] and
G(Z) c (1 + z-2)n (15)
[n zeros at (0,1) and n zeros at 0, -1].
The two other complex-pair positions that do
not change q have the following transforms:
G(Z) = (1 _ z-l + z-2 )n (16)
(which places n zeros on the unit circle at angles
of +60 from the origin and n at -60) snd
G(Z) ~ (1 + z-l + z-2 )n (17)
15 (which p:Laces n zeros at + 120 and n at -120).
The above are the only zero positions inside or on
the unit circle that do not decrease q. There are
none outside the uni~ circle that result in a
satisfactory reconstruction filter.
One other zero position that is of interest
for music data compression is the complex pair at
41.41 on the unit circle. The transform is
G(Z) ~ .5z~l + z-2. (18)
This angle corresponds to 5.06 ~Hz and q is divided
by 2 for each complex pair.
12'~A876
In accordance with one aspect of the present
invention a compression filter is employed in which
the Z-transform thereof has zeros on the unit circle
at at least one of the above-identified complex-pair
positions (i.e. ~41.41, ~60~, ~90, +120 and 180).
In addition to these zero positions, the compression
filter may also have one or more zeros on the unit
circle of the Z-transform at zero degrees. The
above-described zero positions are shown in Fig. 6.
As noted above, these zero positions on the unit circle
minimize the entropy, and the combination of zero
positions employed is dependent upon the spectrum
of the signal to be compressed. For example,
zeros can be placed at the ~60 points to reduce
the part of the output variance that is due to high
frequencies (from say 3 to 14KHz~ so that more
zeros can be used at 1,0. In Fig. 7, the frequency
response of three different compression filters is
shown which filters have zeros on the unit circle
of the Z-transform at OQ; OQ and ~60; and 0, ~90
and ~120. It will be seen that the useable zero
positions for entropy minimization allow for design
of compression filters having a wide range of
frequency responses.
Of course, limitations are encountered when
the number of ze!ros is increased. The amount of
calculation required is directly proportional to
the number of zeros, and the filter arithmetic word
length increases by at least one for each
additional zero. Also, recovery during reconstruction
from bit errors will take longer as the number of
zeros is increased.
After the compression filter transfer
function has been chosen, the entropy that will be
obtained can be estimated as follows: the music
spectrum S(f~ is measured, and the integral
12~87~
21
¦G(Z) ¦2 s ( e;i2~fT) d~ (19)
is integrated along the unit circle fron' (1,0) to
(-1,0), where
S~ ( ~j2~ fT)= S(f) .
The square root of the integral is the ~ of the
compression filter output. Table 1 now can be used
to estimate H(q).
Compression Filter
Although it will be apparent that standard
digital techniques may be used for implementing the
above described compression filter transforms,
including the use of a programmed digital computer,
a block diagram of a second order digital
compression filter suitable for use in implementing
equation (6) is shown at Fig. 8~ to which figure
reference now is made. The illustrated compression
filter includes a series of shift registers 102,
104, and 106 into ~hich consecutive sample si&nals
from the A/D converter, through filter 23, are
shifted. In Fig. 8, for purposes of description,
the registers, 102, 10~ and 106 are shown to
contain samples fn~ fn 1~ fn 2~ respectively. For
14-bit samples, 14-bit registers are employed. The
register outputs are connected to a digital
multipl~exer 108 for selective connection of the
sample signals to an arithmetic and logic unit
(ALU) 110. The multiplexer 108 and ALU 110 are
under control of timing and control unit 24.
As noted above in the description of Fig. lA,
the digital compression filter 30 may include an
estimator 32 having an output comprising an
4~7fi
2~
estilllated sample vslue ~n hased upon actual sam~Jles
fn 1 and fn+1 occurring hefore and after the samp]e
fn to be estimated. Often, prior art estimators
are used which provide an output,
fn = alfn+l + a2fn-1 (20)
where tht-~ coefficients al and a2 are chosen to
minimize the mean square error of the difference
n~ here ~ n = fn ~ ~n~ as noted in equation (1),
above. Ft)r al = a2 = 1, equations (1) and (20) may
bt-~ combined to give
~ n = fn+l - 2fn + fn-l (21)
(It here will be noted that equations (6) and (21)
are equivalent.)
Fquation (21) may be utilized by the
illustrated compression filter in the generation of
the compressed signal ~n An estimate fn of the
sample fn is made using the samples either side of
n n-l and fn~ Dut not fn itself. Under
control of unit 249 the words fn 1 and fn+l are
moved :into the ALU 110 through the multiplexer 108
and adtled. The actual sample fn then is moved into
the AL.U 110 through the multiplexer 108, and
multiplied by 2. ~iultiplying by 2 simply involves
shifting of the bits toward the most significant
bit. The actual sample fn~ multiplied by 2, is
subtracted from ~n to provide the compressed signal
value f~n at the ALU 110 output, which then is
supplied to encoder 40. The arithmetic in the ALU
110 is done in a word length sufficiently long to
ensure against truncation or round-off error. It
will be seen that data compression by the above-
lZ~4~
described appsratus includes estimating a ssmple~alue by interpolation.
HUFFMAN ENCODING AND DECODING
As noted abo~e, Huffman encoding and de~od$ng
means suitsble for use in the present Rystem for
encoding and then decoding the compression filter
output are disclosed ln U,S. Patent
Number 4,396,906
entitled, "Method and Apparatus for
Digital Huff~an Encoding" by the precent inventor-
Reference is ~ade to Fig. 9 wherein ane~smple of n truncsted Huff~an cote is rhown for
purposes of illustratio~ only and not by way of
limitatlon. Tbere, a table of compressed signals,
~n~ rsnging from ~3 is shown together with u code
word for said ~ignal6,the length of the code word,
snd the relative probabilley of ocrurrence of aid
compressed ~ignals. The compressed Ai~nsls ~ n
which occur most frequently (here those between +3)
are assigned a code ~ord. The probhbility of ~ n
comprising a ~alue which ls assigned a code word is
high, ~ay, .9~. These compressed signals are
assigned different lenglth code words, with the most
frequenltly occ~rring compressed signal being
8ssigned the ~hortest code word. In the table, the
most frequently occurring compressed Bignal~ ~ n'~
is as6igned the shortest code word, and the least
frequently occurring compressed signal, ~ n --3, is
assigned the longeslt code word. All other
compressed signals outside the range of ~3 are-
identified as else in ithe table, and these are
assigned a code word which, as tescribed above ~ith
1~4~7fi
24
reference to Figs. 2 and 3, comprises a label for
the flctual compressed signal value a n which
subsequently is transferred to the ~luffman decoder
by way of recording, transmission over a
communications link, or the like. Obviously, the
system is not limited to use with the illustrated
truncated Huffman code. Additional compressed
signals, ~ n' may be assigned a code word, and
other code words may be employed.
RECONSTRUCTION FILTERING
Entropv Versus Reconstruction Filter Stability
.
For exact reconstruction of the digital music
signal supplied to the digital compression filter
30, the reconstruction filter 70 transfer function
]5 would have to be the inverse of the compression
filter 30 transfer function. (Two other necessary
conditions for exact reconstruction are that there
be no over- or under-flow errors in the filter
arithmetic and that there be no truncation of the
compression filter output word length )
As shown above, minimum entropy is obtained
when the zeros of the compression filter transfer
function are on the unit circle. The exact inverse
has poles on the unit circle in the same positions
as the compression filter zeros. Such a
reconstruction filter is unstable. Such
instab:ility is satisfactory until a bit error
occurs whereupon incorrect, and random, "initial
conditions" cause the reconstruction filter to
diverge to saturation. Two different systems are
described hereinbelow for use with arrangements
wherein the compression-reconstruction filter
combination is unstable which systems provide for
lX~4876
recovery from bit errors.
Briefly, one system includes the periodic
transfer of a plurality of actual digital slgnal
values, f , to the digital reconstruction filter 70
to periodically reinitialize the same. This, of
course, requires blocking of the signal and,
without very complex and highspeed logic, the loss
of data from the point of the error until the end
of the block.
Another system includes the use of check bits
and error checking means for production of a bit
error signal whenever an error is detected. The
error signal is used to momentarily move the poles
of the reconstruction filter 70 inwardly of the unit
circle, during which time the filter 70 recovers
from errors without the need to reinitialize the
filter with actual signal values f . By locating
the poles of the reconstruction filter inside the
unit circle, the filter is stable and incorrect
"initial conditions", due to errors, will damp out.
Under these conditions, the filter is stable and no
blocking is required for recovery from errors.
Stable filter combinations of this type also are
described in further detail hereinbelow.
Compression Filter Zeros Inside Unit Circle
Unsatisfactory
It here will be noted that poles of an exact
inverse are off the unit circle if the compression
zeros are not on the unit circle. However, such a
compression-reconstruction filter combination is
not practical for music data compression as will
become apparent from the following example. If the
compression filter transfer function contains two
real zeros near the 1,0 point, they must be aL a
distance from the unit circle that is less than
37~
26
`~ x 200/22000 (the distance around the unit circll
that corresponds to 200 ~Iz). A larger distance
means that the low frequency components will not be
as highly attenuated. Since 0.00909~ ~- 2-7, the
zero ~ould be
[ 1 ( 1 2-7) -1]
Therefore, if two zeros were used, there would be a
coefficient equal to 2-14, and 14 bits would be
added to the least significant end of the filter
arithmetic. With no truncation, approximately 14
bits would be added to the entropy and little data
compression would be possible.
Another compression-reconstruction filter
combination which is not suitable for use in the
present system, also includes arrangements wherein
both the zeros of the compression filter and the
poles of the reconstruction filter are off the unit
circle. With these arrangements there is no
arithmetic word length truncation, however, the
output of the compression filter is truncated to a
length that is one or two bits longer than the
analog l:o digital converter word length. Letting
the out:put quantization level equal qO1 the
quantizing noise power will have a variance of
~ 2 = qo (22)
Io 12
and the noise will be white. The reconstruction
distortion will be equal to the output noise due to
a noise generator at the reconstruction filter
input that has a variance that is given by equation
(22)
1224876
27
Since the input noise samples are white and
statistically independent, it can be shown that the
output noise varlance is
qO ~ gi (23)
or
~ = ql ~ gi ) (24)
where gi is the ith value (at the ith sampling
time) of the impulse response of the reconstruction
filter. In other words, the square root of the
sum-of-the-squares of the impulse response samples
is the standard deviation multiplier. This
multiplier has been calculated for different pole
positions by solving the appropriate difference
equation. From the calculations it has been
determined that noise power produced by such
truncation of the compression filter output is too
large, or is concentrated within such a small
portion of the signal bandwidth, so as to produce
undesirable sound in the music output.
Consequently, truncation of the compression filter
output words is unsatisfactory for music data
compression.
Reconstruction Filter Not an Exact Inverse of
Compression Filter
If there are no bit errors in the transfer of
the compression filter 30 output to the input of
the digital reconstruction filter, and no
truncation of the compression filter 30 output, the
output from the ~luffman decoder 66 is identical to
487~i
28
the output from the compression filter 30. Thus,
it will be understood that the transfer from the
input to the compression filter 30 to the output of
the reconstruction filter 70 is simply the product
of the transforms of the two filters 30 and 70.
Another data compression system which embodies the
present invention includes a compression-
reconstruction filter combination wherein the zeros
of the compression filter are at specific points on
the unit circle to reduce the entropy, and
corresponding poles of the reconstruction filter
are located inside the unit circle, adjacent said
zeros for stability. The frequency response and
stability of such compression-reconstruction filter
combinations are readily calculated. Consider, for
example, a compression-reconstruction filter
combination wherein the compression filter has two
zeros at (1,0) and the reconstruction filter has
two poles at (1-.00195, 0). The pole-zero pattern
of such a compression filter cascaded with a
reconstruction filter is shown in Fig. 10, and the
frequency response of the filter combination is
shown in Fig. 11. As seen in Fig. 11, the
combination provides a very flat high-pass filter
with a 18Hz cut-off. With this filter combination,
recovery from bit errors is within 20-30ms. It
here wil] be noted that the reconstruction filter
70 employed herein preferably comprises a digital
computer programmed for the desired reconstruction
filter operation.
_ord Length Considerations in the Reconstruction_ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
Filter
A stable reconstruction filter, operating
without truncation, would require a large
arithmetic word length. For example, the above-
12;~487~
29
describc(l-lcal-polc 18 1l~ filter woul(l rCq~lirC ~t
I e.lst 34 bit arithmetic (.0()l95 = 2 9), at: 1cast 9
hits per pole on the 1ecl.st ~significant end an(l I
bit on the most sign:ificant end per pole when the
analog to digital (A/D) word length is 14 bits. 4-
pole configurations would require even longer
arithmetic word length. Presently, computcrs
operating with such large word lengths are not
practical for consumer music data compression.
Fortunately, the reconstruction filter
arithmetic words can be truncated to practical
lengths with negligible system degradation.
Arithmetic word truncation noise is analyzed in
substantially the same manner as is the analysis of
quantizing. For this analysis, noise generators
with noise power q2/12 (one generator for each
coefficient) are added to the filter input and the
input-to-output standard deviation multiplier is
calculated. The value of q is the quantization
level of the truncated arithmetic word.
For an 18 Hz 2-real-pole reconstruction
filter, the multiplier is 3227. Then, the
arithmetic word length must be 12 bits longer than
the A/D word length or the arithmetic truncation
noise power will be larger than the A/D quantizing
noise power. Fourteen bit A/D conversion requires
26 or 27 bit reconstruction filter arithmetic. If
the compression filter has two real zeros at (1,0)
and two complex poles at 7KHz on the unit circle,
then a reconstruction filter having a complex pair
of poles at the 20Hz Butterworth position and a
complex pa-ir 7.33 ~Hz along the unit circle and
lOOHz in from the unit circle may be used. The
standard deviation multiplier of such a
reconstruction filter is 32, or 5 bits, and the
1~48~
frequency response of the compression-
reconstruction filter combination is substantially
the same as that shown in Fig. 11, except for a
narrow notch at 7~H~. With 24-bit arithmetic there
is virtually no degradation of the signal. Digital
computers with, say, 24 bit arithmetic for
reconstruction filtering are available at a
reasonable cost for use in the system of this
invention.
SYSTEM WITH ERROR DElECTION AND
MOVABLE RECONSTRUCTION FILTER POLES
In Figs. 12A and 12B, a modified form of this
invention is shown wherein check bits are generated
for recording and/or transmitting along with the
encoded digital compressed signals. At the
playback and/or receiver unit, any errors detected
using the check bits serve to generate an error
signal which is used to momentarily move the poles
of the digital reconstruction filter inwardly, or
further inwardly, of the unit circle in the z-plane
without changing the pole angle. For an ~nstable
reconstruction filter, momentary movement of the
poles inwardly of the unit circle results in a
stable filter combination which recovers from
playback and/or transmission errors without the
need for reinitialization of the filter. For a
stable reconstruction filter, momentary movement of
the poles inwardly of the unit circle provides for
accelerated recovery from error signals.
Reference first is made to Fig. 12A wherein
the digital recording and transmitting portion of a
modified form of data compression system which
includes the use of check bits is shown. The
system of Fig. 12A is similar to that of Fig. lA
76
and is shown to inc1ude an analog to digital
converter 20, digital compression filter 30,
Huffman encoder 40, switch 48, recorder 50, buffer
memory 52, modem 54 and timing and control unit 24,
all of which may be of the same type as shown in
Fig. lA and described above, lt will be noted that
an analog high frequency deempha sis filter 23A is
included in the input of the A/D converter which
filter serves the same function as digital filter
23 shown in Fig. lA.
In the form of invention shown in Fig. 12A, a
check bit generator 90 is shown included in the
connection of the Huffman encoded signal h( ~ n) to
the recorder 50 or modem 54, dependent upon the
position of switch 48. Check bits generated by
check bit generator 90 are added to the digital
stream of Huffman encoded signals for recording
and/or transmission along with said encoded digital
compressed signals. Numerous schemes for the
generation of check bits, and for error detection
using such check bits are well known and require no
detailed description. It here will be noted that
recorders and modems often include check bit
generator means for the generation of check bits to
be added to the data stream to be recorded, or
transmitted.
Recorded encoded digital signals, with check
bits, such as those recorded at recorder 50, are
reproduced using playback unit 60 shown in Fig.
12B, to which figure reference now is made.
Signals transmitted by modem 54 ~Fig. 12A) are
transmitted over line 56 to modem 82 (Fig. 12B).
Switch 64 connects the playback output, or modem
outut, to an error checking circuit 92 where the
signal stream is checked for bit errors. When an
4t~
32
error is detected, a bit error signal is generated
which slgl-a1 is transmitted over line 94 and
through switch 96 to the digital reconstruction
filter for momentarily shifting the poles of the
filter inwardly.
Check bit signals are stripped from the
signals from the playback unit 60 and/or modem 82
by the error checking means 92, and the Huffman
encoded digital compressed signal stream h( ~ n)
from the error checker is supplied to the Huffman
decoder 66, which decoder may be of the same type
as shown in Fig. lB and described above. From the
Huffman decoder, the digital compressed signals ~ n
are supplied through buffer memory 72 to the
digital reconstruction filter 70A. As with
reconstruction filter 70 of Fig. lB, the
reconstruction filter 70A operates with truncation
and converts the compressed signal input~n thereto
to equal length sample signals fn(out) which
closely match the input sample signals fn to the
compression filter 30 (Fig. 12A). A digital to
analog converter 74 converts the signal samples
fn(out) to analog form, f(t) out. An analog high
frequency emphasis filter 75A is included at the
output of the D/A converter, which filter serves
the same function as filter 75 in Fig. lB; i.e. to
restore the amplitude of the high frequency signals
which were deemphasized by filter 23A.
Poles Inside Unit Circle in Z-plane
As noted above, one embodiment of the present
invention includes the use of a compression-
reconstruction filter combination wherein the zeros
of the compression filter are at specific points on
the unit circle to reduce entropy, and the
reconstruction filter has corresponding poles
i2X4876
33
inside the unit circle, adjacent said zeros which
provide for stable operation. Recovery of the
reconstr llC tion filter from bit errors is
accelerated by momentarily moving the poles of the
reconstruction filter inwardly of the unit circle
in the Z-plane whenever an error signal is produced
by error checker 92.
Reference is made to Fig. 13 wherein zeros
and poles of the transfer function of a
compression-reconstruction filter combination are
shown. The compression filter zeros are shown on
the unit circle at zero degrees, and a pair of
reconstruction filter poles are shown adjacent the
zeros and normally at a distance of 0.00195 inside
the unit circle. It will be noted that this
combination of zeros and poles is the same as that
shown in Fig. lO, described above. Ilowever, in the
system illustrated in Fig. 13, the reconstruction
filter poles are momentarily moved inwardly upon
receipt of a bit error signal from the error
checker 92 over line 94. For purposes of
illustration, the poles are shown moved to a point
0.0625 inside the unit circle for rapid recovery
from the error. After a short period of time, say
50 ms, the poles of the reconstruction filter
return to normal position, that is, to a point
0.00195 inside the unit circle at zero degrees.
Difference equations for a reconstruction
filter having two poles at 0 and inside the unit
circle are:
Yn 2~ n + aYn-l = 2~ n + Yn_1 ~2-myn_l (25)
fn = Yn + afn-l = Yn ~~ fn-l -2 fn-l (26)
~2;~4~7~,
34
where: a = 1-2-m and
m = an integer.
~ reconstruction filter for implementing
equations (25) and (26) is shown in Fig. 14, to
which figure reference now is made. The
illustrated reconstruction filter 70A, comprises a
4 to 1 digital multiplexer 130 having one input 132
to which compressed signals ~ n are supplied from
the decoder 66. The output from the multiplexer
130 is supplied to an arithmetic and logic unit,
ALU, 134 where the required multiplication by
shifting, addition and subtraction take place under
control of timing and control unit 76A.
The output from ALU 134 is connected to the
input of a 1 to 2 digital demultiplexer 138. One
output of the demultiplexer 138 is connected to one
register of a pair of series connected shift
registers 140 and 142 over line 144. The other
demultiplexer output is connected over line 146 to
a single shift register 148. The value of Yn
determined by the ALU is loaded into register 140
while the prior value of Yn is shifted from
register 140 into register 142. The third register
148 is supplied with the sample value fn(out) as
calculated by the ALU 134.
Outputs from registers 140, 142, and 148 are
supplied as inputs to the ALU 134 through the
multiplexer 130. When used, the value stored in
register 148 comprises fn l(out). From equation
(25) it will be seen that the value Yn is
calculated using the ~ n and Yn 1 inputs to ALU 134
available at line 132 and from register 142. From
equation (26) it will be seen that the sample value
fn(out) is calculated using the Yn and fn l(out)
inputs from registers 140 and 148, respectively.
1224876
So long as n~ equals an integer less than
infinity, the reconstruction filter 70A operates
s t a b 1 y , a n d n e i t h e r i n t i a l i z a t i o n n o r
reinitialization of the filter is required. In the
5 absence of bit errors the filter is operated with a
relatively large value of m, say m=9, to place the
poles of the filter adjacent the unit circle at
.00195 from the unit circle. When an error is
detected by error checker 92, a smaller value of m
10 is used, say m = 4, thereby moving the poles of the
filter inwardly to a point .0625 from the unit
circle. The bit error signal from error checker 92
(Fig. 12B), which is supplied to the ALU 134
over line 94, controls the value of m used in the
15 implementation of equations (25) and (26) simply by
controlling the amount of shifting to perform the
indicated multiplications by the factor 2-m. When
an error is detected, contents of an ALU register
are not shifted as far to the right for som e
20 nominal length of time (say 50 ms) when performing
the multiplications by 2-m, thereby moving the
reconstruction filter poles inwardly away from the
unit circle to accelerate recovery from transients.
After this short time period, operation returns to
25 normal with the reconstruction filter poles again
adjacent the unit circle.
Poles Normally _ Unit Circle in Z-plane
As noted above, another embodiment of the
present invention involves use of a compression-
30 reconstruction filter combination wherein the zerosof the compression filter are at specific points on
the unit circle to reduce entropy and the
reconstruction filter has corresponding poles which
also are on the unit circle at the same locations
1~24876
36
as the zeros, during normal operation; that is
during operation in the absence of bit errors.
~lowever, when a bit error is sensed by error
checker 92, the poles of the reconstruction filter
70A are momentarily moved inwardly of the unit
circle for stable reconstruction filter operation,
and recovery from the error. This embodiment may
be implemented using the above-described receiving,
or playback, unit shown in Fig. 12B, and
reconstruction filter 70A shown in Fig. 14. Now,
however, the reconstruction filter 70A, in the
absence of transients, operates with poles on the
unit circle, as shown in Fig. 15. In Fig. 15, two
zeros of the compression filter 30 are shown
located on the unit circle in the Z-plane at zero
degrees, and, during operation in the absence of
bit errors, the two poles of the reconstruction
filter 70A are located at the same point on the
unit circle, at 2 point where m equals infinity.
In the presence of a bit error signal from
error checker 92, the reconstruction filter poles
are momentarily moved inwardly, of the unit circle,
at zero degrees. For purposes of illustration, the
value of m is shown changed to 4. Under these
conditions, the reconstruction filter quickly
recovers from the error without the need for
initialization, or reinitialization of the filter
by the transmission of actual signal values fn
thereto. It here will be noted, that at the start
of operation, the reconstruction filter poles are
momentarily moved inwardly of the unit circle to
avoid generation of a random ramp function at the
output therefrom.
Obviously, the invention is not limited to
inward movement of reconstruction filter poles to a
~ ~4~76
sing]e location in the presence of an error signal.
Several values of m msy be employed, with filter
operation being stepped through several different
pole locations during recovery from bit errors.
For example, values of m equal 2, 4, and 7 may be
used wherein operation first is switched to m
equals 2, then m equals 4, and finally to m equals
7, before stepping back to the original value of m,
either on, or inside, the unit circle in the Z-
plane.
SYSTEM WITH PERIODIC TRANSFER OF fn
Another embodiment of the present inventioninvolves use of a compression-reconstruction filter
combination wherein the zeros of the compression
filter are located at specific points on the unit
circle in the Z-plane to reduce entropy, and the
reconstruction filter has corresponding poles on
the unit circle at the same locations as the zeros,
which poles are fi~ed and are not moved inwardly.
As noted above, such a compression-reconstruction
filter combination is unstable, and, any transients
result in a random output from the reconstruction
filter. To minimize the effects of any such
transients, the reconstruction filter is
periodically reinitailized during operation by
transfer thereto of a plurality of actual signal
values, fn. Apparatus illustrated in Figs. lA and
lB may be used for this type of operation.
The signal stream which is transferred by
this operation is illustrated in Fig. 16, to which
figure reference now is made. In addition to
Huffman encoded difference signals h( ~ n+2)
h( ~ n+i)~ Huffman encoded signal values h(fn)~
h(fn+l), etc. are periodically transmitted, by
12~4876
38
periodic actuation of switch 35 to the broken ]ine
pOSitiOIl shown in ~ig. 1~ ith switch 35 in the
broken line posit-ion, a series of actual signaL
values, f are pericdicnlly supplied to the liuffman
encoder 40 for encoding and subsequent recording
and or transmission. The number of consecutive
signal values, f , sent equals the order of the
reconstruction filter.
In the signal stream shown in Fig. 16, two
consecutive signal values f are periodically
encoded, for use in periodically reinitializing a
second order reconstruction filter 70. The encoded
signals h(f ) etc. are shown to comprise a label
and the actual signal value f . The label used is
different from the "else" label used to identify
those signals outside a predetermined range of
compressed signal values ~ . The label portion of
the encoded signals h(f ) are designated Label # 2
in Fig. 16 to distinguish from the "else" label.
The required number of encoded signal values
h(f ) are periodically transferred, say, every 10
milliseconds, as shown in Fig. 16 to periodically
reinitialize the associated digital reconstruct:ion
filter 70. With this periodic reinitialization of
the reconstruction filter, there is no requirement
to operate the reconstruction filter with poles
inside the unit circle in the Z-plane since any
ramp function output produced by transient signals
is eliminated within 0 to 10 milliseconds time.
The invention having been described in detail
in accordance with requirements of the Patent
Statutes, various other changes and modifications
will suggest themselves to those skilled in this
art. For example, many of the illustrated
functions may be implemented using a digital
~Z~4~37~.
39
computer with suitable computer routines. It is
intended that this and other such changes and
modifications shall fall within the spirit and
scope of the invention defined in the appended
S claims.
