CN103326731B - A kind of Hidden Markov correlated source coded method encoded based on distributed arithmetic - Google Patents

Abstract

The invention discloses a method for encoding hidden Markov correlation information sources based on distributed arithmetic coding, which comprises the following steps: generating information sources; encoding hidden Markov correlation information sources; and decoding by forward algorithm. The present invention uses DAC to compress the information source related to memory, in specific implementation, the correlation between information sources is modeled as a Hidden Markov process, experimental result shows, the executive result of new scheme is close to Si Li- The boundary of Wooff theory better solves the existing SWC technology based on entropy coding. After overlapping regions, there will be ambiguous codewords and SWC symmetry problems at the decoding end. The present invention preferably utilizes the existing technology, has good experimental effect and has good application value.

Description

A Hidden Markov Correlation Source Coding Method Based on Distributed Arithmetic Coding

technical field

The invention belongs to the field of distributed arithmetic coding, in particular to a hidden Markov correlation information source coding method based on distributed arithmetic coding.

Background technique

Distributed Arithmetic Coding (DAC) can be effectively applied to Slipper-Wooffer coding, especially for short data blocks. Recently, some SWC technologies based on entropy coding have been proposed, such as Distributed Arithmetic Coding (DAC) and Overlapped Quasi-Arithmetic (OQAC), which can be regarded as classical arithmetic coding (Arithmetic Coding) The principle of the extension of AC) is to allow the overlapping of the code rate probability intervals to realize the encoding of the source X under the condition that the code rate H(X|Y)≤R<H(x). The introduction of overlapping regions results in a larger final interval and a shorter codeword. However, at the same time there will be ambiguous codewords at the decoding end. A soft-connected decoder utilizes side information Y to decode X. Afterwards, the researchers proposed a time-shared DAC (time-shared DAC, TS-DAC) to solve the symmetric SWC problem. In order to realize the rate-incremental SWC, the researchers proposed a rate-adaptive DAC.

Contents of the invention

The present invention provides a hidden Markov correlation source coding method based on distributed arithmetic coding, which aims to solve the existing SWC technology based on entropy coding. After overlapping regions, there will be ambiguous codewords and SWC symmetry at the decoding end The problem.

The object of the present invention is to provide a kind of hidden Markov correlation information source coding method based on distributed arithmetic coding, described hidden Markov correlation information source coding method based on distributed arithmetic coding comprises the following steps:

generate a source;

Encoding hidden Markov correlation sources;

Decoding with forward algorithm.

Further, the steps of generating a source of information are:

Read the HMM file and determine the hidden Markov model;

Apply the hidden Markov model to calculate the observation sequence O;

According to the deviation probability p, generate the source X;

The XOR operation is performed on the information source X and the observation value sequence O to generate side information Y.

Further, the described step of coding the Hidden Markov Correlation Information Source is:

Let p be the bias probability of the binary source X, that is, p=P(x _t =1), in classical arithmetic coding, the source symbol x _t is iteratively mapped to the subinterval of [0, 1), The length of this subinterval is proportional to (1-p) and p. In distributed arithmetic coding, the allocated subintervals will overlap, that is, the symbols x _t =0 and x _t =1 correspond to the interval [0, ( 1-p) ^γ ) and [1-p ^γ , 1), define low and high to represent the coding interval, range represents the length of the entire interval, half_range represents half of the interval, first_quarter represents a quarter of the entire interval, third_quarter represents the entire Three-quarters the size of the interval.

Further, the encoding of the hidden Markov correlation source also includes a specific interval amplification operation

When high<half_range, the sub-interval is completely in the upper half of the range, the most significant bits of the upper and lower endpoints of the range are both 0, and the same most significant bit 0 is output, and then the upper and lower bounds of the interval are respectively enlarged by 2 times , namely: low=2*low, high=2*high;

When low>half_range, the sub-interval is completely in the lower half of the range, and the most significant bits of the upper and lower endpoints of the range are both 1. At this time, the same most significant bit 1 is output, and then the upper and lower bounds of the interval are respectively expanded. Namely: low=2*(low-half_range), high=2*(high-half_range);

When first_quarter≤low≤high≤third_quarter, if the low and high are still updated according to the above method, since the sub-interval keeps shrinking, the sub-interval will always be in the interval of first_quarter≤low≤high≤third_quarter, and there will never be The same highest bit can be output, so in this case, a new method is used to update the sub-interval: low=2*(low-first_quarter), high=2*(high-first_quarter)+1.

