JP2002297194A - Compressing method and restoring method of data, and program used for the same - Google Patents

Abstract

PROBLEM TO BE SOLVED: To enhance the compressibility by improving the procedure for encoding a predictive difference value. SOLUTION: Predictive difference values (A, B, C, etc.), for every sample included in a block of a prescribed length compressed by using an ADPCM method are divided into groups each consisting of a prescribed number of samples. A table(TB) wherein all combinations obtained by selecting arbitrary predictive difference values which are as many as the samples from all the predictive difference values included in the block of the prescribed length are made to correspond to mutually different representative values is generated and combinations of predictive difference values in the respective groups are represented by being replaced with the representative values made to correspond to the table.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a method for compressing data such as voice with high efficiency using an ADPCM method.

[0002]

2. Description of the Related Art ADPCM (Adaptive Differential Pulse Code Modulation) is used as a speech compression technique.
ulation). In this compression method, a waveform to be compressed is sampled at an appropriate frequency, a signal value for each sample (sample) is quantized with an appropriate number of bits, and a difference value between the samples is calculated. Based on the correlation between, predict the difference value for each sample from the difference value for the previous sample, quantize the predicted difference value with a quantization step width set according to the signal value,
Further, the quantized value is encoded. The ADPCM method is used for compressing data in a CD, a facsimile, and the like, because the information amount can be significantly reduced as compared with the PCM method in which the amplitude itself for each sample is quantized and encoded.

[0003]

When the prediction difference value is coded in the ADPCM method, the number of bits required at the time of coding may be wasted depending on the variation of the prediction difference value, and the compression ratio may be reduced. For example, when ten values are included in one data as prediction difference values, in order to encode those 10 prediction difference values for each sample, 4 bits must be allocated per sample. . In this case, although 16 prediction difference values can be specified at the maximum with 4 bits, any one of 10 prediction difference values is actually specified. Has occurred.

Therefore, the present invention realizes a data compression method capable of improving a compression ratio by improving a procedure for encoding a prediction difference value, a method of restoring the compressed data, and a method thereof. It is intended to provide a computer program for performing the above.

[0005]

The present invention solves the above-mentioned problems by a compression method, a decompression method, or a program described below.

According to the compression method of the present invention, a prediction difference value for each sample included in a block of a predetermined length compressed using the ADPCM method is grouped by a predetermined number of samples, and the prediction difference value is included in the block of the predetermined length. Generate a table in which all combinations obtained by selecting the same number of prediction difference values as the number of samples from all the prediction difference values are associated with different representative values. The combination is expressed by replacing it with the representative value associated on the table.

According to the present invention, since the prediction difference values of a plurality of samples are grouped into one group and coded, it occurs for each sample in the conventional method in which a fixed number of bits are allocated to each sample and coded. Wasted data is grouped into groups, and the waste generated in the entire block is relatively reduced, and the compression ratio is increased.

For example, in a case where one block contains 10 prediction difference values and two samples form one group, an arbitrary prediction difference value is calculated from all the prediction difference values as the number of samples. As for the number of combinations obtained by selecting the same number, 10 prediction difference values can be selected for each sample, so that 10 × 10, that is, a total of 100 combinations can be considered. That is, in order to express these combinations, 100 representative values may be prepared. 1
Since the minimum number of bits that can represent 0 in the decimal system is 7 (2 7 = 128), 100 representative values can be represented by 7 bits. In order to represent the combination of the prediction difference values of all the groups, it is necessary to have the number of bits corresponding to the product of the number of bits for each group and the number of groups, so if the total number of samples is m, For example, since the number of groups is 1/2, 3.5 m-bit data is created as a whole. On the other hand, when the prediction difference value is separately encoded for each sample, it is necessary to allocate more bits than 10 to one sample, that is, 4 bits for encoding. The number of samples is m × 4 bits, and 4 m bits are required. As can be seen from the results of this trial calculation, according to the present invention, it is possible to reduce the wasted capacity that occurs during encoding and increase the compression ratio.

