JP2003198379A - Signal encoding device, signal encoding method, program, and recording medium - Google Patents

Abstract

(57) [Summary] [Problem] When compressing data for an audio signal processed by a computer, an embedded device, or the like or an image that has been subjected to image processing, a possible data value is generated for data having a biased probability of occurrence. And a signal encoding apparatus that reduces the total number of lists that hold. SOLUTION: This signal encoding device has a list storage means in which the amount of stored data is smaller than 2 to the Nth power, wherein packing data obtained by dividing input digital data by N bits and The data in the list stored in the storage means is compared, and a symbol is generated from the comparison result and the list is reconstructed. The generated symbol sequence is compressed to form a code word.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a signal coding device,
The present invention relates to a signal encoding method, a program, and a recording medium, and more particularly to a technique of compressing data for an audio signal processed by a computer, an embedded device, or the like, or an image subjected to image processing.

[0002]

2. Description of the Related Art In recent information-oriented society, the amount of communication information between information processing systems has been increasing due to the dramatic development and spread of computer technologies such as the Internet, multimedia, and distributed software. . For this reason, data compression technology is an important basic technology for improving communication efficiency between information processing systems and effectively using storage devices. That is, it becomes possible to reduce the load on the network by reducing the amount of communication data between the information processing systems connected to the network, and to pack more information in the same size.

As a typical example of the data compression technique, 18
There is Morse code (code word used for Morse code) that has been used since around the century, and is currently used not only in the Internet field such as modems and routers, but also in FAX, TV, radio, CD, satellite communication, video,
It is used in various fields such as telephones.

In such a compression technique, although it is a simple algorithm, BWT (Burrows) which can compress the data up to near the entropy (theoretical limit compression rate) of the compression limit.
-A compression processing system based on Wheeler Transform) has attracted attention in recent years. This BWT compression algorithm is 1994
Paper published by M. Burrows and DJ Wheeler in
Block-sorting Lossless Data Compression Algorithm
/ SRC Research Report 124, Systems Research Center-D
igital Equipment Corporation).
It is said that the compression processing system using the BWT is extremely effective not only for text data but also for reversible compression of full-color images having a large number of colors.

Since the BWT alone does not perform any compression, in practice another compression algorithm is used, for example:
The processing sequence is “BWT → Move to Front encoding → entropy compression”. This Move to Front (hereinafter abbreviated as MTF)
The encoding by is a coding method that considers that the previously appearing character has the highest probability of appearing this time among the already-existing characters, and a long string (run) in which the same character is repeated as in block sorting is used. It is an encoding for creating. In this MTF encoding method, "the same byte data is localized close to each other" obtained by block sorting.
It is known that particularly high effects can be expected for such highly redundant data.

This MTF encoding system operates as follows. It has a list that holds all possible input values, compares the input value with the values in the list, and generates a code with the position in the list having the same value as the symbol. Next, the value to be compared is reduced from the list and the input value is brought to the top of the list.