Further, the decoding steps carried out by using the forward algorithm are:

Define a structure node, the structure includes low, high, which is used to represent the probability interval, metric is used to represent the importance of each branch, that is, the sum of the metrics of each node in the branch, and alpha is used to record the local probability α _t (i) , path is used to save the decoded characters, and an array scale[2] is also defined, where scale[0] indicates the total probability that the position symbol corresponding to the side information is 0 when the current decoding symbol is 0 or 1, scale[0]=alpha [0][0]+alpha[0][1]; scale[1] indicates the total probability that the position symbol corresponding to the side information is 1 when the current decoding symbol is 0 or 1, scale[1]=alpha[1][ 0]+alpha[1][1];

Step 1. According to the length N of the original source X, allocate the node space required for decoding, and initialize the decoding buffer of the distributed arithmetic code;

Step 2. During the ith decoding process (0<i≤N), read the character s _i at the current position of the side information,

Step 3. Use the forward algorithm to calculate the probability of branch 0 and branch 1 for each node when it is decoded for the i-th time. When i=1, that is, when the state is at the initial moment, the local probability is calculated using the formula a ₁ (i )=π _i b _i (z ₁ ) to calculate and record with alpha array, when i>1, the local probability is calculated by the formula Calculation, the variable α _t-1 (j) in the formula is obtained from the structure node, and after each calculation, alpha[0], alpha[1], scale[0] and scale[1], scale of this iteration are obtained [0] indicates that when the current decoding symbol is 0 or 1, the total probability that the corresponding position symbol of the side information is 0, scale[0]=alpha[0][0]+alpha[0][1]; scale[1] indicates When the current decoding symbol is 0 or 1, the total probability of side information corresponding to the position symbol being 1, scale[1]=alpha[1][0]+alpha[1][1];

Step 4: Calculate the i-th decoded symbol c _i , if the code word does not fall in the overlapping area, write the current symbol into node.path, and perform XOR operation on the decoded symbol c _i and the side information s _i , The measure of the current point is the sum of the probabilities of all paths to the point To represent, that is, scale[0] or scale[1], if the side information is the same as the current decoding symbol, The metric of the current point is represented by scale[0]. If the side information is different from the current decoding symbol, it is represented by scale[1], and the local alpha in the node is updated as Update the importance of the entire branch, for the kth branch, If the codeword falls in the overlapping area, two branches m and n are generated. At this time, node[m].metric represents the measurement of the same branch as the side information, that is, when the side information is 1, node[m] .metric represents the measurement of branch 1. When the side information is 0, node[m].metric represents the measurement of branch 0, while node[n].metric is the opposite, representing the measurement of the branch opposite to the side information. For m branch , the stored sign is the same as the side information, at this time Therefore, the overall importance of the m branch is represented by node[m].metric+=log(scale[0]), that is, the product of the scale values of all current points on the m branch, and the overall importance of the n branch is represented by node[n ].metric+=log(scale[1]) means, that is, the product of the scale values of all current points on the n branch, and update the node[m].alpha in the original node point with the new probability alpha[0], and use the new alpha [1] Update node[n].alpha in the original node point;

Step 5. Since a new decoding interval will be generated after decoding once, after calculating the branch metric and updating the local probability, the probability interval and related information must be updated;

Step 6. Sort all branches according to the metric value from large to small. If the number of branches is greater than the threshold M we set, cut off the redundant branches. If i<N, return to step 2; otherwise, the decoding ends , take the data saved in the path in the first branch after branch sorting as the decoding output.

The present invention uses DAC to compress the information sources related to memory, and in the specific implementation, the correlation between information sources is modeled as a hidden Markov process, and the experimental results show that the execution result of the new scheme is close to that of Si Li- The boundary of Wooff theory better solves the existing SWC technology based on entropy coding. After overlapping regions, there will be ambiguous codewords and SWC symmetry problems at the decoding end. The present invention preferably utilizes the existing technology, has good experimental effect and has good application value.

Description of drawings

Fig. 1 is the flowchart of the hidden Markov correlation information source coding method based on distributed arithmetic coding provided by the present invention;

Fig. 2 is a schematic diagram of a decoding tree based on distributed arithmetic coding provided by the present invention.

detailed description

In order to make the purpose, technical solution and advantages of the present invention more clear, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the invention.