In the compression method of the present invention, the ADPCM
The data compressed using the method may be divided into a plurality of blocks each having a predetermined length, and the generation of the table and the replacement with the representative value may be separately performed for each of the divided blocks. In this way, even when a large number of prediction difference values appear throughout the data, by dividing the data into a plurality of blocks, the number of prediction difference values included in each block (here, the prediction difference value ), And the compression ratio can be further increased.

[0010] While a predetermined number of prediction difference values are selected as valid prediction difference values from the prediction difference values included in the block of the predetermined length, the prediction difference values which are not made valid are selected as valid. The number of predicted difference values included in the block may be reduced by replacing the predicted difference value with the predicted difference value, and then the generation of the table and the replacement with the representative value may be performed. In this case, since the number (type) of prediction difference values included in one block can be reduced, the number of representative values to be prepared decreases, and the compression ratio increases. In particular, by performing such replacement when the number of prediction difference values slightly exceeds the boundary where the number of bits required to represent the representative value changes, the compression ratio can be effectively increased.

The number of occurrences may be counted for each value of the prediction difference value included in the block of the predetermined length, and the effective prediction difference value may be selected based on the number of occurrences. By examining the number of appearances in this way, for example, a prediction difference value that frequently appears is preferentially adopted as an effective value, and errors due to replacement of the prediction difference value can be made relatively inconspicuous. .

Further, a predetermined number of prediction difference values may be selected as effective prediction difference values in descending order of the number of appearances. As a result, since the prediction difference value having a low appearance frequency is replaced, the error due to the replacement is not conspicuous.

In order to express a value (10 × 10 = 100 in the above example) obtained by raising the number of prediction difference values included in the block of the predetermined length by the same number as the number of samples in a binary number, The required minimum number of bits is set to N (7 in this example).
), It is desirable to select all representative values from a range that can be represented by the N bits. As a result, the representative value can be represented by the minimum necessary number of bits, and the compression ratio can be improved. In this case, the representative value can be set to a continuous integer starting from 0.
A continuous integer need not always be selected as a representative value within the range of bits.

It is desirable that the representative value corresponding to the combination of the predicted difference values in each group be expressed with the minimum number of bits necessary to express all the representative values separately from each other. In this case, the portion corresponding to the representative value in the compressed data does not include redundant bits, so that unnecessary bits can be prevented from occurring and the compression rate can be prevented from lowering.

A program according to the present invention for realizing the above-described compression method includes a method for determining an arbitrary prediction difference value from all prediction difference values included in a block of a predetermined length compressed by using the ADPCM method. A process of generating a table in which all combinations obtained by selecting a number are respectively associated with different representative values, and a prediction difference value for each sample included in the block of the predetermined length is equal to the predetermined number of samples. Assuming that the numbers are grouped, a process of expressing the combination of the predicted difference values in each group by replacing them with the representative values associated on the table,
Is executed by a computer.

By reading and executing this program by a computer, the compression method of the present invention can be implemented.

Note that the program of the present invention can have a preferable mode of the above-described drawing method. That is, the compression program divides the data compressed using the ADPCM method into a plurality of blocks each having a predetermined length, and separately generates the table and replaces the table with the representative value for each of the divided blocks. It may be configured to do so. While a predetermined number of prediction difference values are selected as valid prediction difference values from the prediction difference values included in the block of the predetermined length, the prediction difference values that are not validated are replaced with the prediction prediction values that are validated. It may be configured to reduce the number of prediction difference values included in the block by replacing with a value, and then generate the table and replace with the representative value. It may be configured such that the number of appearances is counted for each value with respect to the prediction difference value included in the block of the predetermined length, and the valid prediction difference value is selected based on the number of occurrences. A configuration may be adopted in which a predetermined number of prediction difference values are selected as valid prediction difference values in descending order of the number of appearances. Assuming that the minimum number of bits necessary to express a value obtained by raising the number of prediction difference values included in the block of the predetermined length by the same number as the number of samples in a binary number is N, The representative value may be configured to be selected within a range that can be represented by the N bits. The representative value corresponding to the combination of the prediction difference values in each group may be configured to be represented by the minimum number of bits necessary to represent all the representative values separately from each other.

