JP6885466B2 - Coding device, decoding device, coding method, decoding method, coding program, decoding program - Google Patents

Description

The present invention relates to a technique for encoding and decoding a sample sequence consisting of integer values such as a sample sequence of a voice or acoustic time series digital signal.

As a technique for coding a sample series for the purpose of compression, a finite precision value (hereinafter referred to as an integer value) obtained by quantizing the sample value is reversibly coded to describe the sample series. There is a technology to reduce the bit length used. In this technique, the code of which length is assigned to which integer value is directly related to the compression performance. This fact is an exception even in engineering applications of sample series coding and decoding, such as image coding that encodes and decodes a sample sequence of an image signal and acoustic coding that encodes and decodes a sample sequence of an acoustic signal. Absent.

Generally, in variable-length lossless coding, there are restrictions on the configuration of codes assigned to integer values due to restrictions on decodability. Specifically, if a short code is assigned to a certain integer value, a long code must be assigned to another integer value in order to make it a decodable code. Therefore, in order to improve the compression performance, it is necessary to make the code configuration (assignment of the code to each integer value) suitable for the distribution of the values in the series of integer values. Specifically, by assigning a short code to an integer value with a high probability of occurrence and a long code to an integer value with a low probability of appearance, the expected value of the bit length after compression of the series of integer values can be obtained. It can be made smaller.

The Golomb-Rice code has been used as one of the simplest variable-length codes in the above-mentioned lossless coding. The Golomb-Rice code is the minimum expected bit length (minimum bit) when a series of integer values belongs to the Laplace distribution, that is, when the probability of occurrence of integer values is exponentially lower than the size of the value. It is known to achieve (long).

This Golomb-Rice code is widely used because it has a very simple structure. The Golomb-Rice code is obtained by dividing each sample value included in, for example, a series of integer values obtained by AD-converting an acoustic signal into PCM or a series obtained by Fourier transforming the series into a frequency spectrum, etc. It is used when encoding a series of absolute values of integer values obtained. Alternatively, the Golomb-Rice code is used to encode a series consisting of non-negative integer values in which each sample value x of the above integer value series is replaced with x'obtained by the following equation (1).

Therefore, the case of encoding / decoding a non-negative integer value will be described below. However, due to the above fact that the entire integer value can be converted to a non-negative integer value one-to-one by Eq. (1) or the like, in the first stage of the coding process. The entire integer value can be converted to a non-negative integer value by the equation (1) or the like, or the non-negative integer value can be converted to the entire integer value by the inverse conversion of the equation (1) in the subsequent stage of the decoding process. It can also be applied to the coding / decoding of.

とし、以下の片側ラプラス分布に従う非負整数値の系列に対して近似的に最適な期待ビット長を与えるように符号化できるものである。Golomb-Rice coding sets the bit length B (x) of the code for the input x of a non-negative integer value as shown in the table of FIG. 1 by appropriately selecting the value of the Rice parameter (rice parameter) r.

Then, it can be coded so as to give an approximately optimal expected bit length to a series of non-negative integer values that follow the following one-sided Laplace distribution.

However, the Rice parameter r is a non-negative integer value. In other words, if the Rice parameter r is a small non-negative integer value, a series with a large value bias can be encoded with a small average number of bits, and if r is a large non-negative integer value, a series with a small value bias is small. It can be encoded with an average number of bits.

However, since Golomb-Rice coding cannot make the Rice parameter r a negative value, the bias of the value of the series is larger than that of the distribution p (x, 1), for example, a series of values according to the distribution p (x, 0.1). As the size increases, the efficiency of compression decreases no matter how the Rice parameter r is set.

For example, when an acoustic signal is AD-converted to PCM, the range of numerical values that can be expressed is set so that it can be recorded up to a large volume, so the values included in many signal sequences are the range of numerical values that can be expressed. There is a tendency for the absolute value of to be biased toward smaller values. In particular, since the audio signal has a time interval in which there is no utterance, it is biased to a very small value of only zero value or background noise. Further, the sequence of integer values obtained by dividing each value included in the sequence of such signals by the quantization value is biased to a smaller value including a zero value than the original sequence by quantization.

There is a technique of Non-Patent Document 1 as a prior art for encoding a series of integer values biased to zero values. In the technique of Non-Patent Document 1, the zero value included in the input integer value series is included in the input integer value series by encoding the number of consecutive zero values with a predetermined fixed number of bits. A value other than the zero value is a Golomb-Rice encoding of a value (value-1) obtained by subtracting 1 from the value.

Further, as a prior art for encoding a series of integer values biased toward a small value including a zero value, there is a technique of Non-Patent Document 2. In the technique of Non-Patent Document 2, a set of two integer values and one integer value are linked in advance so as to be bijective, and the set of two integer values included in the sequence of integer values is combined with one integer value. It is converted to and the converted sequence of integer values is Golomb-Rice encoded.

H. S. Malvar, “Adaptive Run-Length / Golomb-Rice Encoding of Quantized Generalized Gaussian Sources with Unknown Statistics”, in Proc. Data Compression Conference (DCC) 06, IEEE Computer Society, pp.23-32, Mar. 2006. Masayuki Takamura, Yoshiyuki Yashima, "Efficient Coding of Gaussian Sources Based on Distribution Maps", Journal of the Institute of Image Information and Television Engineers, Vol.61, No.9, pp.1357-1362, 2007.

According to the technique of Non-Patent Document 1, zero values can be encoded with a small average number of bits. However, in the technique of Non-Patent Document 1, almost the same coding as Golomb-Rice coding is performed except for the zero value. Therefore, in the technique of Non-Patent Document 1, small non-zero values are distributed p (x, 1). ), There is a problem that the compression performance deteriorates.

Further, the technique of Non-Patent Document 1 is not a coding method corresponding to a mathematically expressed distribution. Therefore, in the technique of Non-Patent Document 1, once the distribution of values in a series of integer values is known, which one should be selected and encoded as the number of bits used to express the continuous number of zero values is a small average. There is also the problem of not knowing whether it can be encoded by the number of bits.

On the other hand, according to the technique of Non-Patent Document 2, a series of integer values whose values are biased from the distribution p (x, 1) can be encoded with a small average number of bits. However, the technique of Non-Patent Document 2 cannot make the average number of bits for one integer value smaller than 0.5 bits, and for a series of integer values with a large bias such that the theoretically optimum average number of bits is less than 0.5 bits. Therefore, there is a problem that the compression performance is lowered.

Therefore, the present invention provides a coding / decoding technique capable of coding a series of integer values including a small value other than a zero value and whose distribution is largely biased to a small value with a small average number of bits. The purpose is to do.

One aspect of the present invention is for a series of input non-negative integer values x_n, n ∈ {1, 2, ..., N} (hereinafter referred to as "integer series"), where K is an integer of 2 or more. A 1-bit code (hereinafter, "code A") as a code corresponding to a series of L numbers, which is any predetermined number of ^{2 to 2 K-1} integer values included in the integer series. ) Is obtained, and K × x_n bits or K × x_n bits or a code corresponding to a set consisting of 0 to L-1 consecutive integer values 0 and one non-zero integer value x_n included in the integer series. Includes an integer coding unit that obtains a K × x_n + 1 bit code (hereinafter referred to as “code B”).

In one aspect of the present invention, with respect to the input code string, K is an integer of 2 or more, and a 1-bit code (hereinafter referred to as “code A”) included in the input code string is used as an integer value of 0-2. A sequence of L pieces, which is any number of 2 ^K-1 pieces, is obtained from the pieces, and a code of K × x_n bits or K × x_n + 1 bits included in the input code string (hereinafter referred to as , "Sign B"), and by obtaining a set of 0 to L-1 consecutive integer values 0 and 1 non-zero integer value x_n, the integer values x_n, n ∈ {1, 2 Includes an integer decoder that obtains the sequence by, ..., N}.

One aspect of the present invention is a data structure of a code string representing a series of non-negative integer values x_n, n ∈ {1, 2, ..., N} (hereinafter referred to as "integer series"). The code string is used in a coding device that obtains the code string from the integer sequence and / and a decoding device that obtains the integer series from the code string, where K is an integer of 2 or more. A 1-bit code (hereinafter, "code A") that is a code corresponding to a series of L numbers, which is any predetermined number of ^{2 to 2 K-1} integer values included in the integer series. ), And a set of 0 to L-1 consecutive integer values 0 and one non-zero integer value x_n included in the integer series, K × x_n bits or K × x_n bits Includes a K × x_n + 1-bit code (hereinafter referred to as “code B”).

According to the present invention, a series of integer values that are largely biased toward small values, including small values that are not zero, or a series of integer values that are biased to the extent that the technology of Non-Patent Document 2 cannot handle them. Even if there is, it can be encoded with a small average number of bits. Moreover, such a code can be decoded.

It is a figure which shows the Golomb-Rice code for the input x of a non-negative integer value. It is a block diagram which shows an example of the structure of the coding apparatus 100 (200,300). It is a flowchart which shows an example of the operation of the coding apparatus 100 (200,300). It is a figure which shows an example of the code tree when K = 2. It is a figure which shows an example of the code tree when K = 3. It is a figure which shows an example of the code tree when K is generalized. It is a block diagram which shows an example of the structure of the decoding apparatus 150 (250, 350). It is a flowchart which shows an example of the operation of the decoding apparatus 150 (250, 350). It is a figure which shows an example of the correspondence table at the time of K = 2. It is a figure which shows an example of the correspondence table at the time of K = 2. It is a figure which shows an example of the correspondence table at the time of K = 3. It is a figure which shows an example of the correspondence table at the time of K = 3. It is a figure which shows an example of the correspondence table at the time of K = 3. It is a figure which shows an example of the correspondence table at the time of K = 3. It is a block diagram which shows an example of the structure of the coding apparatus 400 (401, 402, 500, 501, 502, 600). It is a flowchart which shows an example of the operation of the coding apparatus 400 (401, 402, 500, 501, 502, 600). It is a block diagram which shows an example of the structure of the decoding apparatus 450 (451, 452, 550, 551, 552, 650). It is a flowchart which shows an example of the operation of the decoding apparatus 450 (451, 452, 550, 551, 552, 650).

Hereinafter, embodiments of the present invention will be described in detail. The components having the same function are given the same number, and duplicate explanations will be omitted.

<First Embodiment>
≪Coding device≫
The processing procedure of the coding method executed by the coding apparatus 100 of the first embodiment will be described with reference to FIGS. 2 and 3. As shown in FIG. 2, the coding device 100 of the first embodiment includes an integer coding unit 110. The coding method of the first embodiment is realized by the coding device 100 of the first embodiment executing the processing of each step shown in FIG.

A sequence of non-negative integer values is input to the coding device 100 of the first embodiment. As a series of non-negative integer values, for example, a signal obtained by converting sound or music picked up by a microphone into a digital signal, a signal obtained by converting an image or video captured by a camera into a digital signal, or the like. A series of absolute values of integer values obtained by quantizing a part or all of the signal of the above to a value of finite precision, or a series of x'obtained by Eq. (1) with the integer value as x. You may enter it.

The coding device 100 of the first embodiment uses a plurality of predetermined code trees according to a predetermined rule, and performs variable length coding of a series of non-negative integer values, so that the bias is larger than that of the Laplace distribution. It realizes a coding process that has a bit length shorter than that of Golomb-Rice coding for a series of non-negative integer values in the distribution. Here, the code tree refers to a graph representing a predetermined rule of which code is assigned to an input non-negative integer value. In the following, a non-negative integer value input to the coding apparatus 100 will be simply referred to as an “integer value” for description.

[Integer encoding unit 110]
The integer coding unit 110 is input with a series of integer values of N samples (N is a natural number) among the series of integer values input to the coding apparatus 100. Let the series of input integer values be the integer series x_1, x_2,…, x_N. The integer coding unit 110 encodes the integer series x_1, x_2, ..., X_N using the following code tree based on the coding parameter K which is two or more natural numbers input by a predetermined or not shown means. A code is obtained by coding in the process, and the obtained code is output as an integer code (S110). In the following explanation, it is assumed that each integer of the integer series x_1, x_2,…, x_N is x_n (n is a sample number in the series, and n ∈ {1, 2, ..., N}).

[[Code tree used for coding process]]
First, a code tree used for the coding process in the integer coding unit 110 will be illustrated.