FIG. 1 shows the implementation flow of the distributed arithmetic coding-based hidden Markov correlation information source coding method provided by the embodiment of the present invention. For ease of illustration, only the parts relevant to the present invention are shown.

The Hidden Markov Correlation Source Coding method based on Distributed Arithmetic Coding of the present invention comprises the following steps:

generate a source;

Encoding hidden Markov correlation sources;

Decoding with forward algorithm.

As an optimization scheme of the embodiment of the present invention, the steps of generating the information source are:

Read the HMM file and determine the hidden Markov model;

Apply the hidden Markov model to calculate the observation sequence O;

According to the deviation probability p, generate the source X;

The XOR operation is performed on the information source X and the observation value sequence O to generate side information Y.

As an optimization scheme of the embodiment of the present invention, the encoding steps of hidden Markov correlation sources are as follows:

Let p be the bias probability of the binary source X, that is, p=P(x _t =1), in classical arithmetic coding, the source symbol x _t is iteratively mapped to the subinterval of [0, 1), The length of this subinterval is proportional to (1-p) and p. In distributed arithmetic coding, the allocated subintervals will overlap, that is, the symbols x _t =0 and x _t =1 correspond to the interval [0, ( 1-p) ^γ ) and [1-p ^γ , 1), define low and high to represent the coding interval, range represents the length of the entire interval, half_range represents half of the interval, first_quarter represents a quarter of the entire interval, third_quarter represents the entire Three-quarters the size of the interval.

As an optimization scheme of the embodiment of the present invention, the hidden Markov correlation source coding also includes a specific interval amplification operation

When high<half_range, the sub-interval is completely in the upper half of the range, the most significant bits of the upper and lower endpoints of the range are both 0, and the same most significant bit 0 is output, and then the upper and lower bounds of the interval are respectively enlarged by 2 times , namely: low=2*low, high=2*high;

When low>half_range, the sub-interval is completely in the lower half of the range, and the most significant bits of the upper and lower endpoints of the range are both 1. At this time, the same most significant bit 1 is output, and then the upper and lower bounds of the interval are respectively expanded. Namely: low=2*(low-half_range), high=2*(high-half_range);

When first_quarter≤low≤high≤third_quarter, if the low and high are still updated according to the above method, since the sub-interval keeps shrinking, the sub-interval will always be in the interval of first_quarter≤low≤high≤third_quarter, and there will never be The same highest bit can be output, so in this case, a new method is used to update the sub-interval: low=2*(low-first_quarter), high=2*(high-first_quarter)+1.

As an optimization scheme of the embodiment of the present invention, the decoding steps performed using the forward algorithm are:

Define a structure node, the structure includes low, high, which is used to represent the probability interval, metric is used to represent the importance of each branch, that is, the sum of the metrics of each node in the branch, and alpha is used to record the local probability α _t (i) , path is used to save the decoded characters, and an array scale[2] is also defined, where scale[0] indicates the total probability that the position symbol corresponding to the side information is 0 when the current decoding symbol is 0 or 1, scale[0]=alpha [0][0]+alpha[0][1]; scale[1] indicates the total probability that the position symbol corresponding to the side information is 1 when the current decoding symbol is 0 or 1, scale[1]=alpha[1][ 0]+alpha[1][1];

Step 1. According to the length N of the original source X, allocate the node space required for decoding, and initialize the decoding buffer of the distributed arithmetic code;

Step 2. During the ith decoding process (0<i≤N), read the character s _i at the current position of the side information,

Step 3. Use the forward algorithm to calculate the probability of branch 0 and branch 1 for each node when it is decoded for the i-th time. When i=1, that is, when the state is at the initial moment, the local probability is calculated using the formula α ₁ (i )=π _i b _i (z ₁ ) to calculate and record with alpha array, when i>1, the local probability is calculated by the formula Calculation, the variable α _t-1 (j) in the formula is obtained from the structure node, and after each calculation, alpha[0], alpha[1], scale[0] and scale[1], scale of this iteration are obtained [0] indicates that when the current decoding symbol is 0 or 1, the total probability that the corresponding position symbol of the side information is 0, scale[0]=alpha[0][0]+alpha[0][1]; scale[1] indicates When the current decoding symbol is 0 or 1, the total probability of side information corresponding to the position symbol being 1, scale[1]=alpha[1][0]+alpha[1][1];