Further, according to the present invention, a representative value for each group included in data compressed by any one of the above methods is converted into a combination of prediction difference values for each group with reference to the table. A method of restoring data that specifies the predicted difference value of each sample according to the combination of the converted predicted difference values, and a representative value for each group included in the data compressed by any of the above methods, A configuration in which a computer is configured to execute a process of referring to the table to convert to a combination of prediction difference values for each group, and a process of specifying a prediction difference value of each sample according to the combination of the converted prediction difference values. Data recovery program.

According to these decompression methods or programs, data compressed by the above-described compression method can be correctly decompressed.

Each of the above-described programs of the present invention may be recorded on a storage medium and provided to the user, or may be provided on the wired or wireless transmission medium to the user.

[0021]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An example of a compression method according to the present invention will be described with reference to FIG. FIG. 1A shows a relationship between an example of a signal waveform to be compressed according to the present invention and a predicted difference value obtained from the signal waveform by using the ADPCM method. In the illustrated example, first, a signal waveform before compression is compressed by an ADPCM method in accordance with an appropriate sampling frequency to obtain a predicted difference value quantized for each sample. In FIG. 1A, the predicted difference value is indicated by an alphabet, but the actual predicted difference value is indicated by an arbitrary numerical value. However, each prediction difference value is not limited to a value corresponding to one digit in the decimal system, and may be two digits. Further, the prediction difference values A to J are not necessarily continuous integers, and may take appropriate discrete values.

After obtaining the prediction difference value quantized by the ADPCM method, the compressed data is divided into blocks every predetermined number of samples (m in the figure). The following processing is performed for each block. When the signal waveform is quantized by the ADPCM method, block division may be performed in parallel for every predetermined length.

First, the prediction difference value included in one block is calculated for each appropriate number of samples (here, every two samples).
Group into. Next, the prediction difference value is encoded for each group. FIG. 1B shows a main part of the encoded data thus obtained. As is clear from this figure, the compressed data includes a table and values L (1) to L (n) encoded for each group.
In addition, information specifying the number of samples forming one group may be included in the compressed data.

As shown in FIG. 1 (c), the table contains all the prediction difference values included in one block and selects all the prediction difference values by the same number as the number of samples 2. The combinations are respectively associated with different representative values.

For example, one block from A to J is stored in one block.
When it is assumed that 0 prediction difference values are included, the prediction difference values may overlap in each sample.
Exists. A table is generated by associating 100 combinations with 100 continuous representative values (note that integers) from 00 to 99.

With reference to the table thus obtained, encoding is performed by replacing a combination of prediction difference values for each group with a representative value. For example, since the combination of the predicted difference values of the first group in FIG. 1B is “AC”, the representative value corresponding to this is “02” with reference to the table. The determined representative value is encoded with a predetermined number of bits. The number of bits used here is set to the minimum number of bits necessary to represent all the representative values 00 to 99 in a distinguishable manner. In other words, the minimum number of bits necessary to express 00 to 99 separately is 7 bits (7 of 2).
Since the power is 128, the representative value of each group is encoded with 7 bits. "0000" for the first group
010 ". Hereinafter, similarly, the combination of the predicted difference values of each group is replaced with a representative value according to the table,
The replaced representative value is represented by a 7-bit binary number.