^{The integer coding unit 110 stores in advance 2 K-1} (2 to the K-1 power) code trees as illustrated in FIGS. 4 to 6. FIG. 4 is an example of a code tree when K = 2, and T (0) and T (1) are code trees, respectively. FIG. 5 shows an example of a code tree when K = 3, and each of T (0) to T (3) is a code tree. FIG. 6 is an example of a code tree when K is generalized, and each of T (0) to T (2 ^K-1 -1) is a code tree. In the following, the number in parentheses attached to T is referred to as a code tree number.

[[Relationship between the input integer value in the code tree and the code corresponding to the integer value]]
Next, the relationship between the input integer value in each code tree and the code corresponding to the integer value will be described.

The integer values enclosed in triangles to the right of each code tree node correspond to the entered integer values. Also, the bit values '0' and '1' on the left side of the edge of each code tree correspond to the code rules assigned to the input integer values. This rule is a rule obtained by allocating a sequence of bit values on the left side of the edge from the node at the upper end of the code tree to the node corresponding to the input integer value as a code assigned to the input integer value.

2 One of the ^K-1 code trees corresponds to T (0) in FIGS. 4 to 6, and the number of bits is K as the code corresponding to the input integer value x_n. Corresponds to the rule of obtaining a code that is × x_n + 1 bits, the bit value of the first bit is '1', and the bit value from the second bit to the K × x_n + 1 bits is '0'. It is a code tree to be used. According to this code tree, when the input integer value x_n is 0, the number of bits of the code K × x_n + 1 is 1 bit, so 1 bit whose bit value is '1' You will get the sign.

Of the 2 ^K-1 code trees, the other 2 ^K-1 -1 code trees correspond to T (1) to T (2 ^K-1 -1) in FIGS. 4 to 6. The number of bits is K × x_n bits, the bit value of the first bit is '0', and the bits from the second bit to the K bit are the codes corresponding to the input integer value x_n. The bit value of at least one of the K-1 bits is '1', and the bit value of the K × (x_n-1) bits from the K + 1th bit to the K × x_nth bit is '0'. That is, it is a code tree corresponding to the rule of obtaining a code in which the bit value of K × (x_n-1) bits is '0' from the end. Here, the K-1 bits from the 2nd bit to the Kth bit are a bit group having a one-to-one correspondence with each of ^{2 K-1 -1 code trees.} According to these code trees, when the input integer value x_n is 0, the number of bits of the code K × x_n is 0 bits, so that no code is obtained.

For example, the input integer value in the case of K = 2 in FIG. 4 and the sign rule corresponding to the integer value are input when the input integer value 0 is encoded by the code tree T (0). When '1' is obtained as the sign corresponding to the entered integer value 0 and the input integer value 1 is encoded by the sign tree T (0), the sign corresponding to the input integer value 1 is '100. When'is obtained and the input integer value 2 is encoded by the sign tree T (0), '10000' is obtained as the sign corresponding to the input integer value 2 and the input integer value 0 is coded. When encoding with the tree T (1), the sign corresponding to the input integer value 0 is not obtained, and when the input integer value 1 is encoded with the code tree T (1), it is input. When '01' is obtained as the sign corresponding to the integer value 1 and the input integer value 2 is encoded by the code tree T (1), '0100' is obtained as the sign corresponding to the input integer value 2. Is the rule to get.

[[Rules using multiple code trees]]
Next, a rule using a plurality of code trees will be described. The integer coding unit 110 also stores in advance rules for using a plurality of code trees.

The orientation of the triangle surrounding the integer value on the right side of the node of each code tree in FIGS. 4 to 6 corresponds to the rule of using a plurality of code trees.

The right-pointing triangle represents a rule that uses a code tree next to the right (a code tree whose code tree number is one higher) when encoding the integer value next to the input integer value. At that time, it is assumed that the right neighbor of the rightmost code tree (the code tree with the largest code tree number) is the leftmost code tree (the code tree with the smallest code tree number). It should be noted that this rule is merely an example, and any rule may be used as long as it is a rule that cyclically uses a plurality of code trees. That is, for each code tree, it is a rule to use a different code tree for encoding the next integer value when it is a right-pointing triangle, and for all code trees, the code of the next integer value when it is a right-pointing triangle. Any rule may be used as long as the code trees used for conversion do not overlap. In the rule of using a plurality of code trees cyclically, the maximum number of code trees used is 2 ^K-1 .

The downward triangle represents a rule that uses the code tree T (1) when coding the next integer value after the input integer value. Note that this rule is just an example, and in the case of a downward triangle, what if the rule is that any one of the predetermined code trees for each downward triangle is used as the code tree used for encoding the next integer value? Rule may be. For example, in the case of a downward triangle, the rule may be that any one of the same code trees predetermined for all downward triangles is used as the code tree used for coding the next integer value. Further, in order to shorten the average number of bits, a code tree other than the code tree corresponding to T (0) in FIGS. 4 to 6 is used for encoding the next integer value in the case of a downward triangle. It is better to use the rule.

In order to make the average number of bits the shortest, in the case of a right-pointing triangle ^{, all 2 K-1} code trees are used cyclically, and for all code trees, in the case of a downward triangle, the figure is shown. In the code tree corresponding to T (0) in FIGS. 4 to 6, the code tree used for encoding the next integer value when it is a right-pointing triangle is used as the code tree used for encoding the next integer value. Is good.

For example, the coding rule using the code tree when K = 2 in FIG. 4 is that when the input integer value 0 is encoded by the code tree T (1), the input integer value 0 is used. It is a rule that the code tree used when encoding the next integer value without obtaining the corresponding sign is T (0), and when the input integer value 2 is encoded by the code tree T (0). Is a rule that obtains '10000' as the sign corresponding to the input integer value 2 and sets the code tree used when encoding the next integer value as T (1).

Any of the plurality of code trees may be used at the beginning of the coding process, but the rule of which code tree is used at the beginning of the coding process is also a rule for using a plurality of code trees in advance. Set and remember. For example, in the case of K = 2 in FIG. 4, when the integer series x_1, x_2, ..., X_N are encoded in order from the integer value x_1, the rule may be a rule for encoding the integer value x_1 with T (0). However, the rule for encoding the integer value x_1 with T (1) may be used, but which of T (0) and T (1) is used for encoding the integer value x_1 is determined and stored in advance.

[[Coding process using code tree]]
The integer coding unit 110 uses the above-mentioned plurality of code trees and predetermined each integer value included in the input integer sequence x_1, x_2, ..., X_N according to the above-mentioned rule using the plurality of code trees. A code is obtained by encoding in order, and the obtained code is output as an integer code. For example, the coding procedure performed by the integer coding unit 110 when the predetermined order is the sample number order in the series and the code tree used first is T (0) is as follows.
(Coding procedure)
1. Set the initial values of sample number n and code tree number to 1,0, respectively.
2. Repeat steps (i) to (iv) below until n = N.
(i) If the code tree number is 0, the code '1' is obtained.
(ii) If the integer value x_n = 0, the code tree number plus 1 is used as the new code tree number. At this time, if 1 is added and the code tree number becomes 2 ^K-1 , 0 is set as a new code tree number.
(iii) If the integer value x_n ≠ 0, the sign of the K bit is obtained by the 1-bit '0' and the corresponding K-1 bit corresponding to the code tree, and the K × (x_n-1) bit. The code '0' of is obtained, and 1 is used as a new code tree number.
(iv) Let n plus 1 be the new n.
3. Remove the first code '1' from the codes obtained in steps 1 and 2.
(Or do not perform the first 2. (i) operation.)
4. Add the code '1' (termination code) to the end of the code obtained in steps 1 to 3.
5. Output the code obtained in steps 1 to 4 as an integer code.

It is not essential to perform 3 of the coding procedures. If the first code tree used is T (0), then whatever the value of x_1 is, the first code obtained from 1-2 is '1'. .. Therefore, even if the coding device 100 outputs the integer code obtained by removing the code '1' obtained first, if the decoding device 150 adds the code '1' to the beginning of the input integer code, it is encoded. The decoding device 150 can perform the decoding process corresponding to the coding process performed by the integer coding unit 110 of the device 100. For this reason, in step 3 of the coding procedure, the code ‘1’ obtained first is removed. However, it is not always necessary to perform step 3 of the coding procedure, and it is not necessary to remove the first code ‘1’ obtained from the codes obtained in steps 1 and 2. In this case, the corresponding decoding device 150 may not perform the process of adding the code ‘1’ to the beginning of the input integer code, and may not perform step 3 of the coding procedure.

Further, depending on how the integer code is transmitted from the coding device 100 to the decoding device 150, step 4 of the coding procedure may not be performed. The decoding procedure in the decoding device 150 will be described later, but in order for the decoding device 150 to perform the decoding process corresponding to the coding process performed by the integer coding unit 110, the decoding device 150 needs to be able to specify the end of the integer code. There is. As a configuration for transmitting an integer code from the coding device 100 to the decoding device 150, for example, a packet in which the integer code obtained for the integer series x_1, x_2, ..., X_N in the coding device 100 or in the subsequent stage of the coding device 100 is known. It is possible to adopt a configuration in which the packet is stored in a packet and transmitted to the decoding device 150 by using the method of conversion. In this case, since the decoding side adopts a configuration in which the integer code is taken out from the packet in the decoding device 150 or in the stage before the decoding device 150, the decoding device 150 can specify the end of the integer code. Therefore, in such a case, step 4 of the coding procedure may not be performed. As a configuration for transmitting the integer code from the encoding device 100 to the decoding device 150, the integer code obtained for the integer series x_1, x_2, ..., X_N is concatenated with another code and stored in the above-mentioned packet. The configuration is adopted to transmit to the decoding device 150, or to concatenate another code after the integer code obtained for the integer series x_1, x_2, ..., x_N without performing the above-mentioned packetization and transmit it to the decoding device 150. Sometimes. In these configurations, if 4 of the coding steps is not performed, when the code concatenated at the end is '0000', etc., how far is the code corresponding to the Nth integer value, and at the end? The decoding device 150 cannot determine where the code linked to is from. Therefore, in these configurations, it is decoded that the integer code corresponds to N integer values by storing the same predetermined N value in the coding device 100 and the decoding device 150. It is necessary to make the device 150 recognizable and also perform 4 of the coding procedures so that the decoding device 150 can identify the end of the integer code.

The reference numeral '0' in the above description is an example of one of the binary bit values, and the reference numeral '1' in the above description is an example of the other bit value of the binary bit values. Is. That is, as a matter of course, the code "1" may be used instead of the code "0" described above, and the code "0" may be used instead of the code "1".

[[Example of coding process]]
As an example of coding processing, when the code tree used first at K = 2 is T (0), the input integer series x_1, x_2, x_3, x_4, x_5 is 0, 0, 2, 0, 0. The coding process in the case of is described. First, since the first integer value x_1 = 0 is encoded by T (0), the sign '1' is obtained, and the sign tree number 0 plus 1 is used as the new code tree number, so the next integer value. Let T (1) be the code tree used to encode x_2 = 0. Since the next integer value x_2 = 0 is encoded by T (1), no sign is obtained, and the code tree number obtained by adding 1 to the code tree number 1 is used as the code tree number, but the code tree number obtained by adding 1 is 2 ^{K. Since} it became -1, 0 is used as the new code tree number, and the code tree used for encoding the next integer value x_3 = 2 is T (0). Since the third integer value x_3 = 2 is encoded by T (0), the code '10000' is obtained, and the new code tree number is set to 1, so the next integer value x_4 = 0 is encoded. Let T (1) be the code tree used. Since the fourth integer value x_4 = 0 is coded by T (1), no sign is added and the code tree is transitioned from T (1) to T (0). Since the last integer value 0 is coded by T (0), the code '1' is obtained. The code obtained so far is '1100001', but when the above-mentioned coding procedure 3 is performed and the above-mentioned coding procedure 4 is not performed, the code '1' obtained first is omitted. Obtain the final integer code '100001'.

≪Decoding device≫
The processing procedure of the decoding method executed by the decoding device 150 of the first embodiment will be described with reference to FIGS. 7 and 8. As shown in FIG. 7, the decoding device 150 of the first embodiment includes an integer decoding unit 160. The decoding method of the first embodiment is realized by the decoding device 150 of the first embodiment executing the processing of each step shown in FIG.

An integer code output by the coding device 100 of the first embodiment is input to the decoding device 150 of the first embodiment. The decoding device 150 of the first embodiment converts the input integer code into a plurality of predetermined code trees corresponding to the coding device 100 of the first embodiment in advance corresponding to the coding device 100 of the first embodiment. The sequence of non-negative integer values input to the coding apparatus 100 of the first embodiment is restored by decoding by the decoding process used according to the defined rule to obtain a sequence of non-negative integer values. is there. Hereinafter, as in the above description of the coding apparatus 100, a non-negative integer value will be referred to simply as an “integer value”.