Step 4: Calculate the i-th decoded symbol c _i , if the code word does not fall in the overlapping area, write the current symbol into node.path, and perform XOR operation on the decoded symbol c _i and the side information s _i , The measure of the current point is the sum of the probabilities of all paths to the point To represent, that is, scale[0] or scale[1], if the side information is the same as the current decoding symbol, The metric of the current point is represented by scale[0]. If the side information is different from the current decoding symbol, it is represented by scale[1], and the local alpha in the node is updated as Update the importance of the entire branch, for the kth branch, If the codeword falls in the overlapping area, two branches m and n are generated. At this time, node[m].metric represents the measurement of the same branch as the side information, that is, when the side information is 1, node[m] .metric represents the measurement of branch 1. When the side information is 0, node[m].metric represents the measurement of branch 0, while node[n].metric is the opposite, representing the measurement of the branch opposite to the side information. For m branch , the stored sign is the same as the side information, at this time Therefore, the overall importance of the m branch is represented by node[m].metric+=log(scale[0]), that is, the product of the scale values of all current points on the m branch, and the overall importance of the n branch is represented by node[n ].metric+=log(scale[1]) means that it is the product of the scale values of all current points on the n branch, and update the node[m].alpha in the original node with the new probability alpha[0], and use the new alpha [1] Update node[n].alpha in the original node point;

Step 5. Since a new decoding interval will be generated after decoding once, after calculating the branch metric and updating the local probability, the probability interval and related information must be updated;

Step 6. Sort all branches according to the metric value from large to small. If the number of branches is greater than the threshold M we set, cut off the redundant branches. If i<N, return to step 2; otherwise, the decoding ends , take the data saved in the path in the first branch after branch sorting as the decoding output.

The application principle of the present invention will be further described below in conjunction with the accompanying drawings and specific embodiments.

As shown in Figure 1, the hidden Markov correlation source coding method based on distributed arithmetic coding in the embodiment of the present invention includes the following steps:

S101: Generate a source;

S102: Encoding hidden Markov correlation sources;

S103: Decoding by using the forward algorithm.

Principle of the present invention is:

A. Binary arithmetic coding:

Let p be the bias probability of the binary information source X, that is, p=P(x _t =1). In classical arithmetic coding, the source symbol x _t is iteratively mapped to a subinterval of [0, 1), the length of this subinterval is proportional to (1-p) and p. The resulting code length is greater than the information entropy of X, that is, R≥H(X). In distributed arithmetic coding ^[4] , the length of the subinterval is proportional to the modified probability (1-p) ^γ and p ^γ , where γ satisfies the formula:

The generated code length satisfies R≥γH(X)≥H(X|Y). To fit in the interval [0, 1), the subintervals must partially overlap. More specifically, the symbols x _t =0 and x _t =1 correspond to the intervals [0, (1-p) ^γ ) and [1-p ^γ , 1), respectively. The introduction of overlapping regions results in a larger final interval and a shorter codeword. The resulting penalty is that without side information Y, the decoder cannot decode X accurately.

In order to describe the decoding process, this paper defines a ternary symbol set {0, χ, 1}, where χ represents an ambiguous decoding. Define C _x to be a codeword, is the t-th decoded symbol, we can get

When the t-th symbol is decoded, if The decoder generates branches: two candidate branches are generated, corresponding to the two symbols x _t =0 or x _t =1. For each new branch, its metric value is continuously updated, and its corresponding interval will be used as the start of the next iteration. In order to reduce the complexity, each time a symbol is decoded, the decoder uses the M-degree-of-freedom algorithm to ensure that at most M most important branches are retained, and all other branches are deleted.

It should be noted that for a sequence X of finite length, it is unreliable to measure some of the last symbols. Therefore, for the coding of the last T symbols, the probability intervals do not overlap, that is, the traditional arithmetic coding is adopted. In the range of 1≤t≤(NT), x _t is mapped to the two intervals [0, (1-p) ^γ ) and [1-p ^γ , 1); and for (N-T+1 ) ≤ t ≤ N, x _t is mapped to the interval [0, 1-p) and [1-p, 1).

Therefore, a binary DAC system can be described by four parameters: {p, γ, M, T}.

Hidden Markov Model and Forward Algorithm:

Assume is a sequence of states, is a sequence of observations. Use λ=(A, B, π) to define a hidden Markov process:

A={a _ji }: state transition probability matrix, where a _ji =P(s _t =i|s _t-1 =j);

B={b _i (k)}: observation probability distribution, where b _i (k)=P(z _t =k|s _t =i);