For example, five characters ('a', 'b', 'd', '
O ',' Y ') character sequences are explained. First, the list R = {'a', 'for these five characters
b ',' d ',' o ',' Y '} are created, and each one is a symbol
Give 0,1,2,3,4. Next, input character sequence {Ydbbaaaado
o} character by character, output the symbol of the corresponding list, and move that character to the beginning of the list, repeating until all the characters in the input sequence are output, and finally output sequence {4,3 , 3,0,3,0,0,0,2,4,0} is obtained.

[0008]

When using this MTF coding method, it is necessary to store as many input values as possible in the list as described above. Therefore, when the input value is a value represented by 10 bits, the number that must be stored in the list is 1024, and when it is 12 bits, it is 4096.
That is, as the number of bits forming the input value increases, a large amount of memory is used, and this MTF is increased.
The unit price and mounting area of the device or the LSI incorporating the encoding system swells exponentially.

On the other hand, the probability of occurrence of an input value represented by a bit width of 10 bits or more is biased and may not occur as a data value. If many such non-occurring data values occur, i.e., very few data values occur, maintaining a list for all possible data values is costly.

The present invention has been made in view of the above-mentioned circumstances, and for data whose occurrence probability is biased,
Provided are a signal coding device, a signal coding method, a program for executing the function of the signal coding device, and a computer-readable recording medium for recording the program, which reduce the total number of lists holding possible data values. The purpose is to

[0011]

In order to solve the above-mentioned problems, a signal coding apparatus according to claim 1 of the present invention comprises a bit packing means for dividing input digital data into N bits and data. List storing means for storing as a list without duplication, comparing means for comparing the packing data with data in the list, symbol generating means for generating a symbol from the comparison result, and the list for re-creating the list from the comparison result. A list reconstructing means for configuring the compression means, a compression means for compressing the generated symbol sequence to form a code word, and using a value smaller than the Nth power of 2 as the size of the list storage means. To do. According to a second aspect of the present invention, in the signal coding apparatus according to the first aspect, the list reconstructing means, if the comparing means determines that the packing data is not in the list, the list is rewritten. Suppose it is stored next to the end of
The packing data registered in the list is deleted, and the packing data is inserted at the head of the list to reconstruct the list. The claim 3 of the present invention is the claim 1.
Alternatively, in the signal coding apparatus according to claim 2, when the comparison unit determines that the packing data is in the list, the symbol generation unit sets the position in the list as a symbol, and the comparison unit. When it is determined that the packing data is not in the list, the number of data values in the list smaller than the packing data value is counted, and the number and the packing data value are added to form a symbol. And

According to a fourth aspect of the present invention, there is provided a signal encoding method having a list storage means in which the amount of stored data is smaller than the Nth power of 2, and the input digital data is stored in N
The packing data divided for each bit is compared with the data in the list stored in the list storage means, symbols are generated and the list is reconstructed from the comparison result, and the generated symbol string is compressed. And forming a code word. According to a fifth aspect of the present invention, in the signal coding method according to the fourth aspect, when the list is reconstructed, if it is determined that the packing data is not included in the list, the last next It is assumed that the packing data stored in the list is deleted and the packing data registered in the list is deleted and inserted into the head of the list. According to claim 6 of the present invention, in the signal coding method according to claim 4 or 5, when the packing data is judged to be in the list, the symbol is generated in the list. When it is determined that the packing data is not in the list, the number of data values in the list smaller than the packing data value is counted, and the number is added to the packing data value to determine the symbol. It is characterized by

The program according to claim 7 of the present invention is
A program for causing a computer to execute as the signal encoding device according to claim 1. A recording medium according to claim 8 of the present invention is a computer-readable recording medium recording the signal encoding program according to claim 7.

With the above configuration, M
When compressing data using the TF encoding method, when the probability of occurrence of this data is biased, the total number of lists holding possible data values can be reduced, thus saving memory usage. Can this M
It is possible to reduce the unit price and the mounting area of a device or LSI incorporating the TF encoding system.

[0015]

BEST MODE FOR CARRYING OUT THE INVENTION An embodiment of a signal coding apparatus according to the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a functional configuration of this embodiment. In FIG. 1, the signal coding apparatus includes a bit packing unit 10,
The comparison unit 20, the list storage unit 30, the symbol generation unit 40, the list reconstruction unit 50, and the compression unit 60 are included.

The bit packing means 10 divides the bit data to be compressed into N (4≤N≤32) bits. A symbol is generated by comparing the divided packing data with the data stored in the list storage means 30, and the generated symbol string is compressed by the compression means 60. Further, when the data length of the bit data to be compressed is not a multiple of N when dividing, the bit having the value 0 is padded in the insufficient portion to make it a multiple of N.

The list storage means 30 stores, in a list format, data values that appear as packing data obtained by dividing the bit data to be compressed. The total number of this list is set to be smaller than the Nth power of 2 which is the maximum data value that the packing data of N bits can take. The stored data is ordered by the list reconstructing means 50 so that the data that appeared last time among the existing data is considered to have the highest probability of appearing.

The comparison means 20 compares whether or not one packing data is stored in the list storage means 30, and if it is stored, outputs the found position (for example, in FIG. 2A). (See above). On the other hand, if not stored, the position next to the last data position stored in the list storage means 30 is output (for example,
(See the upper diagram of FIG. 2B).

The symbol generation means 40 compares the packing data with the data in the list storage means 30, and then generates a symbol as follows and temporarily stores it as a symbol string. (1) When the packing data is found in the list storage means 30, the position in the list is used as a symbol. (2) If the packing data cannot be found in the list storage means 30, the number of data values in the list storage means 30 smaller than the packing data is counted, and the value obtained by adding the counted value and the packing data is used as a symbol. .

The list reconstructing means 50 inserts the packing data into the head of the list storing means 30, and sequentially transfers the data from the head to the data immediately before the position found by the comparing means 20 one by one. By shifting the list, the order of the list is reconfigured so that the data that appeared last time among the existing data is considered to have the highest probability of appearing. For example, as shown in FIG. 2A, when the same data as the packing data is registered in the list storage unit 30 at the kth position, this “data k” is inserted into the list storage unit 30 at the first position, From "data 1" which was originally at the beginning, (k
The -1) th "data k-1" is sequentially moved backward one by one, and as a result, the data is reconstructed as shown in the lower diagram of FIG.

If the packing data is not registered in the list storage means 30, this packing data is inserted into the head of the list storage means 30 and the data from the head data to the last position is sequentially copied. The order of the list is reconfigured so that the data that appeared last time among the already-existing data are considered to have the highest probability of appearing by shifting them one by one. For example, as shown in FIG.
If the packing data is not registered in the list storage means 30, this packing data is inserted into the first of the list storage means 30, and the data from "data 1" which is the original first to the final data are sequentially. They are moved backward one by one, and as a result, they are reconstructed as shown in the lower diagram of FIG. Here, if the maximum number that can be stored in the list storage means 30 is exceeded by inserting the packing data, the final data is deleted and shifted.

The compression means 60 compresses and encodes the symbol sequence generated by the symbol generation means 40 and temporarily stored. As the compression method used at this time, known methods such as entropy coding, run length coding, arithmetic coding, and combinations thereof are used.

FIG. 3 is a flow chart for explaining the processing procedure of the signal coding apparatus of this embodiment. The bit data to be compressed is divided into N (4 ≦ N ≦ 32) bits (step S10). When the data length of the bit data to be compressed is not a multiple of N when dividing,
It is a multiple of N by padding the missing part with bits of value 0.

The packing data obtained by dividing the bit data to be compressed is taken out one by one (step S
12) If all the packing data has already been processed to generate the symbol string, the generated and temporarily stored symbol string is compressed and encoded (step S14,
S30). As the compression method used at this time, known methods such as entropy coding, run length coding, arithmetic coding, and combinations thereof are used.

In step S14, if there is packing data to be symbol-generated, the packing data is processed as follows. It is checked whether or not this packing data is stored in the list storage means 30 (step S16). If it has been registered, the found position is temporarily stored as a symbol (steps S18 and S20). On the other hand, if it is not registered, the number of data values in the list storage means 30 smaller than the packing data is counted, and the value obtained by adding the counted value and the packing data is temporarily stored as a symbol (step S18). , S22), and the registration position of the packing data is assumed to be the position next to the last data position stored in the list storage means 30 (step S24).

The data from the head data of the list storage means 30 to the data immediately before the registration position of the packing data is sequentially shifted backward one by one (step S26). here,
When moving backward, if the maximum number that can be stored in the list storage means 30 is exceeded, the final data is deleted. The packing data is inserted into the head of the list storage unit 30 (step S28), and the order of the list is reconfigured so that the data that appeared last time has the highest probability of appearing. The process returns to step S12 to process the next packing data to be compressed.

Further, the present invention is not limited to the above embodiment. A computer device in which each function configuring the above-described embodiment is programmed and written in advance in a recording medium such as a CD-ROM, and this CD-ROM is mounted with a medium driving device such as a CD-ROM drive at each site. Installed on the computer, stores the program in the memory or storage device, and stores it in the CPU of the computer device.
Needless to say, the object of the present invention can be achieved by reading and executing the program stored in the recording medium. In addition, the above program is a ROM (Read Onl
If it is stored in the y memory), the program is read from this ROM, and thus the medium driving device may not be provided.

In this case, the program itself read from the recording medium realizes the functions of the above-described embodiment, and the program and the recording medium recording the program also constitute the present invention.

As recording media, semiconductor media (eg, ROM, non-volatile memory card, etc.), optical media (eg, DVD, MO, MD, CD-R, etc.), magnetic media (eg, magnetic tape, flexible disk). Etc.).