[Integer decoding unit 160]
The integer code input to the decoding device 150 is input to the integer decoding unit 160. The integer decoding unit 160 has the same value as the coding parameter K used by the integer coding unit 110 of the coding device 100, and is a natural number of two or more input by a predetermined or not shown means. Based on the above, the input integer code is decoded by the decoding process using the following code tree to obtain a sequence of integer values, and the obtained integer sequence x_1, x_2, ..., X_N is output (S160). In the following explanation, it is assumed that each integer of the integer series x_1, x_2,…, x_N is x_n (n is a sample number in the series, and n ∈ {1, 2, ..., N}).

The code tree used for the decoding process is the same as the code tree used by the integer coding unit 110 of the coding device 100 of the first embodiment, and the integer decoding unit 160 has 2 as illustrated in FIGS. 4 to 6. ^K-1 code trees (2 to the K-1 power) are stored in advance. The relationship between the input code in the code tree in the decoding process and the integer value corresponding to the code and the rule using a plurality of code trees are the coding process of the integer coding unit 110 of the coding device 100 of the first embodiment. Corresponds to the rule in the above, and the "code assigned to the input integer value" of the rule in the coding process of the integer coding unit 110 of the coding device 100 of the first embodiment is read as "input code". , "The input integer value" is read as "the integer value assigned to the input code", and is stored in advance in the integer decoding unit 160. The value of the parameter K used in the decoding process is the same as the value of the parameter K used by the integer coding unit 110 of the coding device 100 of the first embodiment, and is stored in advance in the integer decoding unit 160. Further, the rule of which code tree is used first in the decoding process is the same as the rule used by the integer coding unit 110 of the coding device 100 of the first embodiment, and is stored in advance in the integer decoding unit 160. I will do it.

The integer decoding unit 160 uses the above-mentioned plurality of code trees to obtain a sequence of integer values corresponding to the input integer code according to the above-mentioned rule of using a plurality of code trees, and obtains a column of integer values. Each integer of is in a predetermined order, and is obtained and output as an integer sequence x_1, x_2,…, x_N. For example, when the predetermined order is the sample number order in the series and the code tree used first is T (0), the decoding procedure performed by the integer decoding unit 160 is, for example, the following decoding procedure 1 or decoding procedure. There are two streets.

(Decoding procedure 1-1) When the terminal code is not added according to the coding procedure 4, that is, when the decoding device 150 can specify the terminal of the integer code.
1. If the code '1' was removed in coding procedure 3, add the code '1' to the beginning of the integer code.
2. Set the initial value of the code tree number to 0.
3. Repeat steps (i) to (ii) below until there are no unread integer signs, and proceed to 4 when there are no unread integer signs.
(i) While there is a code corresponding to the code read in the code tree corresponding to the code tree number (that is, the code corresponding to the code read in the code tree corresponding to the code tree number) Read up to the previous bit).
(ii) Obtain an integer value corresponding to the code corresponding to the read code from the code tree corresponding to the code tree number, and obtain a new code tree number according to the code tree transition rule for the integer value of the code tree. obtain.
4.3 Output the series of integer values obtained in (ii) as integer series x_1, x_2,…, x_N.

(Decoding procedure 1-2) When the terminal code is added according to the coding procedure 4, that is, when the decoding device 150 cannot specify the terminal of the integer code.
1. If the code '1' is removed in coding procedure 3, the code '1' is added to the beginning of the input code string (integer code followed by another code).
2. Set the initial values of sample number n and code tree number to 1 and 0, respectively.
3. Repeat steps (i) to (ii) below until n = N.
(i) While there is a code corresponding to the code read in the code tree corresponding to the code tree number in order of the input code string (that is, the code corresponding to the code read in the code tree corresponding to the code tree number is Read up to the previous bit).
(ii) Obtain an integer value corresponding to the code corresponding to the read code from the code tree corresponding to the code tree number, and obtain a new code tree number according to the code tree transition rule for the integer value of the code tree. The new n is obtained by adding 1 to n.
4.3 Output the series of integer values obtained in (ii) as integer series x_1, x_2,…, x_N.

(Decryption procedure 2)
1. If the terminal code was not added in coding procedure 4, add the terminal code '1' to the end of the input code string. If the code '1' is not removed in the coding procedure 3, the code '1' is removed at the beginning of the input code string.
2. Set the initial values of sample number n and code tree number to 1 and 0, respectively.
3. Repeat steps (i) to (v) below until n ≧ N.
(i) While all K bits have the code '0', the input code string is read in order by K bits, and the number of the code '0' read during that period divided by K is defined as L.
(ii) If the code tree number is 0, the integer value L is obtained.
(iii) If the code tree number is non-zero, get an integer value (L + 1).
(iv) If the next 1 bit of the input code string is code '1', read that 1 bit, get (2 ^K-1 -1) integer values 0, and set 0 to the new code tree number. Then, the sum of n and 2 ^K-1 is used as the new n.
(v) If the next 1 bit of the input code string is sign '0', the K bit containing that 1 bit is read, and the number corresponding to the sign of that K bit is used as the new code tree number (new code). Tree number-1) Obtain 0 integer values and add a new code tree number to n to make a new n.
4. If the number of obtained integer values is more than N, remove the N + 1th and subsequent integer values.

[[Example of decryption process]]
As an example of the decoding process, when the code tree used first at K = 2 is T (0), the integer code '100001' obtained in the above-mentioned coding process example is decoded by the above-mentioned decoding procedure 1-1. The decoding process in the case of performing is described. First, the sign '1' is added to the beginning of the integer sign '100001' to make the integer sign '1100001'. Next, the first 1 bit of the integer sign '1100001', '1', has a sign corresponding to the sign tree T (0), but the first 2 bits, '11', are in the sign tree T (0). Since there is no corresponding sign, the first bit of the integer sign, '1', is read, the integer value 0 corresponding to '1' is obtained, and the sign tree to be used next is T (1). Next, since the first 1 bit of the remaining '100001' of the integer sign, '1', does not have a sign corresponding to the sign tree T (1), the first 1 bit is not read and corresponds to 0 bits. Obtain an integer value of 0, and let T (0) be the code tree used next. Next, from the first 1 bit of '100001', which is the first bit of the integer sign, to '10000', which is the first 5 bits, the corresponding sign is in the sign tree T (0), but of the integer sign. The first 6 bits of the remaining '100001', '100001', has no corresponding sign in the sign tree T (0), so the first 5 bits of the remaining '100001' of the integer sign, '10000' Read, get the integer value 2 corresponding to '10000', and let T (1) be the code tree to be used next. Next, since the remaining '1' of the integer code does not have a corresponding code in the code tree T (1), the first 1 bit is not read, and the integer value 0 corresponding to 0 bit is obtained and used next. Let the sign tree be T (0). Next, the remaining '1' of the integer sign has the corresponding sign in the code tree T (0), and since there is no unread integer sign after this '1', the integer value 0 corresponding to '1' Is obtained, and the series of integer values 0, 0, 2, 0, 0 obtained by these processes is output as the integer series x_1, x_2, x_3, x_4, x_5.

<Explanation of the principle of the invention>
Here, the principle of the present invention will be described.

According to the coding device 100 of the first embodiment, it is possible to assign a code to all the non-negative integer values, and the decoding device 150 of the first embodiment decodes the code to obtain the non-negative integer value itself. Is to be recoverable. As shown in FIGS. 4 to 6, the sign corresponding to the non-negative integer value x_n is K × x_n bits or K × x_n + 1 bits. From this, the code of the present invention used in the first embodiment is a code that gives an approximately optimum expected bit length to a series of non-negative integer values that follow the following one-sided Laplace distribution with a large bias, and is a small value. It is a code that can make the average number of bits for a series of non-negative integer values that are largely biased toward Golomb-Rice code smaller than that of the Golomb-Rice code.

The Golomb-Rice code shown in Eq. (3) has the optimum distribution p (x, 2 ^r ), and the code of the present invention shown in Eq. (4) has the optimum distribution p (x, 1 / K). From the correspondence, it can be seen that the logarithm of the reciprocal of the coding parameter K of the present invention corresponds to the Rice parameter r. Further, since the coding parameter K of the present invention is a positive integer value, the logarithm of the reciprocal of the coding parameter K is a negative value, so that the coding parameter K is a parameter corresponding to the Rice parameter extended to a negative value. Can be interpreted as. That is, by estimating the optimum Rice parameter for the series of non-negative integer values, the optimum parameter K in the code of the present invention assigned to the series of non-negative integer values can be estimated.

The relationship between the integer value in the code tree of the present invention used in the coding device 100 and the decoding device 150 of the first embodiment and the code corresponding to the integer value, and the rule using a plurality of code trees are non-negative. It is designed not only to set the code corresponding to the numerical value x_n to K × x_n bits or K × x_n + 1 bits, but also to make it a decodable code. Specifically, a 1-bit sign '1' is assigned to any number of consecutive numbers from 2 to 2 ^{K-1 integer values 0, and 0 is an integer value 0.} For a maximum of 2 ^K-1 -1 consecutive numbers and one non-negative integer value x_n ≠ 0 that follows, at least one bit value '1' is included in the first K bits. There is a restriction that a code that is included and the subsequent bit values are '0' is assigned. By providing this restriction, when the decoding device 150 reads an integer code corresponding to an integer series consisting of a plurality of integer values, the part containing the bit value '1' in the K bit is contained in the integer code. It is made to be understood that the boundary between a certain sign and the next sign is included. In order to satisfy the above-mentioned restrictions, the ^{number of sign bits for a predetermined maximum of 2 K-1} -1 consecutive values and one non-negative integer value x_n following it is K × x_n bits. Not only K × x_n bits or K × x_n + 1 bits.

<Second embodiment>
In the first embodiment, the embodiment of realizing the coding and decoding of the present invention by using a predetermined code tree has been described, but it is also possible to use a predetermined correspondence table instead of the predetermined code tree. It is possible to realize the coding process and the decoding process equivalent to one embodiment. A mode using this predetermined correspondence table will be described as a second embodiment.

≪Coding device≫
The processing procedure of the coding method executed by the coding apparatus 200 of the second embodiment will be described with reference to FIGS. 2 and 3. As shown in FIG. 2, the coding device 200 of the second embodiment includes an integer coding unit 210 like the coding device 100 of the first embodiment. Similar to the coding device 100 of the first embodiment, the coding device 200 of the second embodiment executes the processing of each step shown in FIG. 3, thereby realizing the coding method of the second embodiment.

As in the first embodiment, a sequence of non-negative integer values is input to the coding device 200 of the second embodiment. The coding apparatus 200 of the second embodiment performs variable-length coding of a series of non-negative integer values according to a predetermined correspondence table, so that the series of non-negative integer values having a distribution larger than the Laplace distribution is subjected to variable length coding. It realizes a coding process with a bit length shorter than that of Golomb-Rice coding. Hereinafter, the non-negative integer value input to the encoding device 200 will be referred to simply as an “integer value” for description.

[Integer encoding unit 210]
In the integer coding unit 210, an integer series x_1, x_2, ..., X_N for each N samples of the series of integer values input to the coding device 200 is input. The integer coding unit 210 of the second embodiment is an integer input based on a correspondence table created in advance corresponding to the coding parameter K which is a natural number of 2 or more and stored in the integer coding unit 210. The series x_1, x_2, ..., X_N are encoded to obtain a code, and the obtained code is output as an integer code (S210).

[[Correspondence table used for coding processing]]
The correspondence table stored in advance is a rule of correspondence between a sub-series of integer values by a combination of a series of zero values (sequential of 0 or more) and one non-zero value, and a code corresponding to the sub-series. Is stored. Examples of correspondence tables for K = 2 and K = 3 are shown in FIGS. 9 (A, B) and 10 (A, B, C, D), respectively. According to the rules stored in the correspondence table, a 1-bit sign with a bit value of '1' is assigned to a subseries with ^{2 K-1 consecutive zero values, and the other subseries, that is, from 0} 2 ^K-1 -1 consecutive zeros followed by one non-zero value x_n in a subseries with K × x_n bits or K × for each combination of consecutive zero values and non-zero values x A rule that assigns a sign of x_n + 1 bits.