When a block including m samples is grouped by two samples, the number n of groups is m / 2, so that the number of bits of the code data portion (L (1) to L (n)) is 7 Xm / 2 results in 3.5 m bits. On the other hand, when each sample is separately coded, as described above, one block contains 10 prediction difference values, and to distinguish them, the prediction difference value is 4 bits for each sample. Therefore, the number of bits of the obtained data is four times (4m) the number of samples m. From this, it can be understood that the compression method of the present invention is highly efficient by comparing the data portions. Moreover, the superiority becomes more remarkable as the number m of samples increases. For example, if the number of samples is 256, according to the present invention, 7 × 25
While 6/2 = 896 bits of data, 4 × 256 = 1024 bits of data for each sample encoding. Therefore, it can be expected that the compression ratio can be increased according to the method of the present invention even when the amount of data required for encoding the table is considered.

In the method described above, all the combinations of the quantized prediction difference values included in one block can be represented by the representative value. However, some of the prediction difference values are treated as valid, and other prediction difference values are treated as valid. The number of representative values may be reduced by approximating the prediction difference value of the above with the effective prediction difference value.

Next, an embodiment of the present invention will be described in more detail with reference to FIGS. FIGS. 2A and 2B show the configuration of a control device for realizing the compression method and the decompression method of the present invention, respectively. As shown in FIG. 2A, in the compression device (encoding device) 1, the input signal X (n)
The difference D (n) between the data and the prediction value from the adaptive prediction unit 2 is guided to the adaptive quantization unit 3 and is quantized. The quantized prediction difference value is guided to the inverse adaptive quantization unit 5 and converted into a difference signal, and the difference signal output from the inverse adaptive quantization unit 5 is guided to the adaptive prediction unit 2 and Is used when quantizing the data of. Such a circuit configuration is the same as a known compression circuit using the ADPCM method. The feature of the present embodiment is that the prediction difference value quantized by the adaptive quantization unit 3 is guided to the code conversion unit 4, where the coding is performed by the above-described method. The encoded data L (n) and a table T generated for each block
B is output.

On the other hand, as shown in FIG. 2B, in the decompression device 6, the compressed data L (n) generated according to the present invention is
Is guided to the sign reverse conversion unit 7 together with the table TB. In the code inverse transform unit 7, a prediction difference value for each sample is obtained in a procedure reverse to the above-described encoding. After the conversion to the prediction difference value, the decoding unit 8 restores the difference signal from the prediction difference value, adds the difference signal to the prediction value from the adaptive prediction unit 9, and restores the original input signal. The circuit configuration after the decoding unit 8 is the same as a well-known restoration circuit using the ADPCM method.

The code conversion unit 4 and the code inverse conversion unit 7 shown in FIG. 2 may be configured as a hardware device combining logic circuits, or may be configured by combining a microprocessor and predetermined software. May be done.

FIG. 3 is a flowchart showing the flow of the encoding process executed by the code conversion section 4. As is apparent from this figure, when the data to be processed is given, the code conversion unit 4 first divides the data into blocks each having a predetermined number of samples (step S1). Subsequently, a block that has not been subjected to the encoding process is selected (step S2), and the number of appearances of the prediction difference value included in the block is counted for each value (step S3).

Next, a predetermined number of predictive difference values included in the block to be processed are selected as valid values in descending order of appearance number (step S4), and the predictive difference values not selected as valid values are determined. Replace with the closest valid value (step S5). For example, when the prediction difference values 4 and 7 are selected as valid values and the prediction difference values 5 and 6 are not selected as valid values, the prediction difference value 5 is approximated by the prediction difference value 4, and the prediction difference value 6 is Approximate by the difference value 7. Thereafter, a table for converting the prediction difference value selected as the effective value into the representative value is created (step S6). The table is as illustrated in FIG.

After the creation of the table, the combination of the predicted difference values is replaced with a representative value in accordance with the conversion table for each predetermined number of samples included in the block to be processed, and the replaced representative value is encoded (step). S7).
The method of selecting the representative value and the method of selecting the number of coded bits at this time are as described above.