Further, not only the functions of the above-described embodiment are realized by executing the loaded program, but the operating system or the like performs a part or all of the actual processing based on the instruction of the program, and It also includes the case where the functions of the above-described embodiments are realized by the processing.

When the above-mentioned program is stored in a storage device such as a magnetic disk of a server computer and distributed in a format such as download from a user's computer connected by a communication network such as the Internet, the server computer A storage device is also included in the recording medium of the present invention.

[0032]

As described above, according to the present invention, M
When compressing data using the TF encoding method, when the probability of occurrence of this data is biased, it is possible to reduce the total number of data values that can occur, thus saving memory usage. Can this MTF
It is possible to reduce the unit price and mounting area of a device or an LSI that incorporates the encoding method.

[Brief description of drawings]

FIG. 1 is a block diagram showing a functional configuration of this embodiment.

FIG. 2 is a diagram for explaining reconfiguration of list storage means.

FIG. 3 is a flowchart illustrating a processing procedure of this embodiment.

[Explanation of symbols]

10 ... Bit packing means, 20 ... Comparison means, 30 ...
List storage means, 40 ... Symbol generation means, 50 ... List reconstruction means, 60 ... Compression means.

   ─────────────────────────────────────────────────── ─── Continued front page    F-term (reference) 5C059 KK08 MA45 MC38 ME01 ME05                       ME11 PP14 SS06 SS11 UA02                       UA38                 5C078 AA04 BA33 BA43 CA27 DA01                       DA11                 5D045 DA20                 5J064 AA02 BA09 BC01 BC14 BC22                       BC23 BC28 BC29 BD03 BD04