In the illustrated correspondence table, each subseries with 0 to 2 ^K-1 -1 consecutive zeros followed by one nonzero value x_n has at least one bit of '1 in the first K bits. It is a rule that'exists and the remaining K × (x_n-1) bits or K × (x_n-1) + 1 bits are all assigned a code of '0'. More specifically, in this rule, the bit value of the first bit is '1' and the bit value of the second bit is '1' in the subseries with ^{0 to 2 K-1 -1 consecutive zero values and one non-zero value.} The code of the K × x_n + 1 bits, or the code of the K × x_n + 1 bits, in which the bit values from the K + 1 bit to the K bit are all '0' and the bit values from the K + 1 bit to the K × x_n + 1 bit are all '0'. , The bit value of the 1st bit is '0', the bit value of at least 1 bit in the K-1 bits from the 2nd bit to the K bit is '1', and the bit value from the K + 1th bit to K × The code of the K × x_n bit, in which all the bit values up to the x_nth bit are '0', is assigned. More specifically, in this rule, the bit value of the first bit of the code of K × x_n + 1 bits is '1', and the first bit from the second bit to the K + 1 bit is '0'. The bit value of the first bit of the K × x_n bits and one partial code from the K + 1 bit to the K + 1 bit is '0', and the K-1 bits from the second bit to the K bit ^{2 K-1} 1 partial code from the 1st bit to the K bit whose bit value of at least 1 bit is '1', ^{2 K-1} partial code by, and 0 to 2 ^K-1 -There is a one-to-one correspondence between the number of consecutive zero values 2 ^{K-1 and.}

[[Coding process using correspondence table]]
The integer coding unit 210 encodes each integer value included in the input integer series x_1, x_2, ..., X_N in a predetermined order using the above-mentioned correspondence table to obtain a code, and obtains a code, and obtains a code as an integer. Output as a code. For example, the coding procedure performed by the integer coding unit 210 when the predetermined order is the sample number order in the series is as follows.
(Coding procedure)
1. Let sample number n be 1.
2. Repeat steps (i) to (ii) below until n = N.
(i) ^{If there is a non-zero value in 2 K-1} integer values after x_n, obtain the sign corresponding to the sub-series from x_n to the first non-zero value from the code table, and x_n The new n is obtained by adding the number of samples up to the first non-zero value thereafter to n.
(ii) ^{If all 2 K-1} integer values after x_n are zero values, ^{obtain the code corresponding to the subseries of 2 K-1} integer values after x_n from the code table, and 2 ^{Let K-1} be added to n and be the new n.
Add the code '1' (termination code) to the end of the code obtained in 3.2.
The code obtained in 4.3 is output as an integer code.

As in the first embodiment, the process of adding the terminal code (3 of the coding procedure) may not be performed depending on how the integer code is transmitted from the coding device 200 to the decoding device 250.

The codes obtained by the coding process using FIGS. 9 (A, B) and 10 (A, B, C, D) in the integer coding unit 210 of the coding device 200 of the second embodiment are respectively. , In the coding process using the code tree of FIGS. 4 and 5 in the integer coding unit 110 of the coding device 100 of the first embodiment, the code obtained when the code tree used first is T (1). Match. Further, when coding is performed by the integer coding unit 210 of the coding device 200 of the second embodiment using each of FIGS. 9 (A, B) and 10 (A, B, C, D). ^{Add (2 K-1} -1) zero values to the beginning of the input integer sequence x_1, x_2,…, x_N, and then perform coding, and the sign '1' at the beginning of the obtained integer sign. If is removed, the code tree used first in the coding process using the code trees of FIGS. 4 and 5 in the integer coding unit 110 of the coding device 100 of the first embodiment is T (0). It matches the code obtained when. As described above, the coding process using the correspondence table in the integer coding unit 210 of the coding device 200 of the second embodiment uses the code tree in the integer coding unit 110 of the coding device 100 of the first embodiment. It is equivalent to the coding process that was used.

≪Decoding device≫
The processing procedure of the decoding method executed by the decoding device 250 of the second embodiment will be described with reference to FIGS. 7 and 8. As shown in FIG. 7, the decoding device 250 of the second embodiment includes an integer decoding unit 260 like the decoding device 150 of the first embodiment. The decoding method of the second embodiment is realized by the decoding device 250 of the second embodiment executing the processing of each step shown in FIG. 8 in the same manner as the decoding device 150 of the first embodiment.

Like the decoding device 150 of the first embodiment, the decoding device 250 of the second embodiment is input with an integer code output by the coding device 200 of the second embodiment. The decoding device 250 of the second embodiment decodes the input integer code by a decoding process using the correspondence table and the correspondence table stored in the integer coding unit 210 of the coding device 200 of the second embodiment. By obtaining a sequence of non-negative integer values, the sequence of non-negative integer values itself input to the coding apparatus 200 of the second embodiment is restored. Hereinafter, as in the above description of the coding device, a non-negative integer value will be simply referred to as an “integer value”.

[Integer decoding unit 260]
The integer code input to the decoding device 250 is input to the integer decoding unit 260. The integer decoding unit 260 is a correspondence table created in advance and stored in the integer decoding unit 260, is a correspondence table prepared in advance corresponding to the coding parameter K, and is an integer coding unit 210 of the encoding device 200. Based on the same correspondence table stored in advance and used in the integer coding unit 210, the input integer code is decoded to obtain the integer series x_1, x_2, ..., X_N and output (S260).

More specifically, the integer decoding unit 260 reads the unread code portion of the input integer code from the beginning to the part having the code corresponding to the correspondence table, and the integer part corresponding to the read code. The process of obtaining a series from the correspondence table is repeated from the beginning to the end of the input integer code, and the series that summarizes the sub-series of integers obtained is output as the integer series x_1, x_2,…, x_N. By this decoding process, in the decoding process using the respective code trees of FIGS. 4 and 5 in the integer decoding unit 160 of the decoding device 150 of the first embodiment, it is the same as the case where the code tree used first is T (1). You can get the integer series x_1, x_2,…, x_N.

^{In the integer coding unit 210 of the encoding device 200, (2 K-1} -1) zero values are added to the beginning of the input integer series x_1, x_2, ..., X_N before encoding. When the process of removing the code '1' at the beginning of the obtained integer code is performed, the integer decoding unit 260 adds the code '1' to the beginning of the input integer code and then performs the above correspondence table. Each sub-series is obtained by the above-mentioned decoding process based on the above, and ^{after omitting the (2 K-1} -1) zero values obtained at the beginning, the integer series x_1, x_2,…, x_N that summarizes the sub-series is obtained. You can output it. By this decoding process, it is the same as the case where the code tree used first in the decoding process using the respective code trees of FIGS. 4 and 5 in the integer decoding unit 160 of the decoding device 150 of the first embodiment is set to T (0). You can get the integer series x_1, x_2,…, x_N. As described above, the decoding process using the correspondence table in the integer decoding unit 260 of the decoding device 250 of the second embodiment is equivalent to the decoding process using the code tree in the integer decoding unit 160 of the decoding device 150 of the first embodiment. It is a thing.

As can be seen from the above, the integer code obtained by the coding process using the code tree by the coding device 100 of the first embodiment is subjected to the correspondence table corresponding to the coding process by the decoding device 250 of the second embodiment. The integer code obtained by decoding in the decoding process used to obtain an integer sequence x_1, x_2, ..., x_N, or by the coding process using the correspondence table by the coding apparatus 200 of the second embodiment is obtained in the first embodiment. The decoding device 150 of the above may perform decoding by a decoding process using a code tree corresponding to the coding process to obtain an integer sequence x_1, x_2, ..., X_N.

<Third Embodiment>
In the first embodiment and the second embodiment, a mode for realizing the coding and decoding of the present invention has been described from the procedural aspect of coding and decoding using a predetermined code tree or a predetermined correspondence table. In the third embodiment, a mode for realizing the coding and decoding of the present invention from the data aspect of a sequence of codes and integer values obtained by these procedures will be described.

≪Coding device≫
The processing procedure of the coding method executed by the coding apparatus 300 of the third embodiment will be described with reference to FIGS. 2 and 3. As shown in FIG. 2, the coding device 300 of the third embodiment includes an integer coding unit 310, like the coding device 100 and the coding device 200. Similar to the coding device 100 and the coding device 200, the coding device 300 of the third embodiment executes the processing of each step shown in FIG. 3, thereby realizing the coding method of the third embodiment.

Similar to the coding device 100 and the coding device 200, a sequence of non-negative integer values (hereinafter, referred to as “integer sequence”) is input to the coding device 300 of the third embodiment. Hereinafter, the non-negative integer value input to the encoding device 300 will be referred to simply as an “integer value” for description.

[Integer encoding unit 310]
The integer coding unit 310 is a 1-bit code (hereinafter, "code") as a code corresponding to a series of any predetermined number of ^{2 to 2 K-1} integer values included in the integer series. A ”) is obtained, ^{and K is used as the sign corresponding to the set of 0 to 2 K-1} -1 consecutive integer values 0 and one non-zero integer value x_n included in the integer series. A code of × x_n bits or K × x_n + 1 bits (hereinafter referred to as “reference B”) is obtained (S310). However, K represents a coding parameter that is a natural number of 2 or more. Specifically, the integer series x_1, x_2, ..., X_N for each N sample is encoded using the code tree described in the first embodiment and the correspondence table described in the second embodiment, and the code A and the code are used. Get B. Here, assuming that the number of 0s included in the sequence of integer values 0 corresponding to the symbol A is L (2 ≤ L ≤ 2 ^K-1 ), the code B obtained in S310 is from 0 of the integer values 0 to L. -1 or K × x_n or K × x_n + 1 bits corresponding to a predetermined maximum of 2 ^{K-1 -1 sequence followed by one non-zero integer value x_n.} ..

Further, here, assuming that the bit value “x” is the bit value “1” and the bit value “y” is the bit value “0”, the code A is a 1-bit code in which the bit value is “x”. Yes (see FIGS. 9B and 10D), reference numeral B contains at least one bit value “x” and at least one bit value “y” from the first bit to the Kth bit, and K × (from the end). The x_n-1) bit has a bit value of "y" (see FIGS. 9A and 9B, FIGS. 10A to 10D). As described above, the bit value “x” may be the bit value “0” and the bit value “y” may be the bit value “1”.

Further, regarding the code B, more specifically, the continuous number of 2 ^{K-1 patterns from 0 to 2 K-1} of the integer value 0 in the integer series and the following 2 ^K-1 patterns of partial codes. There is a one-to-one correspondence between them.
(Partial code of code B)
(1) When the code B is K × x_n + 1 bits, it is composed of K + 1 bits from the 1st bit to the K + 1 bit of the code B, and the bit value of the 1st bit is “x”. And the bit value from the 2nd bit to the K + 1th bit is "y".
(2) When the code B is K × x_n bits, it is composed of K bits from the first bit to the K bit of the code B, the bit value of the first bit is “y”, and the second bit. ^{2 K-1} -1 partial code in which the bit value of at least 1 bit in the K-1 bits from to the Kth bit is “x”

≪Decoding device≫
The processing procedure of the decoding method executed by the decoding device 350 of the third embodiment will be described with reference to FIGS. 7 and 8. As shown in FIG. 7, the decoding device 350 of the third embodiment includes an integer decoding unit 360, like the decoding device 150 and the decoding device 250. The decoding method of the third embodiment is realized by the decoding device 350 of the third embodiment executing the processing of each step shown in FIG. 8 in the same manner as the decoding device 150 and the decoding device 250.

Similar to the decoding device 150 and the decoding device 250, the decoding device 350 of the third embodiment is input with the code string output by the coding device 300 of the third embodiment. In the following, the non-negative integer value will be simply referred to as an “integer value” and will be described in the same manner as in the description of the coding device described above.

[Integer decoding unit 360]
The integer decoding unit 360 is a predetermined number of ^{2 to 2 K-1} integer values 0 from the 1-bit code (hereinafter referred to as "sign A") included in the input code string. From the sign of K × x_n bits or K × x_n + 1 bits (hereinafter referred to as “sign B”) contained in the input code string, 0 to 2 ^K-1 -1 consecutive sequences A pair of a numerical value 0 and one non-zero integer value x_n is obtained (S360). However, K represents a coding parameter that is a natural number of 2 or more. Specifically, the code included in the input code string is decoded using the code tree described in the first embodiment and the correspondence table described in the second embodiment to correspond to the code A and the code B. Obtain a series of the above integer values. Here, assuming that the number of 0s included in the sequence of integer values 0 obtained from the sign A is L (2 ≤ L ≤ 2 ^K-1 ), 0 included in the sequence of integer values 0 obtained from the sign B in S360. The number of is from 0 to L-1.