Thereafter, it is determined whether or not all the predicted difference values included in the block to be processed have been processed (step S8), and if there are unprocessed predicted difference values, the process returns to step S7. If all the predicted difference values have been processed, it is determined whether all blocks have been processed (step S9), and if there are unprocessed blocks, the process returns to step S1. When all the blocks have been processed, the processing in FIG. 3 ends.

On the other hand, FIG. 4 is a flowchart showing the flow of the inverse encoding process executed by the inverse code converter 7 in FIG. 2B. As is apparent from this figure, when the compressed data to be decoded is given, the code inverse transform unit 7 selects an unprocessed block before decoding included in the data (step S11). , Read a table prepared in association with the block (step S
12). Subsequently, referring to the read table, the representative value encoded in the binary number is converted into a combination of the predicted difference values for each group (step S13). Next, the combination of the prediction difference values is divided into prediction difference values for each sample (step S14). Thereafter, it is determined whether or not data of all groups included in one block has been processed (step S15), and if there is an unprocessed group, the process returns to step S14.

When all groups have been processed, it is determined whether or not decoding of all blocks has been completed (step S1).
6) If there is an unprocessed block, the process returns to step S11. When all the blocks have been processed, the processing in FIG. 4 ends.

The above embodiment is merely an example of the present invention, and the present invention may be embodied in various forms. For example, the number of samples included in one group is not limited to two, and may be three or more. In the processing of FIG. 3, steps S3 to S5 may be omitted, and a table may be created corresponding to all combinations of prediction difference values included in one block. When the prediction difference value is divided into a valid value and a non-valid value, the number of valid values may be set to a maximum value in a range in which the number of bits required to represent a representative value is reduced by replacing the valid value. . The selection of the effective value of the prediction difference value does not necessarily have to be made based only on the number of appearances. For example, in a region where errors due to replacement are not conspicuous, even if the number of occurrences is large, some predicted difference values may be excluded from the effective values.

When the number (type) of prediction difference values included in one block exceeds a predetermined number, processing is as follows.
If the number of prediction difference values exceeds a predetermined number in the process of proceeding with encoding, an appropriate value among the prediction difference values selected so far is replaced with another prediction difference value and finally selected. Adjustment may be made so that the prediction difference values are almost equally allocated within the range from the minimum prediction difference value to the maximum prediction difference value.

[0040]

As described above, according to the compression method of the present invention, since the prediction difference values of a plurality of samples are grouped and coded, a fixed number of bits are assigned to each sample. The waste generated for each sample in the case of the conventional encoding method is now grouped into groups, the waste generated for the entire block is relatively reduced, and the compression ratio is increased. Further, according to the decompression method of the present invention, the data compressed by the compression method of the present invention can be suitably decompressed. According to the program of the present invention, the compression method or the decompression method of the present invention can be performed by using a computer. Can be implemented.

[Brief description of the drawings]

FIG. 1 is a diagram schematically showing a compression method according to the present invention.

FIG. 2 is a diagram showing an example of a configuration of a control device for realizing a compression method and a decompression method of the present invention.

FIG. 3 is a flowchart showing a procedure of an encoding process performed by a code conversion unit in FIG. 2;

FIG. 4 is a flowchart showing a procedure of an inverse encoding process performed by the inverse code converter of FIG. 2;

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Compressor 2 Adaptive prediction part 3 Adaptive quantization part 4 Code conversion part 5 Inverse adaptive quantization part 6 Decompression device 7 Code inverse transformation part 9 Adaptive prediction part

 ──────────────────────────────────────────────────続 き Continued on the front page F term (reference) 5D045 DA07 5J064 AA02 BA05 BB03 BB12 BC06 BC08 BD01

Claims (16)