Claims (8)

[Claims] 1. A bit packing means for dividing the input digital data into N bits, a list storage means for storing the data as a non-overlapping list, and a comparison for comparing the packing data with the data in the list. Means, symbol generation means for generating a symbol from the comparison result, list reconstruction means for reconstructing the list from the comparison result, and compression means for compressing the generated symbol sequence to form a code word. A signal encoding device, comprising: a value smaller than the Nth power of 2 as the size of the list storage means. 2. The signal coding apparatus according to claim 1, wherein said list reconstructing means, if said comparing means judges that said packing data is not included in said list, moves to the end of the list. A signal encoding apparatus, which is assumed to be stored, deletes packing data registered in the list and inserts the packing data at the head of the list to reconstruct the list. 3. The signal encoding device according to claim 1, wherein the symbol generating means selects a symbol in the list when the comparing means determines that the packing data is in the list. When the position of the symbol is used as a symbol and the comparison means determines that the packing data is not in the list, the number of data values in the list smaller than the packing data value is counted, and the number and the packing data value are counted. In addition, the signal encoding device is characterized by using a symbol. 4. A list storage means having a size of stored data smaller than the Nth power of 2 is provided, and packing data obtained by dividing input digital data into N bits and stored in said list storage means. A signal encoding method characterized by comparing data in a list, generating symbols from the comparison result and reconstructing the list, and compressing the generated symbol sequence to form a code word. 5. The signal coding method according to claim 4, wherein the reconstruction of the list is stored next to the end of the list when it is determined that the packing data is not in the list. It is assumed that the packing data registered in the list is deleted and the packing data is inserted at the head of the list. 6. The signal coding method according to claim 4 or 5, wherein when the packing data is determined to be in the list, the symbol is generated in the signal generation method. When it is determined that the packing data is not in the list, the number of data values in the list smaller than the packing data value is counted, and the number and the packing data value are added to form a symbol. And a signal encoding method. 7. The computer according to claim 1, 2 or 3
A program to be executed as the signal encoding device according to. 8. A computer-readable recording medium recording the signal encoding program according to claim 7.