Further, here, assuming that the bit value “x” is the bit value “1” and the bit value “y” is the bit value “0”, the code A is a 1-bit code in which the bit value is “x”. Yes (see FIGS. 9B and 10D), reference numeral B contains at least one bit value “x” and at least one bit value “y” from the first bit to the Kth bit, and K × (from the end). The x_n-1) bit has a bit value of "y" (see FIGS. 9A and 9B, FIGS. 10A to 10D). As with the encoding device 300, the bit value “x” may be the bit value “0” and the bit value “y” may be the bit value “1”.

The integer decoding unit 360 can specify the code A and the code B included in the input code string by performing the following two processes. Specifically, the integer decoding unit 360 reads the input code string in order from the beginning of the input code string by consecutive K bits (hereinafter referred to as "K bit string"), and reads the input code string. When the K bit string contains "y", the bit immediately preceding the K bit string containing "y" is identified as the terminal bit of the code A or the code B.

Further, regarding the symbol B, more specifically, the following 2 ^{K-1 partial codes and 0 to 2 K-1} of integer values 0 in the series of integer values obtained by the integer decoding unit 360 are used. There is a one-to-one correspondence with the continuous number of 2 ^{K-1 ways.}
(Partial code of code B)
(1) When the code B is K × x_n + 1 bits, it is composed of K + 1 bits from the 1st bit to the K + 1 bit of the code B, and the bit value of the 1st bit is “x”. And the bit value from the 2nd bit to the K + 1th bit is "y".
(2) When the code B is K × x_n bits, it is composed of K bits from the first bit to the K bit of the code B, the bit value of the first bit is “y”, and the second bit. ^{2 K-1} -1 partial code in which the bit value of at least 1 bit in the K-1 bits from to the Kth bit is “x”

≪Data structure of code string≫
The data structure of the code string handled by the coding device and the decoding device of the third embodiment, that is, the code string obtained from the sequence of integer values by the coding devices of the first embodiment and the second embodiment, and the first embodiment. The data structure of the code string used by the decoding apparatus of the embodiment and the second embodiment to obtain a sequence of integer values will be described.

[Data structure of code string]
A code string representing a sequence of integer values that is a non-negative value (hereinafter referred to as "integer sequence") is used in a coding device that obtains a code string from an integer series and a decoding device that obtains an integer series from a code string.

The data structure of the code string is a 1-bit code (hereinafter, "1 bit code", which is a code corresponding to any number of consecutive numbers ^{from 2 to 2 K-1 of} integer values included in the integer series. It is a sign corresponding to (referred to as "sign A"), a set of 0 to 2 ^K-1 -1 consecutive integer values 0 and one non-zero integer value x_n contained in the integer series. Includes a code of K × x_n bits or K × x_n + 1 bits (hereinafter referred to as “reference B”). However, K represents a coding parameter that is a natural number of 2 or more. Here, assuming that the number of 0s included in the sequence of integer values 0 corresponding to the sign A is L (2 ≤ L ≤ 2 ^K-1 ), the sign B is from 0 to L-1 of the integer values 0. That is, it is a sign of K × x_n bits or K × x_n + 1 bits corresponding to a predetermined maximum of 2 ^{K-1 -1 consecutive values and one subsequent non-zero integer value x_n.}

Further, here, assuming that the bit value “x” is the bit value “1” and the bit value “y” is the bit value “0”, the code A is a 1-bit code in which the bit value is “x”. Yes (see FIGS. 9B and 10D), reference numeral B contains at least one bit value “x” and at least one bit value “y” from the first bit to the Kth bit, and K × (from the end). The x_n-1) bit has a bit value of "y" (see FIGS. 9A and 9B, FIGS. 10A to 10D). As described above, the bit value “x” may be the bit value “0” and the bit value “y” may be the bit value “1”.

Further, regarding the code B, more specifically, the continuous number of 2 ^{K-1 patterns from 0 to 2 K-1} of the integer value 0 in the integer series and the following 2 ^K-1 patterns of partial codes. There is a one-to-one correspondence between them.
(Partial code of code B)
(1) When the code B is K × x_n + 1 bits, it is composed of K + 1 bits from the 1st bit to the K + 1 bit of the code B, and the bit value of the 1st bit is “x”. And the bit value from the 2nd bit to the K + 1th bit is "y".
(2) When the code B is K × x_n bits, it is composed of K bits from the first bit to the K bit of the code B, the bit value of the first bit is “y”, and the second bit. ^{2 K-1} -1 partial code in which the bit value of at least 1 bit in the K-1 bits from to the Kth bit is “x”

According to the invention of the present embodiment, a series of integer values that are largely biased toward small values, including small values that are not zero values, and integer values that are biased to the extent that the technology of Non-Patent Document 2 cannot handle them. Even a series of can be encoded with a small average number of bits. Moreover, such a code can be decoded.

<Fourth Embodiment>
As described above, the coding parameter K used for the code of the present invention has its reciprocal logarithm corresponding to the Rice parameter in the Golomb-Rice code, and the code of the present invention is also interpreted as a Golomb-Rice code for a negative Rice parameter. it can. Therefore, the optimum coding parameter K is obtained for the sub-series of the series by the input integer value based on the conventional method of estimating the optimum Rice parameter, and from the first embodiment using the obtained coding parameter K. The processing of the integer coding unit of the third embodiment may be combined with Golomb-Rice coding to encode a series of input integer values, or decoding corresponding to this coding may be performed. This embodiment will be described as a fourth embodiment.

≪Coding device≫
The processing procedure of the coding method executed by the coding apparatus 400 of the fourth embodiment will be described with reference to FIGS. 11 and 12. As shown in FIG. 11, the coding device 400 of the fourth embodiment includes a parameter determining unit 420 and an integer coding unit 410. When the coding apparatus 400 of the fourth embodiment executes the processing of each step shown in FIG. 12, the coding method of the fourth embodiment is realized.

A series of non-negative integer values is input to the coding device 400 of the fourth embodiment as in the first to third embodiments. The sequence of non-negative integer values input to the coding apparatus 400 of the fourth embodiment is input to the parameter determination unit 420 and the integer coding unit 410 by N samples at a time. That is, the coding device 400 of the fourth embodiment converts a sequence of integer values such as a sequence of absolute values of integer values obtained by converting voice or music picked up by a microphone into a digital signal and quantizing the sequence. Encode frame by frame with N samples.

Hereinafter, the non-negative integer value input to the coding apparatus of the present embodiment will be referred to simply as an “integer value” and will be described.

[Parameter determination unit 420]
The parameter determination unit 420 is input with an integer sequence x_1, x_2, ..., X_N for each N samples from the sequence of integer values input to the encoding device 400. Based on the input integer sequence x_1, x_2, ..., X_N, the parameter determination unit 420 obtains and outputs the Rice parameter r corresponding to the integer sequence and the parameter code representing the parameter (S420). .. The parameter code may be obtained by encoding the Rice parameter so that the decoding device 450 can obtain the Rice parameter r determined by the parameter determination unit 420 by decoding the parameter code.

The parameter determination unit 420 obtains the Rice parameter r by Eq. (5) using each integer value included in the input integer series x_1, x_2, ..., X_N, for example.

The Rice parameter r obtained by Eq. (5) minimizes the estimated value of the total bit length at the time of Golomb-Rice coding estimated by Eq. (2) for the integer series x_1, x_2,…, x_N.

Then, the parameter determination unit 420 obtains a code by scalar-quantizing the Rice parameter r obtained by, for example, Eq. (5), outputs the obtained code as a parameter code, and of the Rice parameter r corresponding to the parameter code. Output the quantized value as Rice parameter r.

[Integer encoding unit 410]
The integer coding unit 410 contains an integer series x_1, x_2, ..., x_N for each N sample of the integer value series input to the coding device 400, and a Rice parameter r output by the parameter determination unit 420. Entered. When the Rice parameter r is a non-negative value, the integer coding unit 410 rounds the Rice parameter r to an integer value by rounding off the first decimal place of the Rice parameter r, and then rounds the Rice parameter r to an integer value, and then the integer series x_1, x_2, …, Golomb-Rice coding is performed on x_N with the integer value Rice parameter r, and the code obtained by Golomb-Rice coding is output as an integer code. If the Rice parameter r is a negative value, Obtain the value of K from the Rice parameter r by K = 2 ^-r, and round the value of K to an integer value by rounding off the first decimal place of the obtained value of K to obtain the coded parameter K. Then, using the obtained coding parameter K, an integer code is obtained and output by the same processing as any of the processing of the integer coding unit of the first to third embodiments (S410). When the coding parameter K is a value between 1 and 2, for example, the rounded integer value may be 2.

≪Decoding device≫
The processing procedure of the decoding method executed by the decoding apparatus 450 of the fourth embodiment will be described with reference to FIGS. 13 and 14. As shown in FIG. 13, the decoding device 450 of the fourth embodiment includes a parameter decoding unit 470 and an integer decoding unit 460. The decoding method of the fourth embodiment is realized by the decoding device 450 of the fourth embodiment executing the processing of each step shown in FIG.

The integer code and the parameter code output by the coding device 400 of the fourth embodiment are input to the decoding device 450 of the fourth embodiment. The integer code and the parameter code input to the decoding device 450 are input to the parameter decoding unit 470 and the integer decoding unit 460 for each code corresponding to the N sample of the integer value series. That is, the decoding device 450 performs the decoding process for each same frame as the coding device 400.

[Parameter decoding unit 470]
The parameter code input to the decoding device 450 is input to the parameter decoding unit 470. The parameter decoding unit 470 decodes the parameter code by the decoding process corresponding to the parameter code obtained by the parameter determination unit 420 to obtain the Rice parameter r and output it (S470). The parameter decoding unit 470 obtains and outputs the quantization value of the Rice parameter r corresponding to the parameter code as the Rice parameter r by, for example, the decoding process corresponding to the scalar quantization performed by the parameter determination unit 420 of the coding device 400. To do.

[Integer decoding unit 460]
The integer code input to the decoding device 450 and the Rice parameter r output by the parameter decoding unit 470 are input to the integer decoding unit 460. When the Rice parameter r is a non-negative value, the integer decoding unit 460 rounds the Rice parameter r into an integer value by the same method as that performed by the integer coding unit 410 of the encoding device 400, and then converts the Rice parameter r into an integer code. On the other hand, Golomb-Rice decoding by the Rice parameter r is performed to obtain an integer sequence x_1, x_2,…, x_N and output. If the Rice parameter r is a negative value, the integer coding unit 410 of the fourth embodiment is obtained. The Rice parameter r is converted to the coding parameter K by the same processing as in the above, that is, ^{the value of K is obtained from the Rice parameter r by K = 2-r} , and the integer coding unit 410 of the coding device 400 performs the process. A coding parameter K is obtained by rounding the value of K to an integer value by the same method as in the above, and using the obtained coding parameter K, any one of the integer decoding units of the first to third embodiments. Integer series x_1, x_2, ..., x_N are obtained and output by the same processing as the processing (S460).

<Modification 1 of the fourth embodiment>
In the fourth embodiment, the coding / decoding process combined with the Golomb-Rice coding / decoding is performed, but it may not be combined with the Golomb-Rice coding / decoding. A form that is not combined with Golomb-Rice coding / decoding will be described as a modification 1 of the fourth embodiment. The operation of the parameter determining unit 421 of the coding device 401 and the parameter decoding unit 471 of the decoding device 451 is the same as that of the fourth embodiment, and the integer coding unit 411 of the coding device 401 and the integer decoding unit 461 of the decoding device 451 The operation is different from the fourth embodiment.

[Integer encoding unit 411]
The integer coding unit 411 contains the integer series x_1, x_2, ..., x_N for each N sample of the integer value series input to the coding device 401, and the Rice parameter r output by the parameter determination unit 421. Entered. When the Rice parameter r is a non-negative value, the integer coding unit 411 uses 2 as the coding parameter K and performs the same processing as any of the processing of the integer coding unit of the first to third embodiments. When the integer code is obtained and output, and the Rice parameter r is a negative value, ^{the value of K is obtained from the Rice parameter r by K = 2 -r, and} the first decimal place of the obtained K value is rounded off. The coded parameter K is obtained by rounding the value of K to an integer value, and the obtained coded parameter K is used to perform the same process as any of the integer coding parts of the first to third embodiments. To obtain an integer code and output it (S411). When the coding parameter K is a value between 1 and 2, for example, the rounded integer value may be 2.