[Claims] 1. A prediction difference value for each sample included in a block of a predetermined length compressed using the ADPCM method is grouped by a predetermined number of samples, and all prediction differences included in the block of the predetermined length are included. A table is generated in which all combinations obtained by selecting an arbitrary number of prediction difference values from the values by the same number as the number of samples are respectively associated with different representative values. A data compression method characterized in that the data is represented by being replaced with a representative value associated with. 2. The method according to claim 1, wherein the data compressed using the ADPCM method is divided into a plurality of blocks each having a predetermined length, and the table is generated and replaced with the representative value separately for each divided block. 2. The data compression method according to claim 1, wherein: 3. While selecting a predetermined number of prediction difference values as valid prediction difference values from prediction difference values included in the block of the predetermined length, the prediction difference values that are not validated are selected as valid prediction difference values. The number of predicted difference values included in the block is reduced by replacing the predicted difference value with the predicted difference value, and after that, the generation of the table and the replacement with the representative value are performed. 3. The data compression method according to 2. 4. The method according to claim 1, wherein the number of appearances is counted for each value of the prediction difference value included in the block of the predetermined length, and the effective prediction difference value is selected based on the number of occurrences. 3. The data compression method according to 3. 5. The data compression method according to claim 4, wherein a predetermined number of prediction difference values are selected as effective prediction difference values in descending order of the number of appearances. 6. The minimum number of bits required to represent a value obtained by raising the number of prediction difference values included in the block of the predetermined length by the same number as the number of samples to a binary number is represented by N. 6. The data compression method according to claim 1, wherein all representative values are selected from a range that can be represented by the N bits. 7. A representative value corresponding to a combination of predicted difference values in each group is represented by a minimum number of bits necessary for distinguishing all representative values from each other. 6. The data compression method according to any one of 6. 8. All combinations obtained by selecting a predetermined number of arbitrary prediction difference values from all prediction difference values included in a block of a predetermined length compressed using the ADPCM method are represented by different representatives. Processing for generating a table corresponding to each value, and assuming that prediction difference values for each sample included in the block of the predetermined length are grouped for each of the same number of samples as the predetermined number, A data compression program configured to cause a computer to execute a process of replacing a combination of values with a representative value associated on the table. 9. The data compressed using the ADPCM method is divided into a plurality of blocks each having a predetermined length, and the table is generated and replaced with the representative value separately for each of the divided blocks. 9. The structure according to claim 8, wherein
The program described in. 10. While selecting a predetermined number of prediction difference values as valid prediction difference values from prediction difference values included in the block of the predetermined length, the prediction difference values which are not validated are selected as valid prediction difference values. Characterized in that the number of prediction difference values included in the block is reduced by replacing the prediction difference value with the calculated prediction difference value, and then the generation of the table and the replacement with the representative value are performed. The program according to claim 8, which performs the program. 11. A method for counting the number of appearances for each value of a prediction difference value included in a block of the predetermined length, and selecting the valid prediction difference value based on the number of occurrences. The program according to claim 10, wherein: 12. The program according to claim 11, wherein a predetermined number of prediction difference values are selected as effective prediction difference values in descending order of the number of appearances. 13. The minimum number of bits necessary for expressing a value obtained by raising the number of prediction difference values included in the block of the predetermined length by the same number as the number of samples in a binary number is represented by N. The program according to any one of claims 8 to 12, wherein all the representative values are selected within a range that can be represented by the N bits. 14. A method for representing a representative value corresponding to a combination of prediction difference values in each group with a minimum number of bits necessary to represent all the representative values in a distinguishable manner. The program according to any one of claims 8 to 13. 15. A representative value for each group included in data compressed by the method according to any one of claims 1 to 7,
A data restoration method comprising: converting a prediction difference value for each group into a combination of prediction difference values for each group with reference to the table; and specifying a prediction difference value for each sample according to the converted combination of prediction difference values. 16. A method for converting a representative value for each group included in data compressed by the method according to any one of claims 8 to 14 into a combination of prediction difference values for each group with reference to the table. A data restoration program configured to cause a computer to execute a process and a process of specifying a predicted difference value of each sample according to a combination of the converted predicted difference values.