π={π _i }: initial state distribution, where π _i =P(s ₁ =i).

The purpose of the forward algorithm is to calculate the observation sequence probability P(z ₁ ,...,z _t |λ), the known observations {z ₁ ,...,z _t } and the model λ. Definition α _t (i) is the local probability of observing the sequence {z ₁ ,...,z _t }, and the state s _t is denoted by i, namely

α _t (i)=P(Z ₁ , . . . , Z _t S _t =i|, (3)

At the beginning, when t=1 there is

a ₁ (i)＝π _i b _i (z ₁ ). (4)

When t>1, α _t (i) can be obtained through iteration, namely

therefore,

In practical applications, α _t (i) is usually normalized by the following formula,

in

In this case, one can get

The concrete implementation process of the present invention is:

The first step, the generation of relevant information sources:

For two statistically correlated sources X and Y, distributed source coding usually assumes that there is a virtual correlation channel between sequence X and sequence Y, where source X is used as the input of the channel, and source Y is used as the input of the channel The output, through the channel to describe the correlation between X and Y, and the correlation between them can be measured by the conditional entropy H(X|Y), and the conditional entropy H(X|Y) can use the hidden state sequence Obtained by calculating with the observation sequence, in the invention, the source X and the side information Y are obtained by Associated, where Z is obtained by a Hidden Markov Model using parameter λ, X is encoded by a DAC encoder with four parameters {p, γ, M, T}, when encoding, the source X is used as the information source to be encoded, and the information source Y is used as side information to assist decoding at the decoding end.

In the invention, a file in HMM format is defined, which contains the number of observations M, the number of states N, the state transition probability matrix A, the observation probability distribution B and the initial probability distribution π, and the generation process of the relevant information source is:

(1) Read the HMM file to determine the hidden Markov model,

(2) Apply the hidden Markov model to calculate the observation value sequence O. A hidden Markov model mainly includes two information sequences, one is the observation value sequence that can be directly observed, and the other is the hidden state sequence that cannot be directly obtained. The hidden Markov model obtained by step (1) can calculate the observation sequence O,

(3) According to the deviation probability p, generate the source X,

(4) XOR operation is performed on the information source X and the observation value sequence O to generate side information Y.

The second step, the encoding process of the hidden Markov correlation source:

Let p be the bias probability of the binary source X, that is, p=P(x _t =1), in classical arithmetic coding, the source symbol x _t is iteratively mapped to the subinterval of [0, 1), The length of this subinterval is proportional to (1-p) and p. In distributed arithmetic coding, the allocated subintervals will overlap, that is, the symbols x _t =0 and x _t =1 correspond to the interval [0, ( 1-p) ^γ ) and [1-p ^γ , 1), it should be noted that for a finite-length sequence X ^[5] , it is unreliable to measure the last symbols, so the last T symbols The coding of , its probability intervals do not overlap, that is, using traditional arithmetic coding, in the range of 1≤t≤(NT), x _t is mapped to [0, (1-p) ^γ ) and [1-p ^γ , 1) In these two intervals; and for the range of (N-T+1)≤t≤N, x _t is mapped to the interval [0, 1-p) and [1-p, 1),

In the specific implementation process of encoding, the division of sub-intervals should also pay attention to the problem of overflow and underflow. Define low and high to represent the encoding interval, range to represent the length of the entire interval, half_range to represent half of the interval, and first_quarter to represent the quarter of the entire interval One size, third_quarter means three-quarters of the entire interval, after the interval is updated, the size of the sub-interval will continue to shrink, if not properly processed, the interval will become smaller and smaller, when the interval is too small, it will Exceeding the range of accuracy that the computer can handle and overflowing, in order to avoid this situation, the low and high endpoints of the interval must be scaled up so that the computer can maintain sufficient accuracy. The specific interval enlargement operation is as follows:

(1) When high<half_range, at this time the sub-interval is completely in the upper half area, and the most significant bits of the upper and lower endpoints of the interval are both 0, and the same most significant bit 0 is output at this time, and then the upper bound of the interval and The lower bounds are expanded by 2 times, namely: low=2*low, high=2*high,

(2) When low>half_range, the sub-interval is completely in the lower half of the range, and the most significant bits of the upper and lower endpoints of the range are both 1. At this time, the same most significant bit of 1 is output, and then the upper and lower bounds of the interval are Expand respectively, namely: low=2*(low-half_range), high=2*(high-half_range),

(3) When first_quarter≤low≤high≤third_quarter, if the low and high are still updated according to the above method, since the sub-interval keeps shrinking, the sub-interval will always be in the interval of first_quarter≤low≤high≤third_quarter, However, there is always no same highest bit to output, so in this case, a new method is used to update the sub-interval: low=2*(low-first_quarter), high=2*(high-first_quarter)+1.

The third step is the decoding process using the forward algorithm:

Suppose binary source X and side information Y pass associated, where Z is obtained by a Hidden Markov Model using parameter λ, and the decoded symbol z _{t obtained by taking XOR with side information y t ,} namely Conforms to the Hidden Markov Model, and can use the forward algorithm to calculate its local probability. The decoding process is very similar to that described in [4]. The innovation of the present invention is that in the decoding process, the measurement of each branch is used P(z ₁ ,..., z _t |λ) to represent,

The decoding method proposed by the present invention mainly utilizes the forward algorithm, and the specific implementation process of the forward algorithm is as follows:

In the implementation process of the present invention, a structure node is defined, and the structure includes low and high, which are used to represent the probability interval, metric is used to represent the importance of each branch, that is, the sum of the metrics of each node in the branch, and alpha is used to Record the local probability α _t (i), path is used to save the decoded characters, and define an array scale[2], where scale[0] indicates that when the current decoding symbol is 0 or 1, the side information corresponding to the position symbol is 0. Probability, scale[0]=alpha[0][0]+alpha[0][1]; scale[1] indicates the total probability that the position symbol corresponding to side information is 1 when the current decoding symbol is 0 or 1, scale[ 1]=alpha[1][0]+alpha[1][1], the process of DAC decoding using the forward algorithm is:

(1) According to the length N of the original source X, allocate the node space required for decoding, and initialize the decoding buffer of the distributed arithmetic code,

(2) During the i-time decoding process (0<i≤N), read the character _si at the current position of the side information,

(3) Using the forward algorithm, for each node, calculate the probability of branch 0 and branch 1 when it is decoded for the i-th time. When i=1, that is, when the state is at the initial moment, the local probability is calculated by formula (4) Calculate and record with the alpha array. When i>1, the local probability is calculated with the formula (5). The variable α _t-1 (j) in the formula is obtained from the structure node. After each calculation, the alpha of this iteration is obtained[ 0], alpha[1], scale[0] and scale[1], scale[0] indicates the total probability that the position symbol corresponding to the side information is 0 when the current decoding symbol is 0 or 1, scale[0]=alpha[ 0][0]+alpha[0][1]; scale[1] indicates the total probability that the position symbol corresponding to the side information is 1 when the current decoding symbol is 0 or 1, scale[1]=alpha[1][0 ]+alpha[1][1],

(4) Calculate the i-th decoding symbol c _i , if the code word does not fall in the overlapping area, write the current symbol into node.path, and perform XOR operation on the decoded symbol c _i and side information s _i , The measure of the current point is the sum of the probabilities of all paths to the point To represent, that is, scale[0] or scale[1], if the side information is the same as the current decoding symbol, The metric of the current point is represented by scale[0]. If the side information is different from the current decoding symbol, it is represented by scale[1], and the local alpha in the node is updated as Update the importance of the entire branch, for the kth branch, If the codeword falls in the overlapping area, two branches m and n are generated. At this time, node[m].metric represents the measurement of the same branch as the side information, that is, when the side information is 1, node[m] .metric represents the measurement of branch 1. When the side information is 0, node[m].metric represents the measurement of branch 0, while node[n].metric is the opposite, representing the measurement of the branch opposite to the side information. For m branch , the stored sign is the same as the side information, at this time Therefore, the overall importance of the m branch is represented by node[m].metric+=log(scale[0]), that is, the product of the scale values of all current points on the m branch, and the overall importance of the n branch is represented by node[n ].metric+=log(scale[1]) means that it is the product of the scale values of all current points on the n branch, and update the node[m].alpha in the original node with the new probability alpha[0], and use the new alpha [1] Update node[n].alpha in the original node point,

(5) Since a new decoding interval will be generated after decoding once, after calculating the branch metric and updating the local probability, the probability interval and related information must be updated.

(6) Sort all branches according to the metric value from large to small, if the number of branches is greater than the threshold M we set, cut off the redundant branches, if i<N, return to step (2); otherwise, After the decoding is completed, the data saved in the path in the first branch after branch sorting is used as the decoding output.

A decoding tree as shown in Figure 2, assuming that the side information is 10111, the metric of each branch is represented by the product of the scale values of all points on the current branch, such as branch 1, then the metric of branch 1 is The product of the scale value of 5 points, that is, metric=scale[1]*scale[0]*scale[0]*scale[0]*scale[1], and the scale of each point is calculated according to the local probability alpha , and the local probability is constantly updated, the calculation method scale[0]=alpha[0][0]+alpha[0][1], scale[1]=alpha[1][0]+alpha[1] [1], the calculation method of alpha is calculated according to the forward algorithm introduced earlier, which can be calculated by formulas (4) and (5),

Experimental result of the present invention:

A 16-bit DAC codec system is verified in the experiment, the deviation probability of X is p=0.5, M=2048 and T=15 are set, and the same two states (0 and 1 ) and two output sources (0 and 1) (see Table 1), the data block length used in each experiment is N=1024,

In order to achieve lossless compression, each experiment starts from γ=H(X|Y) (see Table 2). If the decoding fails, increase γ by 0.01. This process is iterated until the decoding is successful. For each model, run 100 tests were carried out, and the average value of the 100 test results was recorded in Table 2,

Table 1 Simulation model

Model {a ₀₀ , a ₁₁ , b ₀ (0), b ₁ (1)} 1 {0.01, 0.03, 0.99, 0.98} 2 {0.01, 0.065, 0.95, 0.925} 3 {0.97, 0.967, 0.93, 0.973} 4 {0.99, 0.989, 0.945, 0.9895}

Table 2 Experimental results

For comparison, the experimental results of [9] with the same settings are also recorded in Table 2. In each experiment of [9], the source symbols of N = 16384 are encoded with LDPC codes. In addition, in order to compare with Hidden Markov model synchronization, Nα original source symbols are sent directly to the decoder without compression,

Experimental results show that the performance of DAC is similar to or slightly better than that of the LDPC-based method ^[9] (Model 1 and Model 2). In addition, for hidden Markov correlation, DAC is better than LDPC-based methods in two aspects. Basic method:

(1) The LDPC-based method requires a longer codeword to achieve better execution results, while DAC is not sensitive to the length of the codeword ^[4] ,

(2) In order to keep pace with the Hidden Markov Model, LDPC-based methods must send a certain proportion of the original signal to the decoder as a seed, however, it is difficult to determine the optimal proportion α of the seed, the results reported in [9] is obtained through an exhaustive search, which limits its practical application.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. within range.

Claims (2)

1. a kind of Hidden Markov correlated source coded method encoded based on distributed arithmetic, it is characterised in that described to be based on The Hidden Markov correlated source coded method of distributed arithmetic coding is comprised the following steps：

Produce information source；

Hidden Markov correlated source is encoded；

The decoding carried out using forwards algorithms；

Wherein, the step of the generation information source it is：

HMM files are read, HMM is determined；

Observation value sequence O is calculated using HMM；

According to deviation Probability p, information source X is generated；

Information source X is carried out into XOR with observation value sequence O, side information Y is generated；

Wherein, it is described to Hidden Markov correlated source coding step to be：

If p is the deviation probability of binary source X, i.e. p=P (x_t=1), and in classical arithmetic coding, source symbol x_tIt is iterated Be mapped in the subinterval of [0,1], the length in this subinterval is proportional to 1-p and p, distributed arithmetic coding in, point The subinterval matched somebody with somebody has overlap, i.e. symbol x_t=0 and x_t=1 correspond respectively to it is interval [0, (1-p)^γ] and [1-p^γ, 1], definition Low and high presentation codes are interval, and range represents whole siding-to-siding block length, and half_range represents interval half, first_ Quarter represents whole interval a quarter size, and third_quarter represents whole 3/4ths interval sizes；

Wherein, the decoding step that the utilization forwards algorithms are carried out is：

A structure node is defined, structure includes low, high, for representing probability interval (for low and high can be same When represent lower bound and the upper bound of " coding interval " and " probability interval "), metric for represent each branch significance level i.e. The summation of each node tolerance in branch, alpha are used for recording local probability a_t(i), path for preserving the character for decoding, Define arrays scale [2] in addition, when wherein scale [0] represents that currently solution code sign is 0 or 1, side information correspondence position symbol For 0 total probability, scale [0]=alpha [0] [0]+alpha [0] [1]；Scale [1] represents that current solution code sign is 0 or 1 When, side information correspondence position symbol is 1 total probability, scale [1]=alpha [1] [0]+alpha [1] [1]；

Step one, according to length N of original source X, the node space needed for distribution decoding, and initialize distributed arithmetic code Decoding buffer zone；

Step 2, the character s in i ＆ lt decoding process, reading side information current location_i；

Step 3, forwards algorithms are used, to each node, when calculating i ＆ lt and decoding, produce the probability of 0 branch and 1 branch, work as i =1 i.e. when state is in initial time, local probability formula α₁(i)=π_ib_i(z₁), π_i=P (s₁=i) represent s₁During=i Probability, calculate and with alpha arrays record, as i ＞ 1, local probability formula Calculate, z_tObserved value is represented, b is observation probability, a_jiRepresent state transition probability, variable α in formula_t-1J () is by structure node Interior acquirement, after calculating every time, obtains the alpha [0] of current iteration, alpha [1], scale [0] and scale [1], scale [0] When to represent current solution code sign be 0 or 1, side information correspondence position symbol is 0 total probability, scale [0]=alpha [0] [0]+ alpha[0][1]；When scale [1] represents that currently solution code sign is 0 or 1, side information correspondence position symbol is 1 total probability, Scale [1]=alpha [1] [0]+alpha [1] [1]；

Step 4, the symbol c for calculating i ＆ lt decoding_iIf code word is not fallen within overlapping region, current symbol is write Node.path, and will solution code sign c_iWith side information s_iXOR is carried out, the tolerance of current point is just used and reaches all of the point The probability sum in pathTo represent, that is, scale [0] or scale [1], if side information and current solution Code sign is identical,y_tRepresent side information, z_tThe XOR of information source and side information is represented, the tolerance of current point is just Represented with scale [0], if side information and current solution code sign are different, with regard to scale [1] expressions, and by the local in node Alpha is updated toThe importance of whole piece branch is updated, for kTiao branches,If code word falls in overlapping region, Liang Ge branches m and n are produced, this When node [m] .metric represents is tolerance with side information identical branch, i.e., when side information is 1, node [m] .metric the tolerance of 1 branch is represented, when side information is 0, node [m] .metric represents the tolerance of 0 branch, and node [n] .metric then conversely, represent the tolerance of the branch contrary with side information, for m branches, its symbol for storing and side information phase Together, nowSo the overall importance of m branches just uses node [m] .metric+=log (scale [0]) table Show, i.e., the product of the scale values of current all points in m branches, and the overall importance of n branches just uses node [n] .metric+ =log (scale [1]) expressions, i.e., the product of the scale values of current all points in n branches, and with new probability alpha [0] more Node [m] .alpha in new original node points, updates node [n] .alpha in original node points with new alpha [1]；

Step 5, as decoding will once be produced, new decoding is interval, so having calculated the tolerance of branch and have updated locally After probability, the information for update probability interval and related；

Step 6, all branches are ranked up from big to small according to metric values, if branch's number is more than set by us Threshold value M, then cut unnecessary branch, if i is ＜ N, return to step two；Otherwise, decoding terminates, after branch is sorted The data that path is preserved in one branch are used as decoding output.

2. the Hidden Markov correlated source coded method encoded based on distributed arithmetic as claimed in claim 1, its feature It is that described coding to Hidden Markov correlated source also includes specific interval amplifieroperation：

As high ＜ half_range, at this moment subinterval is completely disposed in upper half, and the highest of the end points up and down in the interval is effective Position is all 0, output identical highest significant position 0, the interval upper bound and lower bound is expanded 2 times respectively then, i.e.,：Low=2* Low, high=2*high；

As low ＞ half_range, at this moment subinterval is completely disposed in bottom half, the highest significant position of the end points up and down in the interval All it is 1, now exports identical highest significant position 1, then the interval upper bound and lower bound are expanded respectively, i.e.,：Low=2* (low-half_range), high=2* (high-half_range)；

As first_quarter≤low≤high≤third_quarter, if also according to above-mentioned method to low and High is updated, as subinterval constantly reduces, so subinterval can always be in first_quarter≤low≤high In this interval of≤third_quarter, and no identical the highest-order bit can be exported all the time, so in this case Just subinterval renewal is carried out with new method：Low=2* (low-first_quarter), high=2* (high-first_ quarter)+1。