[Integer decoding unit 461]
The integer code input to the decoding device 451 and the Rice parameter r output by the parameter decoding unit 471 are input to the integer decoding unit 461. When the Rice parameter r is a non-negative value, the integer decoding unit 461 uses 2 as the coding parameter K and performs the same processing as any of the processing of the integer decoding unit of the first to third embodiments to perform an integer. When the series x_1, x_2, ..., x_N are obtained and output, and the Rice parameter r is a negative value, the Rice parameter r is converted to the coding parameter K by the same processing as the integer coding unit 410 of the fourth embodiment. That is, the value of K is obtained from the Rice parameter r by K = 2- ^r , and the value of K is rounded to an integer value by the same method as that performed by the integer coding unit 411 of the encoder 401. Then, the coding parameter K is obtained, and the obtained coding parameter K is used to perform the same processing as any of the processing of the integer decoding unit of the first to third embodiments to perform the integer series x_1, x_2, ..., Obtain x_N and output it (S461).

<Modification 2 of the fourth embodiment>
In the fourth embodiment, the integer coding unit 410 has a configuration in which the coding parameter K is obtained from the Rice parameter r when the Rice parameter r has a negative value, but the parameter determining unit 420 has a negative value for the Rice parameter r. In some cases, the coding parameter K may be obtained directly from the integer sequence. This embodiment will be described as a modification 2 of the fourth embodiment, and a portion different from that of the fourth embodiment will be described.

[Parameter determination unit 422]
The parameter determination unit 420 of the fourth embodiment is configured to always output the Rice parameter and the parameter code corresponding to the Rice parameter regardless of the value of the Rice parameter. The parameter determination unit 422 outputs the Rice parameter r and the parameter code corresponding to the Rice parameter r when the Rice parameter r has a non-negative value, and will be described later when the Rice parameter r has a negative value. The coding parameter K is obtained from the integer sequence according to the equation (6), and the coding parameter K and the parameter code corresponding to the coding parameter K are output (S422). At that time, the parameter code may be a code that allows the corresponding decoding device 452 to uniquely identify the value of the Rice parameter r and the value of the coding parameter K. For example, a code obtained by encoding the Rice parameter r with a 1-bit code '1' added to the parameter code is used as a parameter code, and a code obtained by encoding the coding parameter K is preceded by a 1-bit code'. The code group of the parameter code assigned to the Rice parameter r and the code group assigned to the coding parameter K may not include the same code by using the one with 0'as the parameter code.

[Integer encoding unit 412]
The integer coding unit 412 includes an integer series x_1, x_2, ..., x_N for each N sample of the integer value series input to the coding device 402, and the Rice parameter r or the Rice parameter r output by the parameter determination unit 422. The coding parameter K is entered. When the Rice parameter r is input, the integer coding unit 412 rounds the Rice parameter r to an integer value, and Golomb-Rice by the integer value Rice parameter r for the integer series x_1, x_2,…, x_N. Encoding is performed, and the code obtained by Golomb-Rice coding is output as an integer code. When the coding parameter K is input, the coding parameter K is rounded to an integer value and the integer value is encoded. Using the parameter K, an integer code is obtained and output by the same process as any of the processes of the integer coding unit of the first to third embodiments (S412). When the coding parameter K is a value between 1 and 2, for example, the rounded integer value may be 2.

[Parameter decoding unit 472]
The parameter decoding unit 470 of the fourth embodiment decodes the parameter code to obtain the Rice parameter, whereas the parameter decoding unit 472 of the second modification of the fourth embodiment decodes the parameter code to obtain the Rice parameter r. Alternatively, the coding parameter K is obtained and output (S472).

[Integer decoding unit 462]
The integer code input to the decoding device 452 and the Rice parameter r or the coding parameter K output by the parameter decoding unit 472 are input to the integer decoding unit 462. When the Rice parameter r is input, the integer decoding unit 462 rounds the Rice parameter r into an integer value by the same method as that performed by the integer coding unit 412 of the encoding device 402, and then converts the Rice parameter r into an integer code. On the other hand, Golomb-Rice decoding with the integer value Rice parameter r is performed to obtain the integer series x_1, x_2,…, x_N and output, and when the coding parameter K is input, the coding parameter K is encoded. After rounding to an integer value by the same method performed by the integer coding unit 412 of the apparatus 402, the processing of any of the integer decoding units of the first to third embodiments is performed using the integer value coding parameter K. The integer series x_1, x_2, ..., x_N are obtained and output by the same processing as in (S462).

<Fifth Embodiment>
In the coding apparatus of the fourth embodiment, the Rice parameter r was first obtained, and the coding parameter K was obtained from the obtained Rice parameter r. However, the coding parameter K is the distribution p in which the code of the present invention is optimal. By estimating a plausible K for x, 1 / K), it may be estimated directly from the sequence of input integer values. In this case, the Golomb-Rice code can be interpreted as the code of the present invention by K having a value of 1 or less. Therefore, the optimum coding parameter K is directly obtained from the sub-series of the series of input integer values, and the processing of the integer coding unit of the first to third embodiments using the obtained coding parameter K is Golomb. A series of input integer values may be encoded in combination with -Rice coding, or decoding corresponding to this coding may be performed. This embodiment will be described as the fifth embodiment.

≪Coding device≫
The processing procedure of the coding method executed by the coding apparatus 500 of the fifth embodiment will be described with reference to FIGS. 11 and 12. As shown in FIG. 11, the coding device 500 of the fifth embodiment includes a parameter determining unit 520 and an integer coding unit 510. The coding method of the fifth embodiment is realized by the coding device 500 of the fifth embodiment executing the processing of each step shown in FIG.

A series of non-negative integer values is input to the coding device 500 of the fifth embodiment as in the first to fourth embodiments. The sequence of non-negative integer values input to the coding apparatus 500 of the fifth embodiment is input to the parameter determination unit 520 and the integer coding unit 510 for each N samples. That is, the coding device 500 of the fifth embodiment converts a sequence of integer values such as a sequence of absolute values of integer values obtained by converting voice or music picked up by a microphone into a digital signal and quantizing the sequence. Encode frame by frame with N samples.

Hereinafter, the non-negative integer value input to the coding apparatus of the present embodiment will be referred to simply as an “integer value” and will be described.

[Parameter determination unit 520]
The parameter determination unit 520 is input with an integer sequence x_1, x_2, ..., X_N for each N sample of the integer sequence input to the coding apparatus 500. Based on the input integer sequence x_1, x_2, ..., X_N, the parameter determination unit 520 obtains and outputs the coding parameter K corresponding to the integer sequence and the parameter code representing the parameter (S520). ). The parameter code may be obtained by encoding the coding parameter K so that the decoding device 550 can obtain the coding parameter K determined by the parameter determination unit 520 by decoding the parameter code.

The parameter determination unit 520 obtains the coded parameter K by the equation (6) using, for example, each integer value included in the input integer series x_1, x_2, ..., X_N. Find the log-likelihood of the integer series x_1, x_2,…, x_N for the distribution p (x, 1 / K) based on equation (4), and set the coding parameter K that maximizes the log-likelihood as shown in the following equation. Get and output.

The coding parameter K obtained by Eq. (6) maximizes the log-likelihood for the distribution p (x, 1 / K) based on Eq. (4) for the integer series x_1, x_2,…, x_N.

Then, the parameter determination unit 520, for example, scalar-quantizes the coding parameter K obtained by the equation (6) to obtain a code, outputs the obtained code as a parameter code, and outputs a coding parameter corresponding to the parameter code. The quantization value of K is output as the coding parameter K.

[Integer encoding unit 510]
The integer coding unit 510 includes integer series x_1, x_2, ..., x_N for each N sample of the integer value series input to the coding device 500, and the coding parameter K output by the parameter determination unit 520. Is entered. When the coding parameter K is 1 or less, the integer coding unit 510 _{obtains the value of r from the coding parameter K by r = -log 2} K, and obtains the first decimal place of the obtained value of r. The Rice parameter r is obtained by rounding the value of r to an integer value by rounding, etc., and the obtained Rice parameter r is used for the integer series x_1, x_2,…, x_N with respect to the Golomb-Rice by the Rice parameter r. Encoding is performed, and the code obtained by Golomb-Rice coding is output as an integer code. If the coding parameter K is larger than 1, the first decimal place of the coding parameter K is rounded off to K. After rounding the value of to an integer value, an integer code is obtained and output by the same process as any of the processes of the integer coding unit of the first to third embodiments using the integer value coding parameter K (. S510). When the coding parameter K is a value between 1 and 2, for example, the rounded integer value may be 2.

≪Decoding device≫
The processing procedure of the decoding method executed by the decoding apparatus 550 of the fifth embodiment will be described with reference to FIGS. 13 and 14. As shown in FIG. 13, the decoding device 550 of the fifth embodiment includes a parameter decoding unit 570 and an integer decoding unit 560. The decoding method of the fifth embodiment is realized by the decoding device 550 of the fifth embodiment executing the processing of each step shown in FIG.

The integer code and the parameter code output by the coding device 500 of the fifth embodiment are input to the decoding device 550 of the fifth embodiment. The integer code and the parameter code input to the decoding device 550 are input to the parameter decoding unit 570 and the integer decoding unit 560 for each code corresponding to the N sample of the integer value series. That is, the decoding device 550 performs the decoding process for each same frame as the coding device 500.

[Parameter decoding unit 570]
The parameter code input to the decoding device 550 is input to the parameter decoding unit 570. The parameter decoding unit 570 decodes the parameter code by the decoding process corresponding to the parameter determination unit 520 obtaining the parameter code, obtains the coded parameter K, and outputs the code (S570). The parameter decoding unit 570 obtains the quantization value of the coding parameter K corresponding to the parameter code as the coding parameter K by, for example, the decoding process corresponding to the scalar quantization performed by the parameter determining unit 520 of the coding device 500. And output.

[Integer decoding unit 560]
The integer code input to the decoding device 550 and the coding parameter K output by the parameter decoding unit 570 are input to the integer decoding unit 560. When the coding parameter K is 1 or less, the integer decoding unit 560 is obtained by converting the coding parameter K into the Rice parameter r by the same processing as the integer coding unit 510 of the fifth embodiment, that is, The value of r is obtained from the coding parameter K by r = -log ₂ K, and the value of r is rounded to an integer value by the same method as that performed by the integer coding unit 510 of the encoding device 500. Obtain the parameter r, use the obtained Rice parameter r to perform Golomb-Rice decoding with the Rice parameter r for the integer code, obtain the integer series x_1, x_2,…, x_N and output it, and the encoding parameter K is If it is larger than 1, the coding parameter K is rounded to an integer value by the same method used by the integer coding unit 510 of the coding device 500, and then the integer value coding parameter K is used. The integer series x_1, x_2, ..., X_N are obtained and output by the same processing as any of the processing of the integer decoding unit of the first to third embodiments (S560).

<Modification 1 of the fifth embodiment>
In the fifth embodiment, the coding / decoding process combined with the Golomb-Rice coding / decoding is performed, but it may not be combined with the Golomb-Rice coding / decoding. A form that is not combined with Golomb-Rice coding / decoding will be described as a modification 1 of the fifth embodiment. The operation of the parameter determining unit 521 of the coding device 501 and the parameter decoding unit 571 of the decoding device 551 is the same as that of the fifth embodiment, and the integer coding unit 511 of the coding device 501 and the integer decoding unit 561 of the decoding device 551 The operation is different from the fifth embodiment.

[Integer encoding unit 511]
The integer coding unit 511 includes an integer series x_1, x_2, ..., X_N for each N sample of the integer value series input to the coding device 501, and a coding parameter K output by the parameter determination unit 521. Is entered. The integer coding unit 511 rounds the value of K to an integer value by rounding off the first decimal place of the input coding parameter K, and then rounds the value to an integer value, and then the integer value coding parameter K is 1 or less. Uses 2 as the coding parameter K to obtain and output an integer code by the same processing as any of the processing of the integer coding unit of the first to third embodiments, and the integer value coding parameter K is 1. If it is larger than, an integer code is obtained and output by the same process as any of the processes of the integer coding unit of the first to third embodiments using the integer value coding parameter K (S511).

[Integer decoding unit 561]
The integer code input to the decoding device 551 and the coding parameter K output by the parameter decoding unit 571 are input to the integer decoding unit 561. The integer decoding unit 561 rounds the input coding parameter K into an integer value by the same method as that performed by the integer coding unit 511 of the encoding device 501, and then the integer value coding parameter K is 1 or less. If, 2 is used as the coding parameter K, and the integer series x_1, x_2, ..., x_N are obtained and output by the same processing as any of the processing of the integer decoding unit of the first to third embodiments. , When the integer value coding parameter K is larger than 1, the integer series x_1 is performed by the same processing as any of the processing of the integer decoding unit of the first to third embodiments using the integer value coding parameter K. , X_2,…, x_N are obtained and output (S561).

