Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
~L~3~35~
DATA COMPRESSION METIIOD AND APPARATUS
BACKGROUND OF TI~E INVENTION
Systems which include means for converting
analog signals to digital sample signals, digital
compression filter means for reducing the entropy
of the sample signals, and lluffman encoding means
for encoding the output from the digital
compression filter in preparation for recording
and/or transmission to a remote location, together
with a playback or receiver means, Huffman decoding
rneans, digital reconstruction means which is the
exact or nearly exact inverse of the digital
compression filter means, and means for converting
the decoded and filtered digital signals back to
analog form are disclosed in an article by U.E.
Ruttimann and ll.V. Pipberger entitled, "Compression
of the ECG by Prediction or Interpolation and
Entropy Encoding", IEEE Transactions on Biomedical
_ g neering, 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 Electrocardiographic
Data", Pro. Com~ Cardiol. pp.439-445, 1976. The
present invention is directed to method and means
for further reducing the entropy of the digital
sample signal prior to recording and/or
transmission thereof.
SUMMARY OF TIIE INVENTION
The present invention is particularly adapted
for use in the compression of audio analog signals,
such as music signals. The analog music signals
~é
~ ;~3~:~S~
typically are converted to 14 to 16 bit sample
signals by analog to digital conversion which
provides for small quantization levels. For very
low level music signals such small quantization
levels are necessary, but with moderately high
level signals, the ear is incapable of resolving
the waveform down to such levels i.e. from one part
in approximately 16,000 to one part in approximately
65,000. That is, the quantization level where distortion
is noticeable to the listener is higher when the music level
is higher. ~xperiments have shown that, depending upon
the music level, the word length may be reduced to as
low as 8 bits with no, or extremely small amount of
noticeable distortion. It will be apparent that greater
signal compression is possible with shorter sample
signals.
The present invention is directed to an
arrangement for changing the "effective" word length
for different average music levels. With this invention,
the average music energy level is measured as by means
of an envelope detector, and the detector output is
sensed by one or more thresholds. In one embodiment of
the invention, one or more least significant bits (LSB)
of the sample signal are set to a predetermined value,
i.e. to 1 or 0, when the theshold(s~ is exceeded, as
for example by truncation, round-off, a table look-up
procedure, or the like, thereby effectively reducing
the entropy of sample signals when the music level
increases. These sample signals are supplied to a digital
compression filter to generate signals whose entropy is
less than the entropy of the input signals. When the
LSBs are set to 1 or O the output entropy is further
reduced. The compressed signals are supplied to
an encoder for truncated
~i 23~
Huffman encoding thereof. The digital output from
the encoder is recorded by digital recording means,
and/or transmitted to a remote receiving location.
~t a playback unit or receiving station the encoded
music signal is decoded by decoder means, and the
decoded signal is supplied to a digital
reconstruction filter which is~substantially an
inverse of the compression filter. Digital to
analog converter means converts the reconstruction
filter output to analog form.
In a modified form of this invention,
different Huffman codes may be employed for
encoding the compression filter output, the code
employed being dependent upon the threshold signal.
The code employed is selected for minimizing the
average bit rate of the Huffman encoded signal.
With this arrangement, a code identification word
is inserted in the signal stream from the encoder
to identify the code which is being employed at the
time. At playback, the code identification word is
used to select the proper operating mode of the
Huffman decoding means.
In another modified form of this invention
variable gain circuits are included in the
recording and playback systems for controlling
input signal levels to the digital compression
filter means and from the digital reconstruction
filter means in accordance with the threshold
signals. Either analog or digital gain control
circuitry may be emp]oyed. This form of the
invention also may be used with a plurality of
different Huffman codes for different encoding of
the sample signals dependent upon the threshold
signals.
In yet another modified form of this
~X3~3S~
invention, the setting of LSBs, or the setting of
variable gain circuits at the input to the digital
compression filter means, is controlled by means
responsive to the average music energy level at
the output from the digital compression filter.
With this arrangement, different Huffman codes are
employed for encoding the comp'ression filter output
dependent upon of the number of LSBs which are set
to zero, or the gain setting. Code identification
words are inserted in the lluffman encoded signal
stream for use at playback for correct decoding oE
the signal stream.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention will be better ùnderstood from
the following description when considered with the
accompanying drawings. In the drawings, wherein
like reference characters refer to the same parts
in the several views:
Fig. lA and lB together show a block diagram
of a data reduction system; a digital rccording
section being shown in Fig. lA and playback section
being shown in Fig. lB;
Fig. 2 shows the frequency response of high
frequency deemphasis and emphasis filters included
at the input and output, respectively, of the data
reduction system;
Fig. 3 shows a waveform and graphic
representations of signals appearing at various
locations in the data compression system shown in
Figs. lA and lB;
Fig. 4 is a graphic representation of encoded
difference signals showing the format employed for
encoding those difference signals which are outside
a predetermined signal range;
3;235~)
Fig, 5 is a block diagram showing details of the
mode control unit shown in Fig. lA;
Fig. 6 is a table illustrating different
truncated Huffman codes for use in the data reduction
system;
Fig. 7 is a graph for use ln showing the
relationship ~etween the probability that a digital
sample signal value will occur within a certain
quantization level and size of the quantization
level;
Fig. 8 is a table which illustrates the
setting of least signtficant ~its of sample signals
supplied to the digital compression filter;
Fig. 9 is a block diagram of a modified form
of data reduction system which is similar to that
shown in Figs. lA and lB but which employs a single
truncated Huffman code;
Fig. lOA and lOB together show a block diagram
of a modified form of data reduction system which
includes gain setting means instead of the least
significant bit setting means employed in the
embodiment of Figs. lA and lB; and
Fig. 11 is a block diagram of yet another
modified form of a digital data recording system
which embodies the present invention in which the
mode control unit is responsive to the output from
the digital compression filter means.
~23~ 7
RECORDING SYSTEM
Reference first is made to Fig. lA wherein a
recording unit of a combinat:ion recording-playback
system embodying the present invention is shown
comprising a high frequency deemphasis filter 20 to
which an analog input signal f(t), such as a music
signal, is supplied. The filter 20 deemphasizes
the high frequency portion of the analog signal to
reduce the signal entropy. The frequency response
of filter 20 together with the frequency response
of filter 20A included in the playback portion of
the system is shown in Fig. 2. There, it will be
seen that the relative gain of the filter 20
decreases beginning at approximately 0.4K~Iz, to
deemphasize high frequency components of the
analog signal. For simplicity, the analog output
from filter 20, as well as the analog input
thereto, is identified as f(t). At A of Fig. 3, an
analog signal f(t) is shown, comprising a music
signal which may range in frequency from
approximately 15 to 20,000Hz.
The filter 20 output is supplied to an analog
to digital converter (A/D converter) 22 for
conversion of the analog signal into digital form,
the nth sample from the A/D converter being
identified as fn. The form of the A/D converter
output, shown at C of Fig. 3, comprises samples
fn 1 through fn~i of equal length words. The A/D
converter 22 operates in a conventional manner at a
fixed sampling rate and fixed word length output.
As noted above, A/D conversion word length
typically is 14 to 16 bits and, for purposes of
illustration only, a 14 bit word length is shown in
Fig.3. Also, for purposes of description only, a
sampling rate of, say, 44Khz may be employed for
3~
conversion of the analog music signal.
The output from the high frequency deemphasis
filter 20 also is supplied to a mode control unit
24 over line 25 which, as described in detail
hereinbelow generates mode control signals at
output 26 therefrom for step control of several
elements of the data compression circuit. Mode
control signals at output 26 are dependent upon the
average energy level of the music signal input to
the unit.
The output from A/D converter 22 is supplied
to an entropy control circuit 28 which, in the
illustrated system comprises means for setting one
or more of the least significant bits of the sample
lS signal supplied thereto to a predetermined value of
1 or 0. A mode control signal from mode control
unit 24 is supplied to the entropy control circuit
28 for controlling the setting of the least
significant bits. For low level input signals,
sample signals pass unaltered through circuit 28.
At a first threshold level of the analog input
envelope, the least significant bit may be set to
0, for example; at a second threshold level, the
two least significant bits may be set to 0; etc.
The operation of setting least significant bits to
zero in response to mode control signals is
described in greater detail following a description
of the mode control unit 24. For simplicity, in
Fig. lA, the output from entropy control unit 28 is
identified as fn the same as the input thereto.
The output from the entropy setting unit 28
is supplied to a compression filter 30 which, for
present purposes, is shown to include an estimator
32 and subtracting means 34. The estimator 32
provides an estimate of fn~ here identified as ~n~
~3~3~
based upon actual samples occuring both before and
after the sample fn to be estimated. Estimators
for providing such estimated ~n 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 ~n by subtraction
of the estimated value from the actual value at
subtracting means 34, as follows:
10~ n = fn ~ fn (1)
In the graphic signal representation of the
compression filter output, shown at D in fig. 3,
diffcrence signals ~ n, ~ n+l~ ~ n~2~ ~n~i
are shown.
15It 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 fn Other
compression filtering may be used in which the
compression filter output ~ n is not a direct
function of the difference between the actual input
fn and an estimated value thereof, fn. The use of
the term "difference signal values ~n"~ therefore,
is intended to identify the output from any
suitable digital compression filter which may be
employed in the systems of the present invention.
The compressed signal values a n are supplied
to a digital encoder 40 for coding the same using a
truncated lluffman code. Truncated lluffman encoding
is, of course, well known. Briefly, the lluffman
encoding technique makes use of the fact that the
compression filter 30 has signal outputs, Q n~
~u
~3~3~
having different probabilities of occurrence, and
uses this fact to achieve a reduction in the total
number of bits in the encoded signal over the input
signal. A single code word is assigned to
infrequently occurring compressed signals, and
supplied as a label for the actual compressed
signal value~n. In Fig. lA, the encoder 40 output
is designated h( ~ n) and, at E in Fig. 3, the
a ues h(L~n), h(~ n+l)~ etc. represent encoded
ues of ~ n~ ~n+l,etc. The encoder 40 output
comprises code words for the most frequently
occurring values of ~ n~ together a combined code
word label and actual value of the compressed
signal ~n for less frequently occurring values of
~ n. For purposes of illustration only, if the
compressed signal ~ n is outside the range of -3 to
+3 then the actual signal ~ n together with a code
word label is produced at the encoder output.
In Fig. 4, wherein several encoded values are
shown, it will be seen that the encoded value for
~ n+2 comprises a label together with the actual
compressed signal Q n+2~ wherein ~n+2 comprises
an infrequently occurring compression signal value;
that is some value outside the range of +3.
The digital compression filter 30 has a
predetermined transfer function which is unaltered
in the operation of the system. For example only,
the compression filter may implement the following
transform:
~n = fn-~l - 2fn + fn-l (2)
~lowever, the probability that particular signals
~ n will be produced by the compression filter is
dependent upon the setting of entropy setting unit
28. Therefore, in accordance with another aspect
~3235~
of the present invention, the Huffman code
implemented by Huffman encoder 40 may be selected
for maximum reduction in the length of encoded
compressed signals produced thereby. In Fig. lA,
the digital encoder unit 40 is shown to include a
plurallty of individual encoders 40-0, 40-1... and
40-N. Switches 42 and 44 at the inputs and outputs
of the encoders select which encoder is employed
during system operation. The switches 42 and 44
are under control of the output from mode control
unit 24 for changing the Huffman code employed
simultaneously with changes in the number of least
significant bits which are set to a pre-determined
value by entropy setting unit 28.
The encoded compressed signal h( ~ n)~ from
the selected Huffman encoder is supplied to a code
identification generator and insertion circuit 50
for insertion of a code word into the encoded
signal stream to identify the operating state of
the system. The code identification generator and
insertion circuit 50 is controlled by the output
from the mode control unit 24 for the generation of
a code word that is unique for the energy level
band of the analog input signal f(t). In the
illustrated arrangement, the code word identifies
the Huffman code employed by digital encoder 40.
The code word may comprise a word which is not
contained in any of the }luffman codes, or it may be
a code word that is the same for each of the codes,
but which is followed by a binary number that
identifies the state. The code word is sent after
a switch in the output from the mode control unit
24 and periodically thereafter in case some of the
subsequently recorded bit stream is destroyed by
bit errors. For example, placing an identifier in
~LZ3235'~
the encoded bit stream every 50 or 100 samples wi].l
identify the code every several milliseconds but
cause negligible increase in the average bit
length. The encoded bit stream, with identifier
word, is identified by h(~ n) + ID in the drawings.
The encoded digital data stream,with
identifiers, is recorded and/or transmitted to a
remote receiver. For recording, the data stream
from code identification generator and insertion
circuit 50 is connected through a buffer memory 52
to a recorder unit 54. Recorded encoded digital
signals such as those recorded at recorder unit 54
are reproduced using the system shown in Fig. lB,
which system includes a playback unit 60.
Signals from the playback unit 60 are
supplied through a buffer memory 62 to a code
checker and stripper unit 64 which examines the bit
stream for the identifying code word, or words.
This process may be accomplished using one or more
AND logic gate network means connected to a shift
register through which the bit stream is passed;
one logic gate network for each identifying code
word. Alternatively, the code word may be
identified by use of a subroutine in a
microprocessor. In any case, the identifying code
word is stripped from the bit stream, and the
encoded compressed signals h(~ n) are supplied to a
digital decoder 66 for decoding the same. A
control signal is generated by the code checker and
stripper in response to the identifying code word,
which signal is connected over line 68 to the
decoder 66 for control of the decoding operation.
Since the compressed signal stream is encoded
using different codes, it will be apparent that the
decoder 66 must be operable in different decoding
~3~3~j ~
12
modes for decoding the coded signal stream supplied
thereto. The illustrated decoder is shown to
include a plurality of individual decoders 66-0,
66-l.... and 66-N. Switches 70 and 72 at the
5 inputs and outputs of the decoders select which
decoder is employed. The switches 70 and 72 are
under control of the control signal supplied
thereto over line 68 from the code checker and
stripper 64. The appropriate decoder unit is
10 switched into the circuit for decoding the encoded
difference signals supplied to decoder 66,
dependent upon which Huffman encoder 40-0 etc. is
employed during coding.
The compressed signal output ~ n from the
15 digital decoder 66 is supplied to a reconstruction,
or decompression, filter 74 for conversion of the
compressed signals to equal length sample signals
fn(out). The reconstruction filter 74 is an exact,
or substantially exact, inverse of the compression
20 f i 1 t e r 4 0 f o r e x a c t, o r n e a r 1 y e x a c t,
reconstruction of the input sample signals fn
supplied to the digital compression filter 30.
A digital to analog converter (D/A converter)
76 converts the signal samples fn(out) from the
25 digital reconstruction filter 74 to analog form.
An analog high frequency emphasis filter 20A,
having a frequency characteristic depicted in Fig.
2, emphasizes the high frequency components of the
analog signal from the D/A converter 76 whereby the
30 filter output closely matches the input which was
supplied to the high frequency deemphasis filter 20
included in the recording section shown in Fig. lA.
Ref erence no w is made to Fig. 5 of the
drawings wherein a mode control unit 2~l of the type
35 which may be included in the recording section of
3~'~
13
Fig. lA is sho wn to include an envelope detector 80
responsive to the analog music signal f(t) supplied
thereto over line 25 Erom the high frequency
deemphasis filter 20. It here will be noted that
the input signal to the envelope detector may be
obtained from the analog music signal at the input
to the high frequency deemphasis filter 20 rather
than from the filter output, if desired.
The envelope detector measures the average
music energy level, and the detector output is
connected to one or more threshold circuits for
sensing one or more thresholds of the detector
output. In Fig. 5, threshold circuits 82-1, 82-2
through 82-N are shown. The envelope detector
output identified by reference character 80A, is
depicted at B of Fig. 3, together with the input
levels TRl, TR2 and TRN at which the threshold
circuits 82-1, 82-2 and 82-N, respectively,
function to produce an output.
The threshold circuit outputs are supplied to
a logic unit 84 which9 in turn, produces a first
output when the analog input envelope equals or
exceeds TRl, a second output when the envelope
equals or exceeds TR2, etc. Obvîously, output line
26 from the logic unit 84 may comprise a plurality
of conductors over which individual control signals
dependent upon the level of the analog input
envelope are conducted to the various circuits to
be controlled. The logic may be implemented using a
logic gate network, computer subroutine, or the
like.
Reference now is made to Fig. 6 which shows a
table of truncated ~luffman codes which may be
employed in the operation of encoder 40 shown in
35 Fig. lA. In Fig. 6, encoding operations at four
r~
3~ ~
14
different levels of the average value of the analog
input signal are illustrated wherein the input
signal envelope, IE, is less than threshold TRl
(see B of Fig. 3.), i.e. IE~TRl; IE>TRl<TR2;
IE>TR2<TR3; and IE>TR3. The compressed signals,
~ n which occur most frequently are assigned a
code word. In the illustrated arrangement, these
signals comprise values between +3 and -3. The
most frequently occuring compressed signals are
assigned the shortest code word. All other signals
outside the range of_3 are identified as "else" in
the table, and these are assigned a code word
which, as decribed above with reference to Fig. 4,
comprise a label for the actual compressed signal
value Q n which subsequently is recorded.
An examination of the table of Fig. 6
reveals, for example, that the signals 2, -2, 3 and
-3 have the least probability of occurrence during
operation when IE>TR3, IE>TR2<TR3, IE>TRl<TR2, and
IE<TRl, respectively. Consequently, these signals
are assigned the longest code word which, in the
table is 00000001. From the table, it will be
apparent that a different code is employed for each
operating mode, which code minimizes the average
bit rate from the encoder. Obviously, the
invention is not limited to the use of the
illustrated codes, or to coding of the il]ustrated
range of compressed signal values.
A brief description of the operation of the
data compression system shown in Figs. lA and lB
and described above now will be provided. An
analog music signal f(t) (A of Fig. 3) is filtered
by high frequency deemphasis filter 20 to reduce
the level of the high frequency components of the
music signal. (See Fig.2 ) The output from the
2~ ~ 7
filter 20 is converted to a stream of sample
signals, fn by analog to digital converter 22,
which sample signals are supplied to an entropy
setting unit 28 comprising, for example, a register
into which the sample signals are shifted and which
includes means for setting one or more least
significant bits of the sample signal to a
predetermined value (either 0 or l) dependent upon
the output from mode control unit 24.
Mode control unit 24 is responsive to the
analog music signal and includes an envelope
detector and one or more threshold circuits for
production of control signals dependent upon the
energy level of the music signal. For a mode
control unit 24 which includes three threshold
circuits, a first mode control signal is produced
at the output 26 thereof when the average energy
level is less than threshold level TRl. Between
energy levels TRl and TR2 a second mode control
signal is produced; between energy levels TR2 and
TR3 a third mode control signal is produced and
above energy level TR3 a fourth mode control signal
is produced.
At low music energy levels, wherein the input
signal envelope, IE (B of Fig. 3) is less than the
first threshold level TRl 9 the sample signals pass
unaltered through the entropy setting unit 28 to
digital compression filter 30. In this operating
mode, the complete sample signal, fn is supplied to
filter 30 or compression filtering thereof. The
compressed signal output ~ n from the compression
filter 30 is encoded using a first truncated
}luffman code provided by ~luffman encoder 40-0 which
is selected under control of the mode control
signa] from mode control unit 24.
~A~ 2 ~ r ~
When the music signal envelope, IE, exceeds the
first threshold level TR1, a different mode control
signal is generated by mode control unlt 24 which operates
to:
1) set one or more of the least significant
bits of the sample signal to a predetermined
value at entropy setting unit 28;
2) select a different ~uf~man code, such as
provided by Huffman encoder 40-1, for encoding
the compression signals ~n from compression
filter 30; and
3) generate a new identifier word for
insertion in the encoded signal stream.
With increases in the ~usic energy level, above
predetermined threshold levels, the more least
significant bits are set to some predetermined value
thereby effectively (not actually) reducing the word
length of the ~ample signals from the analog to digital
converter 22. In Fig. 8, the settIng of one, two, and
three least significant bits of a word to zero dependent
upon which of three thresholds are exceeded is depicted
for purposes of illustration. Obviously, although
truncation is illustrated in Fig. 8 for restriction of
LSBs when a threshold is exceeded, ~t wlll be apparent
that other means including round-off may be employed,
if desired.
During playback, the encoded signal stream is
searched for the identifier by the code checker and
stripper 64 (Fig. ls]. From the code checker and
stripper 64, the encoded signal stream is supplied to
digital decoder 66 for decoding by one of the ~luffman
decoders 66-0 through 66-N. The decoder employed is
selected under control of the code identification signal
at the output line 68 from the code checker and stripper 64
for proper decoding of the encoded signal stream. From the
selected decoder, the digital compressed signals
~n are suppled to digttal reconstruction ~ilter
,i `
~3'~'7
17
74 having an output f (out~ which nearly matches
the input f to the digital compression filter 30.
The output from the digital reconstruction filter
74 is converted to analog form by digital to analog
converter 76, and the converter output is filtered
by high frequency emphasis filter 20A to restore
the analog signal to one nearly matching the analog
input signal to the high frequency deemphasis
filter 20 in the recording section.
It now will be shown that for a single
threshold the entropy at the output of the
compression filter 30 Is reduced by at least Pn
where the n least significant bits of the sample
signal input to the filter are set to 0 (or to 1)
when the threshold is on, and where P is the
probability that the threshold Is on. ~t here will
be understood that the average word length, L, from
a Huffman encoder, such as encoder 40 to which the
output from the compression filter 30 is supplied
is bounded by
H < L < H + 1 (3
where H is the entropy.
The reduction in entropy can be generalized
for M thresholds; the entropy being reduced by
M
~ i i (4
L=l
where P is the probability that the ith threshold
but not the (i ~ l~th threshold is on, and Ni is
the number of least significant bits (LSB) that are
set to 0 (or to 1). However, only the single
.. ..
~3~3.~ ~
1~
threshold proof is given hereinbelow since the
notation is greatly simplified.
The average entropy, Ha is
l~a = (l-P) Ho + PH1 (5)
where HO is the entropy at the output of
compression filter 30 when the threshold is off, P
is the probability that the threshold is on, and Hl
is the entropy thereat with bit restriction when
the threshold is on.
( ) o ( P) ~ Pio log P (6)
where Pio is the probability oE the ith value of
the filter output when the threshold is off. For
example, if the filter arithmetic is in 18 bits,
there are 218 possible values of filter output.
Now, let Hl be the entropy at the filter output
when the threshold is on but without 1.SB restriction~
PHl = P ~ Pil log Pil (7)
where Pil is the probability of the ith filter
output when the threshold is on but with no LSB
restriction.
The following inequality is well known.
If
Xi > and Yi >
and if
~32~
19
~ Xi = ~ Yi = 1
then
~ Xi log xi< ~ Xi log y~ (8)
thus
(l-P) Pio log p < ~ p)Pio log(l~ o+~il(g)
and
P ~ Pil log 1 < PPil log ~(10)
then
(l-P)Ho+PHl< ~[(l-p)pio+ppil] g(l-P)Pio +PPil
(1'1)
Note that Pio is the probability that the ith
output occurs given that the average sound energy is
less than a specified level and Pil is the
probability given that the energy is above the
level. Then the probability of the ith value of
the filter output when there is not ~hreshold
switching, Pi is
Pi = (l-P)Pio + PPil (12)
The entropy, without switching, at the filter
~3'~3~
output, H, is
~ = Pi log lr (13)
and
(l-P)Ho ~ PHl < H (14)
With a sample signal word length L,there will be
2L possible outputs from the A/D converter 22, and
every other possible output will end in a 1. If an
LSB is changed from 1 to 0 the number will be
changed to the next smallest number, and if all ~he
LSBs that are 1 are changed to 0, the number of
possible numbers will be 2L-l. The difference
between any two successive numbers will double and
so will the quantization level. This setting of
the n LSBs to 0 (or 1) wil] reduce the entropy by n
bits as can be seen in the following argumen~.
The entropy of a binary analog to digital
(A/D) converted N bit long sample is
~N
H(q) = ~ _ Pi log2 Pi (15)
i=l
where there are 2N 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
quantization9 which gives the ith value, is from
q(i-l) to qi. Then, as seen in Fig. 7, the signal
before A/D conversion will fall in the range of
q(i-l) to iq. In Fig. 7, the shaded area is the
probability that the signal, x(t) falls into the
ith quantization
Now, assum~ further that the size of the
quantiæation level, q, is small compared to the
standard deviation, ~ , of the signal. If the A/D
conve~ter word length is increased by one bit, the
quantization size is cut in half and, as shown
by dashed lines in Fig. 7, two quantization bins
are formed from the original. For q small, the
areas on either side of the dashed line will be
almost equal and the probability that xtt) 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 very
nearly is
2 [pi 2 2] [ 2 (log2 Pi ~ 1~] (16)
-Pi log2 Pi + Pi
The entropy of the (n-~l) bit long word is
2 2N
H (-2)= ~ -Pi log2 Pi + ~ Pi (17)
i=l i=l
= H(q) ~ 1
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
~L~3~3~ ~
22
quantization bin is centered about zero (the usual
case) is slightly more complex, however the result
is the same.
Thus
Hl = Hl - n (18)
then
(1 -P)Ho + PHl = Pn + Ha (19)
and~ using equation (11),
H> Pn + Ha (20)
or
H - Pn> Ha (21)
which shows that the entropy with least significant
bit restriction is less than the average entropy
without bit restriction.
From the above, it will be apparent that
entropy reduction may be obtained by a system
similar to that of Figs. lA and lB but without the
need for different Huffman encoding of the
compressed signals ~ n. Such a system which
operates with a single Huffman encoder/decoder and
without the need for a code identifier word in the
encoded compressed signal stream, is shown in Fig.
9 to which figure reference now is made. There,
the simplified system is shown comprising analog to
digital converter means 22 to which the analog
music ~ignal, f(t), is supplied for conversion to
digital form. A digital high frequency deemphasis
r~
23
filter 20-1 is included in the connection of the
sample signal output, fn~ from the analog to
digital converter to the input of entropy setting
unit 28. .As described above, entropy setting unit
5 28 is adapted for setting one or more least
significant bits of the sample signal to a
predetermined value when one or more threshold
values of the input signal en~elope exceed
predetermined levels. A mode control unit 24,
10 responsive to the analog input signal, controls the
setting of the least significant bit(s), which mode
control unit may be of the same construction as
shown in Fig. 5 and described above.
The sample signal output from the entropy
15 setting means 28 is compression filtered by
compression filter 30, truncated Huffman encoded by
encoder 40 and supplied through buffer memory 52 to
a modem 86 for transmission over communications
link 88 to a modem 90 at a receiving station.
20 There, the signal is fed through buffer memory 62
to Huffman decoder 66 for decoding the same. The
compressed signal output from the Huffman decoder
66 is filtered by reconstruction filter 74 having
an output which substantially corresponds to the
25 input to the digital compression filter 30. A high
frequency emphasis filter 20-2 boosts the high
frequency components of the output, fn(out) from
the reconstruction filter 74, and the output from
filter 20-2 is converted to digital form by digital
30 to analog converter 76.
With the arrangement of Fig. 9, input least
significant bits to the digital compression filter
are restricted in the manner described above with
reference to Fig. lA. When n least significant
35 bits are set to 0 (or to 1) the number of possible
~232~
24
compression ~ilter input values is reduced by a
factor of 2n numbers. Thus the 2L n values will
have a higher probability mass which reduces the
entropy over that of a probability distribution
that is not conditioned on the threshold state of
the music signal envelope. A single truncated
Huffman code is derived from this distribution for
use by ~uffman encoder 40, for a reduction in the
average word length from the Huffman encoder. A
bound for the entropy, ~It, is:
Ht < H - Pn + P log 1 + (l-P) log 1 ~22)
P l-P
This is a higher bound than equation 21 but close
thereto when P is near l. Experiment has shown
that the actual entropy with the single Huffman
code embodiment of Fig. 9 is significantly greater
than the multiple code embodi~ment of Figs. lA and
lB. However, the Fig. 9 e~bodiment is easier to
implement and is of value since it does provide for
a reduction in entropy.
Referring now to Fig. lOA, the recording
section is shown to include a high frequency
deemphasis filter 20 to which the analog music
signal is suppliedO The output from the high
frequency deemphasis filter 20 is supplied to a
variable gain amplifier 2~C, in which the amplifier
gain is set, in steps, under control of the output
from mode control unit 24 at line 26. The mode
control unit 24, which is responsive to the analog
music signal f(t) from the high frequency
deemphasis filter 20 may be of the same type as
shown in Fig. 5 and described above. At one or
more predetermined threshold levels of the music
signal envelope, the output from the mode control
unit 24 serves to change the gain of the variable
gain amplifier, the amplifier gain being reduced in
~L~3~
steps as increasingly higher threshold levels of
the analog music energy are reached.
The analog output signal from the variable
gain amplifier is converted to digital form by
analog to digital converter 22, and the digital
sample signal from A/D converter 22 is compression
filtered by compression filter 30. The compressed
signal output, ~n from the digital compression
filter 30 is encoded at Huffman encoder 40 which
implements a single truncated Huffman code. A
code word is inserted ~n the Huffman encoded signal
stream from encoder 40 by the code identification
generation and insertion circuit 50 which circuit,
as in other arrangments, is controlled by the
output from the mode control unit 24. Here, the
code word identifies the gain setting of variable
gain ampli~ier 28C. The Hu~fman encoded signal
stream, with the code word inserted therein at
changes in the gain setting, and periodically
thereafter, is supplied through hu~fer memory 52 to
the recorder 54 for recording thereof.
The playback section shown in Fig. lOB,
includes a playback unit 60, buffer memory 62/
Huffman decoder 66, digital reconstruction filter
74 and D/A converter 76 all of which are of the
same type as described above. In Fig. lOB, an
analog variable gain circuit 28D is included
in the output from the D/A converter 76 to
restore the strength of the signal thereat to a
level substantially corresponding to that at the
input to variable gain amplifier 28C in the
recording section when a decrease has been provided
during recording. The control signal at line 68
from the code checker and stripper circuit 64
controls the gain setting of variable gain
~L~3~
26
amplifier 28D in accordance with the code word
contained in the digital signal stream at the input
to the code checker and stripper circuit. The gain
is changed, in steps, with changes in the code
word. Obviously, digital gain control means for
controlling the gain of the output from digital
reconstruction filter means 74, before digital to
analog conversion by D/A converter 76, may be used
so long as corresponding inverse gain settings of
variable gain amplifier 28C are employed during
recording.
In yet another modified form of this
invention, shown in Fig. 12, a mode control unit
responsive to the output from the digital
compression filter 3~ is employed. There, the data
compression system is shown to include: a high
frequency deemphasis filter 20 to which the analog
music signal, f(t), is supplied; an analog to
digital converter 22 for con~erting the analog
signal output from the filter 20 to digital form;
an entropy setting unit 28 for use in setting one
or more least significant bits of the A~D converter
output to a predetermined value; a digital
compression filter 30 for compression of the
signal; a Huffman encoder 40 for truncated Muffman
encoding of the compressed signal; a code
identification generator and insertion circuit 50
for inserting an identifying code word in the
encoded compressed signal stream to identify the
setting of entropy control unit 28; and a buffer
memory 52 and recorder 54 for recording the signal
stream from the code identification generator and
insertion circuit 50; all of which elements may be
o the same type as shown in Fig. lA and described
above.
;~
35~
The music data compression system of Fig. 11
includes a mode control unit 24A which is
responsive to the output from the compression
filter 30 xather than to the input to the
compression filter. Outputs from the mode control
unit 24A are supplied to the entropy setting unit
28 for setting one or more least significant bits
of the sample signal to a predetermined value; to
the Huffman encoder 40 for selecting a Huffman
code; and to the I.D. generator and insertion
circuit 50 for generating an identification word
for insertion in the encoded signal stream.
In the Figure 11 arrangement, the mode control
unit 24A comprises an envelope detector and a set
of thresholds, in the manner shown ~n Fig. 5. The
envelope detector of mode control unlt 24~ is
implemented digitally using the following equation
y = ~ 2 ~ 2Yn_l (23
where Yn is the present value of the detector
output, Y 1 is the previous detector output, and
is a constant such that ~cl.
There is a set of numbers, Tl, T2, ...., T
that set the threshold levels. For example, if Y
is less than T3 the two LSBs would be set to zero
(or one). The quantity Yn is an estimate of the
average power of the ~n.
That a measure of the power of the
compression filter output, ~n' may be used to
control the mode will become apparent from the
following argument. It was shown earlier that if
the quantization level, q Cthe minimum distance
between the A/D converted numbers~, is doubled the
entropy is decreased by one bit~ A digital filter
3a with finite word length coefficients will change
the quantization of the output signal so that the
3~j~
28
ratio of the input quantization level to the output
quantization level is a constant. Therefore, if
the input quantization level is doubled so is the
quantization level of the 4~n and the entropy of
the ~n will decrease by one bit. As an example,
when the LSs is set to zero half of th~ original
numbers can no longer occur and the minimum
distance between num~ers (the quantization level)
at the filter 30 input and thus at the filter
output will double.
To a closed approximation music is a gaussian
waveform so that the fn are gaussian distributed
numbers. Since the compression filter is linear
the ~n are also gaussian. A computer evaluation
of the entropy of gaussian num~ers shows that to a
close approximation the entropy is
H ~ 1 ~ log(a ~ bits
q
where a is the standard deviation of the numbers
(the standard deviation is equal to the square root
of the power).
The quantization level of the ~n can be
raised or lowered by raising or lowering the number
of bits that are set to zero (:or to one) to adjust
a/q to near a designed ratio. The quantization of
the ~n is
- 2m
q - qO -
where qO i5 the quantization level of the ~nwhen no LSBs are set to zero ~or 1) by entropy
setting unit 28 and m is the number of LSBs that
are fixed to zero ~or one~. Since ~ is the
estimate of a and there is a one-to~one
relationship between a positIve num~er and its
square, Yn is applied to the thresholds.
t .
~L~3~3~
29
For example only, when the word length out o~
the A/D converter 22 is 14 ~its, the possible
numbers are all the integers between -8192 and
~8192. If the quantization level of the ~n is the
same as the quantization level of the fn~ qO = 1.
If it is desired to keep the entropy near 4 bits,
then log u 3 or ~ 8; then Yn/22m 64, or Yn
~ 22m x 64 = 22m~6q
The threshold numbers can be calculated using
this relationship as follows:
T = 22xO.5~6 = 128
T = 22x1.5+6 = 512
T = 22x2.5+6 = 2048
T3 = 22x3.5+6 = 8196
T = 22x4.5+6 = 32768
T = 22x5.5+6 ~ 131072
etc.
These values will keep the entropy wi~hin one bit
o~ 4.
The remainder of the operation of the system
is exactly the same as when the thresholds on the
input signal envelope detector set the numher of
bits that are set to zero Cor to 1), as shown in
Figs. lA and lB and described in detail above.
The entropy setting unit 28C of the variable
gain type (shown in Fig. lOA~ can also be operated
by mode control unit 24A instead of ~y mode control
unit 24, in which case the gain is cut in half each
time the next largest threshold is exceeded by ~n.
For example, a mode control 24A responsive to the
output from digital compression filter 30 may be
used in place of mode control unit 24 in the
arrangement shown in Fig. lOA, in which case the
system shown in Figs-~ lOA and 10~ would operate in
the same manner as described above except that the
output from a mode control unit 24A would be
~`~3~
employed for control of entropy setting unit 28C
and code I.D. generator and insertion circuit 50.
In summary, it will be seen that either the
quantization level, q, of the digital sample
signals from the A/D converter 22 is controlled
by entropy setting unit 28 in the arrangements
of Figs. lA, 9 and 11, or the standard deviation
~, of the compressed signal stream from the
digital compression filter means 30 is controlled
by entropy setting unit 28C in the Fig. lOA
arrangement. Either the quantization level, q, or
the standard deviation, ~, is controlled in a
particular system but not both factors. When
either q or ~ is changed, it is changed by a
factor of 2 , where x is a non-zero integer. For
example, each time q ls doubled, or ~ is halved,
the entropy of the signal stream from the digital
compression filter 30 ~s decreased b~ one bit
which, then, allows for a reduced bit rate at
the output from the variable word length encoder ~0.
Since only q or a is changed in a particular
system the ratio ~/q also IS changed by a factor 2x
with each change in energy level band as measured
by mode control unit 2~ in the Fi~. lA, 9 and lOA
arrangements or the mode control unit 24A in the
Fig. 11 arrangement.
The invention having been described in detail,
various other changes and modifications will
suggest themselves to those skilled in this art.
For example, the identifying code word in the
si~nal stream may be of a type which is suitable
for decoding hy the Huffman decoder 66, which
signal is used for switching to the required
Huffman decoder for implementing the required
decoding algorithm, and for setting of the gain of
the output from the reconstruction filter in the
,:
3~'~
31
gain setting embodiments. Also, the system may
include a digital computer, such as a
microcomputer, for use in implementing functions o
some of the elements of the system using suitable
computer routines. If desired, the envelope
detector and threshold functions of mode control
unit 24 may be digitally implemented following
analog to digital conversion of the analog input
signal. It is intended that the above and other
such changes and modifications shall fall within
the spirit and scope of the invention as defined in
the appended claims.
