Apparatus and method for real time data compressor

• US 4,926,482 A
• Filed: 06/26/1987
• Issued: 05/15/1990
• Est. Priority Date: 06/26/1987
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Morley, Kenneth S., Frost, Richard L., Pulsipher, Dennis C.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Merecki, John A.
• Application Number:
  US07/066,587
• Time in Patent Office: 1,054 Days
• Field of Search: 381/29-32, 381/36-41, 381/47, 364/513.5, 375/122, 375/25-26, 375/34
• US Class Current: 704/229
• CPC Class Codes: H03M 7/3053 Block-companding PCM systems

Abstract

High speed computing apparatus for performing real time data compression of analog voice data or digital data to be transmitted over a data link. The incoming data stream is divided into blocks of digital data and the blocks are subdivided into digital samples or elements to be compressed. Each sample is analyzed individually to determine its estimated variance and the marginal return to be gained by alloting the sample one or more of the bits to be employed to define the block of digital data. The bits are assigned samples having the highest estimated variance factor so that an optimum allocation of bits to individual samples is achieved with variable ratio data compression. The allocated bits are employed to encode the samples during real time data compression and transmission.

Claims

1. Apparatus for performing real time data compression of blocks of digital or analog data of the type having an input data stream converted to a desired digital format data stream of time domain estimated variance samples comprising:

high speed computing means coupled to said digital data stream for allocating a digital bit to individual estimated variance samples and calculating marginal return values for said samples

comparator means,

high speed storage means coupled to said high speed computing means and to said comparator means,

look-up table means coupled to said computing means for storing predetermined mean-squared error constants employed for computing the highest marginal return for said digital data samples

address generation means coupled to said high speed storage means and to said look-up table means, and

control means coupled to said computing means, said comparator means and said address generation means for presenting a sequence of commands to provide a real time stream of blocks of compressed data samples from said computing means, said blocks of compressed data each having

a predetermined number of bits to be allocated for each block of compressed data,

each said block of compressed data having an optimum allocation of bits to the highest marginal return samples, and

a minimum bit error rate and the highest average marginal return for each block of compressed data.

2. Apparatus for performing real time data compression as set forth in claim 1 wherein said high speed computing means is programmed by said control means to store said estimated variance for each digital data samples of said input data stream as input data into said high speed storage means.

3. Apparatus for performing real time data compression as set forth in claim 2 wherein said high speed computing means is programmed by said control means to sense and compress a predetermined number of said samples of digital data representative of which define a block of incoming data.

4. Apparatus for performing real time data compression as set forth in claim 3 wherein said

digital data samples are individually examined by said high speed computing means and compressed at variable compression ratios to provide a predetermined data compression ratio for said block of compressed data by allocation of different numbers of bits to different samples.

5. Apparatus for performing real time data compression as set forth in claim 3 wherein said high speed computing means is programmed to calculate estimated variances of said samples of data to be compressed and to arrange said estimated variance samples of a block of data in a diminishing order of magnitudes.

6. Apparatus for performing real time data compression as set forth in claim 5 wherein said high speed computing means is programmed to calculate marginal return values for each of said samples of a block of data and to determine the sample having the highest marginal return by multiplying said estimated variance by a constant stored in said look-up table means.

7. Apparatus for performing real time data compression as set forth in claim 6 wherein said high speed computing means is programmed to assign one bit of said bits to be allocated to the sample having the highest marginal return and to recalculate the marginal return of the sample then having the highest marginal return.

8. Apparatus for performing real time data compression as set forth in claim 7 wherein said high speed computing means is programmed to assign one bit at a time of said bits to be allocated to the sample having the highest marginal return value until all bits to be allocated are assigned to said samples to provide an optimum allocation of bits to the highest marginal return values.

9. Apparatus for performing real time data compression as set forth in claim 8 wherein said high speed computing means is programmed to encode each of said samples employing the number of bits assigned to each sample whereby samples are compressed at different compression ratios in the same block of samples.

10. Apparatus for performing real time data compression as set forth in claim 1 which further includes a plurality of division look up tables containing estimated inverse values coupled to said computing means for performing high speed division by multiplication.

11. Apparatus for performing real time data compression as set forth in claim 1 which further includes a bisection generation means coupled to said address generation means and to said comparator for performing bisection pointer address calculations.

12. A method of performing real time data compression of an input stream of data comprising the steps of:

dividing said input stream of data into blocks of digital data,

dividing said blocks of digital data into samples of digital elements,

calculating an estimated variance for each digital element sample,

arranging said samples of digital data into a diminishing order by magnitude of said estimated variances,

examining each sample to determine the sample having the highest marginal return,

reducing the marginal return of the sample having the highest marginal return by allocating one bit of a predetermined number of bits to be allocated to define said block of digital data,

moving a pointer representative of the number of bits allocated to the particular sample which had the highest marginal return to the next lowest sample in the order of samples,

repeating the steps of determining the sample having the highest marginal return and reducing the marginal return of the sample having the highest marginal returns by allocating one bit and moving a pointer representative of the number of bits allocated to the particular sample until all bits to be allocated are allocated, and

encoding each said sample with the number of bits so allocated to each individual sample in real time.

13. A method of performing real time data compression as set forth in claim 12 which further includes the steps of:

predetermining in advance the total number of bits to be allocated to define a block of digital data of greater bits thus defining the compression ratio of data compression.

14. A method of performing real time data compression as set forth in claim 13 which further includes the step of determining side information defining the spectral energy content characteristics of said block of digital data and wherein the step of encoding each sample further includes encoding each sample employing said side information.

15. A method of performing real time data compression of an input stream of data comprising the steps of:

dividing said input stream of data into blocks of digital data,

dividing said blocks of digital data into samples of digital elements,

examining each sample of digital data to determine the energy content of each sample,

sorting said samples in a diminishing order of energy content,

determining the cumulative gain related to the energy content applicable to defining any one sample with one or more bits in order to digitally define said sample,

determining the maximum number of bits to be employed to define any one sample,

positioning a reference marker and other markers which have a fixed ratio relative thereto to the sorted samples,

assigning bits to samples between markers in said sorted order to provide an optimum allocation of bits,

checking to determine if the total number of bits allotted to define a block of digital data have been allocated, and

encoding each said sample of elements of said block of digital data employing an optimum allocation of digital bits.