<Modification 2 of the fifth embodiment>
In the fifth embodiment, the integer coding unit 510 has a configuration in which the Rice parameter r is obtained from the coding parameter K when the coding parameter K is 1 or less, but the parameter determination unit 520 has a coding parameter K of 1 or less. In the case of, the Rice parameter r may be obtained directly from the integer sequence. This form will be described as a modification 2 of the fifth embodiment, and a part different from the fifth embodiment will be described.

[Parameter determination unit 522]
The parameter determination unit 520 of the fifth embodiment is configured to always output the coding parameter K and the parameter code corresponding to the coding parameter K regardless of the value of the coding parameter K. When the coding parameter K is larger than 1, the parameter determination unit 522 of the modified example 2 of the form outputs the coding parameter K and the parameter code corresponding to the coding parameter K, and the coding parameter K becomes If it is 1 or less, the Rice parameter r is obtained from the integer sequence by the equation (5), and the Rice parameter r and the parameter code corresponding to the Rice parameter r are output (S522). At that time, as in the modified example 2 of the fourth embodiment, the parameter code may be a code that allows the corresponding decoding device 552 to uniquely identify the value of the Rice parameter r and the value of the coding parameter K.

[Integer encoding unit 512]
The integer coding unit 512 includes integer series x_1, x_2, ..., x_N for each N sample of the series of integer values input to the coding device 502, and the coding parameter K output by the parameter determination unit 522. Alternatively, the Rice parameter r is entered. When the Rice parameter r is input, the integer coding unit 512 rounds the value of the Rice parameter r to an integer value, and then sets the Rice parameter r as an integer value for the integer series x_1, x_2,…, x_N. Golomb-Rice coding by Golomb-Rice is performed, the code obtained by Golomb-Rice coding is output as an integer code, and when the coding parameter K is input, the coding parameter K is rounded to an integer value. , An integer code is obtained and output by the same process as any of the processes of the integer coding unit of the first to third embodiments using the integer value coding parameter K (S512). When the coding parameter K is a value between 1 and 2, for example, the rounded integer value may be 2.

[Parameter decoding unit 572]
The parameter decoding unit 570 of the fifth embodiment decodes the parameter code to obtain the coded parameter K, whereas the parameter decoding unit 572 of the second modification of the fifth embodiment decodes the parameter code and encodes the code. The conversion parameter K or the Rice parameter r is obtained and output (S572).

[Integer decoding unit 562]
The integer code input to the decoding device 552 and the coding parameter K or Rice parameter r output by the parameter decoding unit 572 are input to the integer decoding unit 562. When the Rice parameter r is input, the integer decoding unit 562 rounds the value of the Rice parameter r into an integer value by the same method as that performed by the integer coding unit 512 of the encoding device 502, and converts it into an integer code. On the other hand, Golomb-Rice decoding with the integer value Rice parameter r is performed to obtain the integer series x_1, x_2,…, x_N and output, and when the coding parameter K is input, the coding parameter K is encoded. After rounding to an integer value by the same method performed by the integer coding unit 512 of the apparatus 502, the processing of any of the integer decoding units of the first to third embodiments is performed using the integer value coding parameter K. The integer series x_1, x_2, ..., x_N are obtained and output by the same processing as in (S562).

<Other variants of the fourth embodiment and the fifth embodiment>
Since the Rice parameter r and the coding parameter K ^{can be converted to each other by K = 2 -r} and r = -log ₂ K, the integer coding unit of the coding device and the integer decoding of the decoding device If it is possible to use the same value of the same parameter in the unit, which parameter is to be encoded / decoded may be used in any combination of the above conversions. Also, if the integer coding unit of the coding device and the integer decoding unit of the decoding device can use the same value of the same parameter, either the value of the Rice parameter r or the value of the coding parameter K should be the target of the rounding process. Either the value before or after the coding of the parameter (that is, before and after the quantization) may be the target of the rounding process, or the value quantization and the rounding process in the coding may be performed at the same time. In short, the fourth and fifth embodiments and their modified examples 1 and 2 are merely examples, and the integer coding unit and the decoding apparatus of the encoding device are described for each frame by N samples. It suffices to enable the integer decoding unit of the above to perform the coding process and the decoding process using the same values of the same parameters.

<Sixth Embodiment>
In the fourth embodiment and the fifth embodiment, the Rice parameter r or the coding parameter K obtained for the sub-series of the series by the input integer value is used to code the first to third embodiments. A mode for realizing the coding and decoding of the present invention by decoding has been described. In the sixth embodiment, a mode for realizing the coding and decoding of the present invention will be described using at least one of the Rice parameter r and the coding parameter K.

≪Coding device≫
The processing procedure of the coding method executed by the coding apparatus 600 of the sixth embodiment will be described with reference to FIGS. 11 and 12. As shown in FIG. 11, the coding device 600 of the sixth embodiment includes a parameter determining unit 620 and an integer coding unit 610, similar to the coding device 400 and the coding device 500. Similar to the coding device 400 and the coding device 500, the coding device 600 of the sixth embodiment executes the processing of each step shown in FIG. 12, so that the coding method of the sixth embodiment is realized.

Similar to the coding device 400 and the coding device 500, a sequence of non-negative integer values is input to the coding device 600 of the sixth embodiment. The sequence of non-negative integer values input to the coding apparatus 600 of the sixth embodiment is input to the parameter determination unit 620 and the integer coding unit 610 for each N samples.

Hereinafter, the non-negative integer value input to the coding apparatus of the present embodiment will be referred to simply as an “integer value” and will be described.

[Parameter determination unit 620]
The parameter determination unit 620 is input with an integer sequence x_1, x_2, ..., X_N for each N sample of the integer value sequence input to the encoding device 600. Based on the input integer sequence x_1, x_2, ..., X_N, the parameter determination unit 620 includes at least one of the Rice parameter r and the coding parameter K corresponding to the integer sequence, and the Rice parameter r and the coding parameter K. A parameter code representing at least one of them is obtained and output (S620). That is, the parameter determination unit 620 uses the equation (5) for each integer series, which is a series of integer values for each predetermined sample included in the series of input non-negative integer values, based on the integer values included in the integer series. At least one of the process of obtaining the rice parameter r and the process of obtaining the coded parameter K by the equation (6) based on the integer value included in the integer series, and at least one of the rice parameter r and the coded parameter K. The process of encoding and obtaining the parameter code is performed.

[Integer encoding unit 610]
The integer coding unit 610 includes integer series x_1, x_2, ..., x_N for each N sample of the series of integer values input to the coding device 600, and Rice parameter r output by the parameter determination unit 620. At least one of the coding parameters K is entered. When the coding parameter K is input, the integer coding unit 610 performs Golomb-Rice coding as in the fifth embodiment if the coding parameter K is 1 or less, and performs Golomb-Rice coding. If the code obtained by the conversion is output as an integer code and the coding parameter K is larger than 1, the same processing as any processing of the integer coding unit of the first to third embodiments is performed as in the fifth embodiment. When an integer code is obtained and output, and the Rice parameter r is input, if the Rice parameter r is a non-negative value, Golomb-Rice coding is performed and the Golomb-Rice code is performed as in the fourth embodiment. If the code obtained by the conversion is output as an integer code and the Rice parameter r is a negative value, the same processing as in any of the integer coding parts of the first to third embodiments is performed as in the fourth embodiment. An integer code is obtained and output (S610). That is, the integer coding unit 610 receives the coding parameter K obtained by the parameter determination unit 620 or the Rice parameter r obtained by the parameter determination unit 620 for each integer series which is a series of integer values for each predetermined sample. The code of the code A or the code B is obtained by using the coded parameter K obtained by = 2 ^{-r as the coded parameter K.} In particular, when the coding parameter K corresponding to the integer series is 1 or less, or when the Rice parameter r corresponding to the integer series is non-negative, the integer series is Golomb-Rice encoded to obtain a code string. You may do so.

≪Decoding device≫
The processing procedure of the decoding method executed by the decoding apparatus 650 of the sixth embodiment will be described with reference to FIGS. 13 and 14. As shown in FIG. 13, the decoding device 650 of the sixth embodiment includes a parameter decoding unit 670 and an integer decoding unit 660, similar to the decoding device 450 and the decoding device 550. The decoding method of the sixth embodiment is realized by the decoding device 650 of the sixth embodiment executing the processing of each step shown in FIG. 14, similarly to the decoding device 450 and the decoding device 550.

The integer code and the parameter code output by the coding device 600 of the sixth embodiment are input to the decoding device 650 of the sixth embodiment. The integer code and the parameter code input to the decoding device 650 are input to the parameter decoding unit 670 and the integer decoding unit 660 for each code corresponding to the N sample of the integer value series. That is, the parameter code and the code string for each predetermined unit are input to the parameter decoding unit 670 and the integer decoding unit 660.

[Parameter decoding unit 670]
The parameter decoding unit 670 decodes the parameter code by the decoding process corresponding to the parameter code obtained by the parameter determination unit 620, obtains at least one of the Rice parameter r and the coding parameter K, and outputs the result (S670). .. That is, the parameter decoding unit 670 decodes the parameter code for each predetermined unit to obtain at least one of the Rice parameter r and the coding parameter K.

[Integer decoding unit 660]
At least one of the integer code input to the decoding device 650, the Rice parameter r output by the parameter decoding unit 670, and the coding parameter K is input to the integer decoding unit 660. When the coding parameter K is input, the integer decoding unit 660 performs Golomb-Rice decoding as in the fifth embodiment if the coding parameter K is 1 or less, and performs integer series x_1, x_2, ... , X_N is obtained and output, and if the coding parameter K is larger than 1, the integer sequence x_1, is processed in the same manner as in any of the integer decoding units of the first to third embodiments as in the fifth embodiment. When x_2,…, x_N is obtained and output, and the Rice parameter r is input, if the Rice parameter r is a non-negative value, Golomb-Rice decoding is performed and the integer series x_1, If x_2,…, x_N are obtained and output, and the Rice parameter r is a negative value, an integer is processed by the same processing as any of the integer decoding units of the first to third embodiments as in the fourth embodiment. The series x_1, x_2, ..., x_N are obtained and output (S660). In other words, the integer decoding part 660, for each predetermined unit, the coding parameter K parameter decoding section 670 to obtain or a coding parameter K from Rice parameter r to parameter decoding section 670 was obtained was obtained by K = 2 ^-r , Is used as the coding parameter K, and 2 to 2 ^K-1 consecutive integer values of 0, or 0 to 2 ^{K-1 to} 1 consecutive integer values 0 and 1 non-zero integer value x_n Obtain a series of integer values consisting of a set of. In particular, when the coding parameter K is 1 or less, or when the Rice parameter r is non-negative, the code string may be Golomb-Rice decoded to obtain a sequence of integer values.

According to the invention of the present embodiment, if the value corresponding to the Rice parameter r corresponding to the sequence or subseries of integer values is known, the code can be coded with a small average number of bits by using the coding parameter K optimal for the sequence. Can be transformed into. Moreover, such a code can be decoded.

<Supplement>
The device of the present invention is, for example, as a single hardware entity, an input unit to which a keyboard or the like can be connected, an output unit to which a liquid crystal display or the like can be connected, and a communication device (for example, a communication cable) capable of communicating outside the hardware entity. Communication unit to which can be connected, CPU (Central Processing Unit, cache memory, registers, etc.), RAM and ROM as memory, external storage device as hard hardware, and input, output, and communication units of these , CPU, RAM, ROM, and has a connecting bus so that data can be exchanged between external storage devices. Further, if necessary, a device (drive) or the like capable of reading and writing a recording medium such as a CD-ROM may be provided in the hardware entity. A physical entity equipped with such hardware resources includes a general-purpose computer and the like.

The external storage device of the hardware entity stores the program required to realize the above-mentioned functions and the data required for processing this program (not limited to the external storage device, for example, reading a program). It may be stored in a ROM, which is a dedicated storage device). Further, the data obtained by the processing of these programs is appropriately stored in a RAM, an external storage device, or the like.

In the hardware entity, each program stored in the external storage device (or ROM, etc.) and the data necessary for processing each program are read into the memory as needed, and are appropriately interpreted, executed, and processed by the CPU. .. As a result, the CPU realizes a predetermined function (each configuration requirement represented by the above, ... Department, ... means, etc.).

The present invention is not limited to the above-described embodiment, and can be appropriately modified without departing from the spirit of the present invention. Further, the processes described in the above-described embodiment are not only executed in chronological order according to the order described, but may also be executed in parallel or individually depending on the processing capacity of the device that executes the processes or if necessary. ..

As described above, when the processing function in the hardware entity (device of the present invention) described in the above embodiment is realized by a computer, the processing content of the function that the hardware entity should have is described by a program. Then, by executing this program on the computer, the processing function in the above hardware entity is realized on the computer.

The program describing the processing content can be recorded on a computer-readable recording medium. The computer-readable recording medium may be, for example, a magnetic recording device, an optical disk, a photomagnetic recording medium, a semiconductor memory, or the like. Specifically, for example, a hard disk device, a flexible disk, a magnetic tape, or the like as a magnetic recording device is used as an optical disk, and a DVD (Digital Versatile Disc), a DVD-RAM (Random Access Memory), or a CD-ROM (Compact Disc Read Only) is used as an optical disk. Memory), CD-R (Recordable) / RW (ReWritable), etc., MO (Magneto-Optical disc), etc. as a magneto-optical recording medium, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory), etc. as a semiconductor memory Can be used.

Further, the distribution of this program is performed, for example, by selling, transferring, renting, or the like a portable recording medium such as a DVD or a CD-ROM in which the program is recorded. Further, the program may be stored in the storage device of the server computer, and the program may be distributed by transferring the program from the server computer to another computer via a network.

A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. Then, when the process is executed, the computer reads the program stored in its own recording medium and executes the process according to the read program. Further, as another execution form of this program, a computer may read the program directly from a portable recording medium and execute processing according to the program, and further, the program is transferred from the server computer to this computer. Each time, the processing according to the received program may be executed sequentially. In addition, the above processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition without transferring the program from the server computer to this computer. May be. The program in this embodiment includes information to be used for processing by a computer and equivalent to the program (data that is not a direct command to the computer but has a property of defining the processing of the computer, etc.).

Further, in this form, the hardware entity is configured by executing a predetermined program on the computer, but at least a part of these processing contents may be realized in terms of hardware.

The description of the embodiment of the present invention described above is presented for purposes of illustration and description. There is no intention to be exhaustive and no intention to limit the invention to the exact form disclosed. Deformations and variations are possible from the above teachings. The embodiments are in various embodiments and in various ways to provide the best illustration of the principles of the invention and to be suitable for practical use by those skilled in the art. It is selected and expressed so that it can be used by adding transformations. All such variations and variations are within the scope of the invention as defined by the appended claims, interpreted according to the width given fairly, legally and impartially.

Claims (15)

Non negative integer value x_n, n∈ {1, 2, ..., N} sequence by (hereinafter referred to as "integral sequence") as input, codes in a predetermined order to each integer value included in the integer sequence It is a coding device that obtains a code string and outputs it .
Let K be an integer greater than or equal to 2
When the partial series of integer values in the predetermined order is a series of L pieces, which is any number of predetermined numbers from 2 to 2 ^K-1 pieces of integer value 0, the L pieces. A 1-bit code (hereinafter referred to as "code A") is obtained as a code corresponding to the continuation of.
If the partial series of integer values in the predetermined order is a set consisting of 0 to L-1 consecutive integer values 0 and one non-zero integer value x_n, the set is included. The process of obtaining a code of K × x_n bits or K × x_n + 1 bits (hereinafter referred to as “code B”) as the corresponding code,
A coding device including an integer coding unit that performs until the Nth integer value in the predetermined order is processed, and outputs a concatenated code obtained as the code string. The coding device according to claim 1.
The bit value “x” is the bit value “1” and the bit value “y” is the bit value “0”, or the bit value “x” is the bit value “0” and the bit value “y” is the bit value. As "1",
The reference numeral A is a 1-bit code having a bit value of “x”.
The reference numeral B includes at least one bit value “x” and at least one bit value “y” from the first bit to the Kth bit, and the K × (x_n-1) bit from the end has a bit value. Encoding device that is “y”. The coding device according to claim 2.
L is 2 ^K-1
Each zero or an integer value 0 for 2 ^K-1 -1 single 2 ^K-1 kinds of continuous number in the integer sequence,
When the code B is K × x_n + 1 bits,
It is composed of K + 1 bits from the 1st bit to the K + 1th bit of the code B, the bit value of the 1st bit is "x", and the bit value from the 2nd bit to the K + 1th bit is. One subcode that is "y" and
When the code B is K × x_n bits,
It is composed of K bits from the 1st bit to the K bit of the code B, the bit value of the 1st bit is "y", and at least 1 bit in the K-1 bits from the 2nd bit to the K bit. ^{2 K-1} -1 subcodes with a bit value of “x” and
A coding device that has a one-to-one correspondence with any of the 2 ^{K-1 partial codes in.} A sequence of non-negative integer values is input, and each sequence of non-negative integer values x_n, n ∈ {1, 2, ..., N} (hereinafter referred to as "integer series"), which is a predetermined unit by N samples, is coded. It is a coding device to be converted
The coding device encodes each integer value included in the integer series in a predetermined order to obtain a code string and outputs the code string.
For each of the integer series
When the partial series of integer values in the predetermined order is a series of L pieces, which is any number of predetermined ^{numbers from 2 to 2 K-1 pieces of integer value 0, the L pieces.} A 1-bit code (hereinafter referred to as "code A") is obtained as a code corresponding to the continuation of.
If the partial series of integer values in the predetermined order is a set consisting of 0 to L-1 consecutive integer values 0 and one non-zero integer value x_n, the set is included. The process of obtaining a code of K × x_n bits or K × x_n + 1 bits (hereinafter referred to as “code B”) as the corresponding code,
It includes an integer coding unit that performs until the Nth integer value in the predetermined order is processed and outputs a concatenated code obtained as the code string.
For each of the integer series
The process of obtaining the rice parameter r by the following equation based on the integer value included in the integer series, and

At least one of the processing of obtaining the coding parameter K'by the following equation based on the integer value included in the integer series, and

A process of obtaining the parameter code by encoding at least one of Rice parameter r and the coding parameter K ',
Including a parameter determination unit that performs
Code the integer encoding unit, for each of the integer sequence, the parameter determination unit is obtained coding parameters K ', or, wherein the parameter determining unit K from the Rice parameter r obtained' was obtained by = 2 ^-r parameter K ', the coding device using a value to an integer value as the K crumpled. The coding device according to claim 4.
The integer coding unit is the integer sequence when the coding parameter K'corresponding to the integer sequence is 1 or less, or when the rice parameter r corresponding to the integer sequence is non-negative. A coding device that obtains a code string by coding Goromulais. A decoding device that takes a code string as an input, decodes the codes contained in the code string in order, obtains a sequence with integer values x_n, n ∈ {1, 2, ..., N} and outputs it .
Let K be an integer greater than or equal to 2
When the code included in the code string is a 1-bit code (hereinafter referred to as "code A"), it is predetermined from 2 to 2 ^K-1 integer values 0 corresponding to the code A. Obtain any number of L consecutive pieces,
When the code contained in the code string is a code of K × x_n bits or K × x_n + 1 bits (hereinafter referred to as “code B”), 0 to L-1 corresponding to the code B. The process of obtaining a pair of consecutive integer values 0 and one non-zero integer value x_n,
A decoding device including an integer decoding unit that performs until there are no more codes included in the code string and outputs a series of obtained integer values as a series of the integer values x_n. The decoding device according to claim 6.
The bit value “x” is the bit value “1” and the bit value “y” is the bit value “0”, or the bit value “x” is the bit value “0” and the bit value “y” is the bit value. As "1",
The reference numeral A is a 1-bit code having a bit value of “x”.
The reference numeral B includes at least one bit value “x” and at least one bit value “y” from the first bit to the Kth bit, and the K × (x_n-1) bit from the end has a bit value. Decryptor that is “y”. The decoding device according to claim 6 or 7.
The integer decoding unit is in order from the beginning of the input code string.
Reading the input code string one by one consecutive K bits (hereinafter referred to as "K bit string")
When the read K bit string contains "y", it is identified that the bit immediately preceding the K bit string containing "y" is the terminal bit of the code A or the code B.
By doing
A decoding device that identifies the code A and the code B included in the input code string. The decoding device according to claim 7 or 8.
L is 2 ^K-1
When the code B is K × x_n + 1 bits,
It is composed of K + 1 bits from the 1st bit to the K + 1th bit of the code B, the bit value of the 1st bit is "x", and the bit value from the 2nd bit to the K + 1th bit is. One subcode that is "y" and
When the code B is K × x_n bits,
It is composed of K bits from the 1st bit to the K bit of the code B, the bit value of the 1st bit is "y", and at least 1 bit in the K-1 bits from the 2nd bit to the K bit. ^{2 K-1} -1 subcodes with a bit value of “x” and
Each of the 2 ^K-1 subcodes in
Decoding apparatus corresponding to the one-to-one with any of the number of consecutive 2 ^K-1 kinds from 0 2 ^K-1 -1 single integer value 0 in the sequence by an integer value obtained by the integral decoder. Decoding that takes the parameter code and code string for each predetermined unit as input, decodes the codes included in the code string in order, obtains a series with integer values x_n, n ∈ {1, 2, ..., N} and outputs it. It ’s a device,
For each predetermined unit,
When the code included in the code string is a 1-bit code (hereinafter referred to as "code A"), it is predetermined ^{from 2 to 2 K-1 integer values 0 corresponding to the code A.} Obtain any number of L consecutive pieces,
When the code contained in the code string is a code of K × x_n bits or K × x_n + 1 bits (hereinafter referred to as “code B”), 0 to L-1 corresponding to the code B. The process of obtaining a pair of consecutive integer values 0 and one non-zero integer value x_n,
It includes an integer decoding unit that performs until there are no more codes included in the code string and outputs the obtained sequence of integer values as a series of the integer values x_n.
Each predetermined unit further includes a parameter decoding unit that decodes the parameter code to obtain at least one of the rice parameter r and the coding parameter K'.
The integer decoding part, for each predetermined unit, the parameter decoding section obtained coding parameters K ', or, wherein the parameter decoding section K from the Rice parameter r obtained' coding parameters obtained by = 2 ^-r A decoding device that uses the value obtained by rounding K' , as an integer value, as the above K. The decoding device according to claim 10.
When the coding parameter K'is 1 or less, or when the rice parameter r is non-negative, the integer decoding unit decodes the code string by Golomulais to obtain a sequence of integer values. .. Encoding apparatus, non-negative integer value x_n, n∈ {1, 2, ..., N} by sequence (hereinafter, referred to as "integral sequence") as inputs, each integer value included in the integer sequence It is a coding method that encodes in a predetermined order to obtain a code string and outputs it .
Let K be an integer greater than or equal to 2
When the partial series of integer values in the predetermined order is a series of L pieces, which is any number of predetermined numbers from 2 to 2 ^K-1 pieces of integer value 0, the L pieces. A 1-bit code (hereinafter referred to as "code A") is obtained as a code corresponding to the continuation of.
If the partial series of integer values in the predetermined order is a set consisting of 0 to L-1 consecutive integer values 0 and one non-zero integer value x_n, the set is included. The process of obtaining a code of K × x_n bits or K × x_n + 1 bits (hereinafter referred to as “code B”) as the corresponding code,
A coding method that executes an integer coding step in which the Nth integer value in the predetermined order is processed, and the obtained codes are concatenated and output as the code string. A decoding method in which a decoding device takes a code string as an input, decodes the codes contained in the code string in order, obtains a sequence of integer values x_n, n ∈ {1, 2, ..., N} and outputs the sequence. And
Let K be an integer greater than or equal to 2
When the code included in the code string is a 1-bit code (hereinafter referred to as "code A"), it is predetermined from 2 to 2 ^K-1 integer values 0 corresponding to the code A. Obtain any number of L consecutive pieces,
When the code contained in the code string is a code of K × x_n bits or K × x_n + 1 bits (hereinafter referred to as “code B”), 0 to L-1 corresponding to the code B. The process of obtaining a pair of consecutive integer values 0 and one non-zero integer value x_n,
Decoding method for performing integer decoding step of outputting is performed until the code is no longer included in the code sequence, a sequence according to obtain integer value as a sequence by the integer value x_n. A coding program for operating a computer as the coding device according to any one of claims 1 to 5. A decoding program for operating a computer as the decoding device according to any one of claims 6 to 11.

Images