JP5409196B2 - Encoding method and decoding method - Google Patents

Description

  The present invention relates to a digital data encoding method and decoding method, and more specifically, an encoding method for converting n-bit input data into a code having a code length N including redundant bits under a predetermined constraint condition, and Further, the present invention relates to a decoding method for decoding a code converted under the constraint condition into original n-bit data, and further relates to an encoding device and a decoding device that implement these methods.

  In a digital transmission or recording system, redundant bits are added for various purposes when converting input data into a code suitable for transmission or recording. As a method of giving a redundant bit to a code, a certain rule (constraint) to be satisfied by a code having a code length N is determined for given n-bit input data, and this rule (hereinafter referred to as “constraint condition”) is determined. There is a method for converting input data into code (Patent Document 1, Non-Patent Document 1). Here, the ratio (= n / N) between the number of bits n of the input data and the code length N of the code is called a coding rate, and N−n = K is the number of redundant bits. Under constraint conditions, the encoding and decoding procedures become more complicated as the encoding rate approaches the maximum theoretically possible value (referred to as Shannon capacity).

Japanese Patent Laid-Open No. 11-186717

Kees A. Schouhamer Immink, "Codes for Mass Data Storage Systems," Second Edition, published by Shannon Foundation Publishers, Edindhoven, The Netherlands, 2004 (pp. 1-5, 9-10, 20-22, 137-141, 215 -218) Lyle J. Fredrickson, "On the Shannon Capacity of DC-and Nyquist-Free Codes", IEEE TRANSACTIONS ON INFORMATION THEORY, VOL37, NO.3, MAY 1991

  Various techniques exist for the above-mentioned coding with constraints, and one of the methods for achieving a coding rate close to capacity is enumerated coding. In this method, ranks are calculated for all possible numerical values of n-bit input data, and this is defined as an index. Then, by extracting all codes satisfying the constraint condition from the set of codes with the code length N, and assigning a one-to-one correspondence between the index set and the extracted code set, In actual signal processing, conversion to code and decoding to input data are executed based on this correspondence. Here, the correspondence between the index and the code can be defined by a lookup table. However, this association method using the lookup table becomes difficult when the number of bits of input data increases. For example, when the input data is 200 bits (n = 200), it is necessary to set the correspondence of 2 to the 200th power in the lookup table. Have difficulty.

  In counting encoding, encoding and decoding are performed using a trellis diagram under a certain constraint condition. In this case, in addition to the look-up table, the total number of paths on the trellis diagram and the weight based on the number of paths from each state to the final state on the trellis diagram are necessary for calculation. For example, when N = 4000, considering a trellis diagram that can take 17 states as a constraint, the memory required to store the weight is 4000 * (2 * 8 + 1) * 4000 = 30 MB. Therefore, it cannot be realized due to hardware limitations.

  The present invention makes it possible to calculate the correspondence between the index of the input data and the code in counting encoding, eliminates the need for a lookup table for association, and eliminates the need to calculate and store weights in advance. It aims to be.

  An encoding method according to the present invention is an encoding method for converting n-bit input data into an N-bit code including redundant bits under a predetermined constraint condition, and accepting n-bit data, In the initialization step, an index determination step for determining an index for the received n-bit data, and a trellis diagram determined under the constraint condition, the trellis when the state at the next time point is set as a start point The total number of paths that can be taken to reach the end point in the diagram is defined as the weight of the state at the next time point, the weight calculation step for calculating the weight or a value approximate thereto, and the state transition from the current time point to the next time point Select one of a plurality of paths from the current state based on the index and the weight of the state at the next time point or a value approximate thereto A path determination step determined by the above, a symbol value determination step for determining a value assigned in advance to the determined path as a symbol value of the code, and the path satisfies a predetermined condition based on the determined path In this case, the normalization step for normalizing the index, the state update step for updating the state by changing the state to the next time point according to the path determined in the path determination step, and the weight calculation step to the state update step are repeated N times. This is a method including a repetition step and a code output step for outputting the sequence of numerical values determined in the determination step as a code.

  A first decoding method according to the present invention is a decoding method for decoding a code encoded with redundant bits under a predetermined constraint condition into original n-bit data, wherein the code is Accepting and initializing, and in the trellis diagram determined under the constraint conditions, the state on the trellis diagram is right according to the symbol value of the bit corresponding to each time point included in the code A path specifying step for specifying a path that advances to one point in time, and the total number of paths up to all possible end points when a state with point k in the trellis diagram is set as the starting point is used as a weight of the state at that point k. For the identified path, the weight of the state following the path that is truncated when the numerical value in the code corresponding to the current time is a predetermined value or a value approximate thereto is calculated. State according to the path specified in the weight calculation step, the index addition step for adding the value of the truncated weight or its approximate value to the index only when there is a truncated weight or its approximate value, and the path specifying step A state update step that updates the state by transitioning to the next time point, an index integrated value calculation step that repeats the process from the path identification step to the state update step for all symbol values included in the code, and the calculated index And determining a value as an index of the original data, and outputting the original data based on a predetermined relationship between the original data and the index.

  Furthermore, a second decoding method according to the present invention is a decoding method for decoding a code encoded with redundant bits under a predetermined constraint condition into original n-bit data, wherein the code is In the accepting step, in the trellis diagram determined under the constraint condition, on the basis of the code, determining the final state corresponding to the code, and setting the index to zero starting from the final state An initialization step, a path specifying step for specifying a path whose state returns one time point to the left on the trellis diagram according to a symbol value of a bit corresponding to each time point included in the code, and a time point k in the trellis diagram The total number of paths up to all possible end points when a certain state is a starting point is defined as the weight of the state at that time k. When the numerical value in the code corresponding to the point is a predetermined value, a weight calculation step for calculating the weight of the state following the path that is truncated when the time is returned or a value approximate thereto, and the truncated weight or An index addition step that adds the truncated weight or an approximate value to the index only when there is an approximate value, and updates the state by transitioning the state to the previous time according to the path selected in the path determination step. A state update step, an index integrated value calculation step that repeats from the path identification step to the state update step for all symbol values included in the code, and the calculated index value is determined as an index of the original data Pre-determined between the original data and its index Based on the relationship, a method comprising the step of outputting the original data.

  In these encoding or decoding methods of the present invention, in the weight calculation step, calculation of the power of 2 by bit shift and the maximum eigenvalue of the transition matrix corresponding to the trellis diagram are already calculated and stored in the storage means. A weight can be calculated using a lookup table including stored values and the eigenvector of the transition matrix.

  The invention further relates to an encoding device and a decoding device. An encoding apparatus according to the present invention is an encoding apparatus that converts n-bit input data into an N-bit code including redundant bits under a predetermined constraint condition. And an index calculation unit that calculates an index indicating the rank in the data series for the data, and a trellis diagram defined under the constraint condition, the trellis In the diagram, the total number of paths that can be taken to reach the end point is defined as the weight of the state at the next time point, a weight calculation unit that calculates the weight or a value approximate thereto, and the state transition from the current time point to the next time point And selecting one of a plurality of paths continuing from the current state based on the weight of the state at the next time point or a value approximate thereto, and A pre-assigned value for a given path is determined as a symbol value of the code, and based on the determined path, a comparison / output unit that normalizes an index when the path meets a predetermined condition is determined And a state updating unit that updates the state by changing the state to the next time point according to the path, and repeats N times from the weight calculation to the state update.

  The first decoding device of the present invention is a decoding device that decodes a code encoded with redundant bits under a predetermined constraint condition into original n-bit data, and accepts the code. In the trellis diagram determined under the constraint conditions, the state is set to 1 on the trellis diagram according to the symbol value of the bit corresponding to each time point included in the code. A state update unit that performs state update by specifying a path to be progressed at a time point, and the number of paths up to all possible end points when the state at the time point k is a start point in the trellis diagram, the weight of the state at the time point k A weight calculation unit that calculates a weight of a state following a path that is rounded down by a numerical value in a code corresponding to the current time being a predetermined value or a value approximate thereto for the identified path; It includes an index calculation unit that adds the discarded weight or its approximate value to the index when there is a discarded weight or its approximate value, and includes the index calculation from the state update in the code This is a decoding device that repeats all symbol values and outputs original data based on the integrated value of the final index.

  Furthermore, the second decoding device of the present invention is a decoding device that decodes a code encoded with redundant bits under a predetermined constraint condition into original n-bit data, and accepts the code. In the trellis diagram determined under the constraint conditions, the final state specifying unit for specifying and initializing the state at the final time point based on the code, and the individual included in the code in the trellis diagram A state update unit that updates the state by identifying a path whose state returns to the left by one point on the trellis diagram according to the symbol value of the bit corresponding to the point in time, and a state at the point k in the trellis diagram. By defining the number of paths up to all possible end points as the start point as the weight of the state at that time k, the numerical value in the code corresponding to the current time for the specified path is a predetermined value A weight calculation unit that calculates a weight of a state following a path to be discarded or a value approximate thereto, and if there is a weight that has been truncated or a value that approximates it, the weight that is truncated or a value approximate to it is added to the index And an index calculation unit, which repeats index calculation from state update for all symbol values included in the code, and outputs original data based on the integrated value of the final index .

  In these encoding devices or decoding devices, the weight calculation unit has already calculated the power of 2 by bit shift and the maximum eigenvalue of the transition matrix corresponding to the trellis diagram, and stored in the storage means. It is possible to calculate a weight or a value approximating it using a look-up table including the measured value and the eigenvector of the transition matrix.

  According to the present invention, in the conversion from the input data to the code, the path from the state to the next state is set to any one of the final state from the state using the path of the state transition on the trellis diagram as an index. The numerical value of the weight corresponding to the total number of paths up to is calculated, and the code is obtained from the index of certain input data based on the calculated weight value. This weight calculation performed in the process of encoding is important in the present invention. In the present invention, the total number of paths from each state on the trellis diagram is not counted or stored. In addition, a lookup table for directly assigning the correspondence between the original data and the code is not used. As a result, it is possible to determine the correspondence between the index of the input data and the code based on the path where the state transitions. Therefore, it is very large for providing a direct correspondence between the original data and the code. Thus, even if the number of digits of input data is considerably large under constraint conditions, a high coding rate can be achieved by a relatively simple method of path selection.

  Similarly, in decoding from a code to the original data, it is possible to specify a path whose state transitions on the trellis diagram based on a numerical value in the input code. Therefore, the correspondence relationship between the code and the original data index is determined based on the number of paths (weights) to be cut off when converting to the code, and it is very large for providing a direct correspondence between the code and the original data. The decoding of the original data can be achieved by calculating the index of the original data without using the lookup table. According to the present invention, the weight is calculated numerically. There is no need to count the paths for each state or store and use the total number of paths to obtain the weight.

The block diagram which shows the structure of the encoding apparatus which concerns on the 1st Embodiment of this invention. Explanatory drawing which shows the concept of the process of the encoding and decoding which concern on the embodiment Explanatory drawing which shows notionally the correspondence of the input data which concerns on the same embodiment, a rank identification index, and a code Trellis diagram for encoding according to the embodiment Explanatory drawing which shows the encoding process which concerns on the embodiment notionally (transition to the time 1, 2, 3) Illustration of encoding process (transition to time point 4) Illustration of encoding process (transition to time points 5 and 6) Flow chart showing the flow of encoding process Flow chart showing weight calculation method Illustration of transition matrix for trellis diagram The flowchart which shows the flow of the decoding process which concerns on embodiment which concerns on the 2nd Embodiment of this invention. The block diagram which shows the structure of the decoding apparatus which concerns on the 2nd Embodiment of this invention. The flowchart which shows the flow of the decoding process which concerns on the 3rd Embodiment of this invention.

  Embodiments of the present invention will be described below with reference to the drawings.

  FIG. 1 is a block diagram showing a configuration of an encoding apparatus according to the first embodiment of the present invention. In this embodiment, the n-bit input data i, whose outline is shown in FIG. 2, is converted into a code c having a code length N including K redundant bits under a predetermined constraint (N = n + K).

An index calculation unit 111 shown in FIG. 1 receives input data i and calculates an index I of the input data i. The index I indicates the order in the sequence of n-bit input data i. In the present embodiment, for example, a decimal conversion value (= 0 to 2 ⁿ −1) of the input data i is adopted as the index I. Here, the decimal conversion value of the input data i is adopted because the decimal number is easier to understand for explanation, and the input data i is used as an index for ranking in an actual calculation. Can be used.

FIG. 3 shows the relationship between the input data (length n bits), the decimal conversion value of the input data, and the code (length N) in this embodiment. Here, the n-bit input data and the N-bit code are generally expressed as strings of n and N symbol values, respectively. Needless to say, there is a binary value as a representative example of the symbol value, but it is not limited to the binary value. In this specification, a case where the symbol value is a binary value will be described as an example. U (i) represents a column in which binary data that may be inputted with n bits is arranged. I (i) indicates a column of decimal conversion values of the n-bit input data. The display of 1 to ²ⁿ shown beside each conversion value for the column I (i) is an increasing order starting from decimal conversion value = 0, and this is referred to as index I. When the decimal conversion value of the input data i is 0, the index I is also 0, and the index I increases as the decimal number increases.

As illustrated in FIG. 3, for example, when there is n-bit input data consisting of all zero values, the corresponding N-bit code is 0 or 0 based on some rule to provide redundancy. 1 is added. Similarly, the code for the input data of all 1s at the end of U (i) includes an additional 0 or 1. The N-bit code includes m codes that have no correspondence with input data. An N-bit code string (FIG. 3) that satisfies the constraint condition is called C (M, N). M represents a constant related to the constraint condition, and N is the number of bits of the code to which redundancy is added in the same manner as above. Encoding and decoding can be performed by associating an input data string with an element of C (M, N) via an index. Assuming that the number of elements in the set C (M, N) is P, theoretically, if P is equal to or greater than 2 to the power of n, encoding and decoding can be performed. If the minimum value of N that satisfies such conditions is N _min , the coding rate close to the theoretical limit of counting encoding or Shannon capacity is n / N _min .

FIG. 4 shows a trellis diagram expressing the constraint conditions according to the present embodiment. The intersection of the lines in the trellis diagram of FIG. 4 indicates a state S _k that can be taken at that time k. And in the conversion from input data to a code | symbol, a constraint condition is provided by a running digital sum (RDS, Running Digital Sum). The RDS sign “1” and “0” have a value “+1” (meaning a transition upward in the trellis diagram) and a value “−1” (also meaning a transition downward in the right direction). ) Represents the sum of these values from the start point of the code string. Specifically, the RDS calculation is -1 if the value of the sign determined in the following procedure corresponding to the transition from the time point k to the time point k + 1 is “0”, and 1 if it is “1”. By sequentially adding each time point. In other words, in the trellis diagram having the RDS value as the vertical axis, if the value of the code corresponding to the transition from a certain time point k to the time point k + 1 is “0”, the state S _{k is} moved toward the next time point k + 1. While the transition is made to the state S _{k + 1 in the} direction in which RDS is decreased by one (diagonally below), in the case of “1”, the state S _k is transited in the direction in which RDS is increased by one (obliquely). The value that can be taken by the RDS is limited by a given constraint condition.

  The constraint condition represented by the trellis diagram of FIG. 4 limits RDS between +2 and −2. Starting from RDS = 0, if 1 or 0 continues in the input data twice, then 0 or 1 is inserted next. That is, the running digital sum (RDS) is limited to a range of ± 2 by setting M = 2.

  Here, as an example, N = 10 and M = 2, but N = 10 is intentionally selected to be a small number for the purpose of explanation. The present invention can be applied to codes having a large number of bits such as N = 20 or more and thousands. Similarly, M = 2 is not a numerical value that limits the scope of the present invention. In this example, the total number of C (2,10) elements is 324. Therefore, it can be understood that 8-bit input data can be encoded using C (2,10) because n = 8 and the eighth power of 2 are 258.

Then, the numbers described near each intersection in Figure 4 shows the number of paths leading up to one of the end points S ₁₀ which can be taken in this diagram when starting from the state S _k represented by the intersection ing. In other words, from state S _k until reaching the end point S _10, the number of combinations of path segments between the time points. The number of passes about the state _{S k + 1,} is used as a weight _{W k} when considering a transition from state _{S k} to state _{S k + 1.} For example, at the time 0, the state S ₀ exists only at one point of RDS = 0 according to the definition of RDS, and reaches all the end points S ₁₀ (three states of RDS = −2, 0, 2). The number of possible paths (weight W ₀ ) is 324. That is, in order to consider the transition from the time point k = 0 to the time point k = 1, there are the state S ₁ (−1) and the state S ₁ (1) as transition destinations, and the weight W _{1 of} the transition toward each of them. There are (−1) = 162 and W ₁ (1) = 162 (the parenthesis of W ₁ represents the value s of RDS). At time point k = 2, there are a total of three states S ₂ (−2), S ₂ (0), S ₂ (2) (corresponding to RDS = −2, 0, ₂ respectively) and time point k. The weight W _{2 of} each state from = 1 to the time point k = 2 is W ₂ (−2) = 54 (RDS = −2), W ₂ (0) = 108 (RDS = 0) from the bottom toward the drawing. ), W ₂ (2) = 54 (RDS = 2).

  Looking at the start of FIG. 4, assuming that the path P1 that is the element of C (M, N) illustrated in FIG. 4 is 0011101100111, assuming that RDS = 0, first, since the first code is 0, RDS = Transition to −1 and the next code is also 0, so transition to RDS = −2. After that, since 1 continues three times, the transition is made to RDS = + 1. Next, 0 continues twice, so RDS = −1. However, since 1 continues three times, RDS = 2 ends. Thus, it can be seen again that P1 satisfies the constraint condition. The same applies to the exemplified P2 = 0101101001 and P3 = 1000110111. Such P1 to Pn are associated with input data.

  As another constraint condition, in Non-Patent Document 2, when a code is represented by the NRZ (Non Return to Zero) method, a value “+1” and a value “−” are added to the code “1” and the code “0”, respectively. FSTD that considers both ADS (Alternate Digital Sum) and RDS, which represents the sum from the start time of consecutive code strings when “1” is matched and the value “−1” is multiplied every other bit, is also proposed Has been. Such FSTD is also an object of the present invention. Also, constraint conditions such as RLL (run-length limited constraint) and MTR (mazimum transition run constraint) can be used in the same way, and more complicated codes can be generated and decoded. The constraint condition RLL (d, k) is such that the number of 0s between 1 and 1 is a minimum of d and a maximum of k. The MTR limits the number of continuous changes 101010 or 010101, and the MTR (j; k) in the NRZI system constrains the number of consecutive 1s to j and the number of consecutive 0s to k. It is.

The comparison / output unit 112 compares the index I calculated by the index calculation unit 111 with the weight W (= W _{k + 1} ) calculated by the weight calculation unit 113 described below, and changes the state on the trellis diagram of the code. In addition to selecting a path to be used, a numerical value “0” or “1” previously assigned to the selected path is output as a code value at each time point.

For the trellis diagram described above, the weight calculation unit 113 uses the state S _k (s) where the RDS value is s at the time point k as the start point, and passes through all possible end points _SN in this diagram. to calculate the weight W _k is the total number of. Specifically, the encoding apparatus according to the present embodiment includes a weight calculation unit 113 that calculates the weight W _k (s) for the state S _k (s) on the trellis diagram. In the weight calculation unit 113, the transition matrix T (transition matrix generation unit 125) obtained corresponding to the trellis diagram, and the maximum right eigenvalue λ _max (maximum eigenvalue calculation unit 127) calculated for the transition matrix T are obtained. ), And the value R (s) of the eigenvector component of the transition matrix T (s = integer of −2 to 2 under the constraint condition of the present embodiment) (eigenvector calculation unit 126) and the calculation described below. The weight W _k (s) can be calculated from the equation. The parameter calculation unit 121 includes the transition matrix generation unit 125, the eigenvector calculation unit 126, and the maximum eigenvalue calculation unit 127, but this is not necessarily required to be part of the apparatus of the present invention. A transition matrix is determined corresponding to the set constraint condition, and an eigenvector and a maximum eigenvalue of the transition matrix can be obtained in advance and used for numerical calculation of weights. Here, the comparison output unit 112 receives the state weight W _{k + 1} at the next time point k + 1 from the weight calculation unit 113, compares the index I with the input weight W _{k + 1,} and changes the state toward the next time point k + 1. Select the path to transition.

State update unit 115 transits the state according to the selected path by comparing the output section 112, (advance the state S _{k + 1} from the S _k) to update the status.

FIG. 4 shows a trellis diagram of codes according to the present embodiment and paths P1 to P3 that are selected when three different codes are output. A path P1 indicated by a solid line is a path when outputting the code c ₁ = (0011100111), and a dotted line and a one-dot chain line are paths when outputting the code c ₂ = (0110110001) and the code c ₃ = (1000110111). P2 and P3 are shown respectively.

As described above, the symbols c1 to c3 represented by the paths P1 to P3 all satisfy the constraint condition of M = 2. For example, in the path P1, since RDS = 0 at the time point 0 and the numerical values of the first bit and the second bit of the code c1 are both “0”, the states S ₀ and S _{1 at} the time points 0 and 1 respectively. A path in the direction of decreasing RDS by one is selected. Therefore, at time point 2, RDS is −2. Since the numerical value is “1” in the subsequent third to fifth bits, the path selected for the states S _{2 to} S ₄ switches in a direction to increase RDS by one, and RDS increases to 1 by time point 5. Then, it becomes “0” again at the 6th and 7th bits and becomes “1” after the 8th bit, so that the final RDS value is 2, and the code c1 represented by this path P1 has the above constraint condition. Fulfill. The same applies to the other codes P2 and P3. Here, the path P2 is separated from the path P1 at time 1 and the path P3 is separated from the path P1 at time 0. Therefore, there are different paths on the trellis diagram for all codes that satisfy the constraint conditions included in C (M, N).

Here, the operation of the encoding apparatus according to the present embodiment will be described by taking as an example the case where 8-bit input data 00100001 is input. In conclusion, the encoding device changes the state along the path P1 in the trellis diagram of FIG. 4 and converts this input data into code c ₁ = (0011100111).

  5a to 5c show the operation of the encoding device (specifically, the comparison output unit 112 and the state update unit 115) when input data i = (00101001) is input. First, the encoding device calculates an index I of input data i that has been input. As already described, the index I is the rank in the 8-bit sequence of the input data i in which the numerical value increases starting from 0, and is the decimal conversion value 41 of the input data i.

As shown in Figure 5a, the time 0, there is a state at the RDS = 0, the index I = 41 is the possibility of a transition to state _{S 1} at the next time point 1, to the state of the RDS = 1 The weight W ₁ (1) representing the possibility of transition is 162, and the weight W ₁ (−1) representing the transition to the state of RDS = −1 is also 162. In order to determine which path I = 41 belongs to among the 324 possible paths in total, the 324 paths are first counted, and the path starting from 1 and ending at 324 at the top is vertically An aligned vertical column 201 is created. The elements in the column corresponding to the index I = 41 are shown with hatching. Since the element with I = 41 belongs to 162 elements corresponding to W _i (−1) at the bottom of the column 201, it is determined that the element corresponds to a path in which RDS decreases by one. That is, c ₁ (1), which is the value of the code corresponding to the transition to the time point k = 1, becomes zero and RDS = −1.

Since the upper half of this column 201 has no possibility of passing as a path anymore, it is truncated and the next column 202 is created. Then, the elements in this column include the first 1 to 162 elements. Considering the transition to the state S ₂ , the weight becomes W ₂ (−1) = 54 and W ₂ (0) = 108 in the direction in which the RDS decreases. This is expressed by a column 203 having 162 elements. When I = 41 corresponds to the lower element in the column 203 or the upper 108 element in association with the column 202, it can be seen that it is included in the lower 54 element. This means that the RDS is reduced by one, so that c ₁ (2) = 0 for the value c ₁ (2) of the code corresponding to the transition to the time point k = 2. Then, in S ₂ , the state is in the state S ₂ (−2) where RDS = −2. Since there is no possibility of a transition in the direction in which the RDS at the top of the column 203 increases by one (the side of the weight W ₂ (0)), the column 204 is created by truncating it.

Here, since the constraint condition is M = 2, the RDS does not decrease any more, so the transition is made in the direction in which the RDS is increased by one in addition to the transition to the state S ₃ (−1). That is, c ₁ (3) = 1 and RDS = −1.

Next, with reference to FIG. Since the previous transition was made with no room for selection, there is no change in column 204. Then, the weights of the transition to the time point 4 are W ₄ (−2) = 18 and W ₄ (0) = 36. If this is expressed as a column, a column 205 is obtained. Looking at column 205, it can be seen that I = 41 is on the side of weight W ₄ (0) = 36 in column 205. Since the transition is in a direction in which RDS increases by ₁ , c ₁ (4) = 1 and RDS = 0. Then, since the lower part of the column 205 can be cut off, the column 206 is formed. At this time, since the number of the lowermost element in the column 206 is 19, the numbering is normalized, and the numbers of the entire elements are shifted by 18 so that the lowermost edge starts from 1. Then, it becomes column 207, and the element of I = 41 becomes the 24th (41-18 = 23) counting from 0.

Looking at FIG. 5 c, the weights of the next transition are W ₅ (−1) = 18 (lower part) and W ₅ (1) = 18 (upper part), so that the column 207 can be expanded as the column 208. Since it is understood that the 24th element from the bottom is on the W5 (1) side, c ₁ (5) = 1 and RDS = 1. Then, if the lower part of the column 208 is truncated, the column 209 is obtained. As in the previous case, when numbering is normalized by 18 elements that are rounded down, a column 210 is obtained. The element corresponding to the original I = 41 comes sixth from the bottom.

Then, considering the transition to the next time point 6, since the weights W ₆ (0) = 12 (lower part) and W ₆ (2) = 6 (upper part), the column 211 is obtained. The element corresponding to I = 41 is at the bottom. Therefore, it can be seen that the next transition is in the direction of decreasing RDS, and c ₁ (6) = 0 and RDS = 0.

Although not shown in the drawings, when this is repeated, c ₁ (7) = 0, c ₁ (8) = 1, c ₁ (9) = 1, c ₁ (10) = 1, and time 10 It can be seen that RDS = 2. In this way, input data of I = 41 can be encoded into the code 0011100111.

  FIG. 6 is a flowchart showing the encoding method according to the present embodiment described above.

In S11, as an initialization, the index I is calculated, the time point k is set to 0, and the state is set to S ₀ (0) (the value s of RDS is set to zero in parentheses).

In S12, reads the weight _{W k + 1} of each state from the weight calculation unit 113 at the next time k + 1, if the value of the index I is greater than the weight _{W k} + 1 is the number of paths that follow in the direction of reducing the RDS (s-1) not Determine whether. When it is larger than W _{k + 1} (s−1), the process proceeds to S13, and when it is equal to or less than W _{k + 1} (s−1), the process proceeds to S14. When the state is RDS = −2 at the current time k (s = −2), since there is a constraint condition of M = 2, the transition to the state of RDS = −3 cannot be made, so that the next time point k + 1 is reached. The transition weight W _{k + 1} (−3) is zero. W _k (−2) = W _{k + 1} (−1).

In S13, since the state in the direction of RDS increases it has been found that transition, the code of the corresponding bit c a (k + 1) is set to "1", a state S _k along the direction of the path of RDS increases state Transition to S _{k + 1} . Further, since the path in the direction in which the RDS decreases is truncated, the index I is normalized, and the weight W _{k + 1} (s−1) corresponding to the number of paths to be discarded is subtracted from the index I sequence. The value s of RDS is s + 1.

In S14, since it is known that the state transitions in the direction in which RDS decreases, the corresponding bit c (k + 1) of the code is set to “0”, and state S _k is in a state along the path in the direction in which RDS decreases. Transition to S _{k + 1} . The value s of RDS is s-1.

  In S15, the time point k is advanced by 1, and it is determined whether k obtained by adding 1 is equal to or less than (N−1). If it is (N-1) or less, the process returns to S12. If it is greater than (N-1), the encoding process for the input data i is terminated.

  As described above, according to the present embodiment, by employing the enumerative coding method, it is possible to achieve a high coding rate under constraint conditions. Furthermore, in this embodiment, since the correspondence between the index I of the input data and the code c is determined by calculation based on the path where the state S transitions, the encoding process is performed with a relatively simple procedure. Can do. According to this embodiment, a lookup table for determining the correspondence between the index I and the code c is not necessary.

In the first embodiment described above, the weight W _k (s) on the trellis diagram is set for each state S _k (s) at each time point k (k = 1, 2,..., N) (s = −2). It was described as known in ~ 2). When the number of bits of input data is small, this weight can be calculated in advance and stored in the storage device. However, the weight W _{k + 1} obtained by counting the number of paths is a numerical calculation called a “weight system” (Weight System) that can be obtained by calculation when necessary by the inventors as described below. It has been proven that the results can be replaced. This weight system is a weight based on the pass count or a value approximating it. By calculating the numerical value of the weight system each time by calculation, the amount of data to be stored can be dramatically reduced, and the amount of necessary numerical calculation does not increase greatly.

Such calculation is performed by the weight calculation unit 121 of FIG. First, the basic structure of the trellis diagram shown in FIG. 4 has a state transition pattern as shown on the left side of FIG. A transition matrix T corresponding to this state transition pattern is shown on the right side of FIG. 1 indicates that transition is possible, and 0 indicates that transition is not allowed. That is, the diagonal elements of the transition matrix T are all zero, indicating that there is no transition from a certain state to the same state. For example, the element in row 1 column 2 is 1, indicating that the transition from the RDS = 2 state (S _k (2)) to the RDS = 1 state (S _{k + 1} (1)) is possible. Yes. Similarly, the element in row 2 column 1 is 1, which means that a transition from the state of RDS = 1 (S _k (1)) to the state of RDS = 2 (S _{k + 1} (2)) is possible. Is shown. From this transition matrix T, it can be seen that the transition can only be made to an adjacent state, for example, a direct transition from RDS = 2 to RDS = 0 is not allowed. According to the weighting system of the present invention, it has been proved that the formula 1 is established based on the Perron-Frobenius theorem. In other words, it has been proved that the encoding and decoding of the counting method can be performed using W _k (s) obtained by solving the following equation instead of the weight obtained by counting the number of paths.
(Equation 1)
W _k (s) = Ceil {(λ _max ) ^Nk · R (s)}
Here, s is the value of RDS, and W _k (s) represents the weight as a function of s at time k. λ _max is the maximum right eigenvalue of the transition matrix T and is a constant. R (s) is a component of the right eigenvector of the transition matrix T. Ceil means rounding up to integer.

  The encoding apparatus according to the present invention includes a parameter setting unit 121 in addition to the index calculation unit 111, the comparison output unit 112, the weight calculation unit 113, and the state update unit 115. The parameter setting unit 121 includes a transition matrix generation unit. 125, an eigenvector calculation unit 126, and a maximum eigenvalue calculation unit 127.

The transition matrix setting unit 125 sets a transition matrix T representing the characteristics of transition from each state in the trellis diagram. FIG. 8 shows the transition matrix T when the constraint condition is given by the RDS restriction code of M = 2, as described in the explanation regarding the first embodiment. The transition matrix T represents a state S _k at a time point k in the column direction, and represents a state S _{k + 1} to be transitioned to the next time point k + 1 in the row direction. Specifically, the transition matrix T, whether the transition from state S _k represents the value of 0 or 1. 1 indicates that transition is possible, and 0 indicates that transition is not possible. Transition from the upper first row represents whether a transition from RDS = 2 states _S k (2) to state _{S k +} 1 of the next time point _(s), from _S k (2) of the _{S k +} 1 to the (1) This indicates that only the other transitions to S _{k + 1} (2), S _{k + 1} (0), S _{k + 1} (−1), and S _{k + 1} (−2) are impossible. Similarly, the second row from the top indicates whether or not the transition from the state S _k (1) of RDS = 1 to the state S _{k + 1} (RDS) of the next time point is possible, and S _k (1) to S _{k + 1} (2) And S _{k + 1} (0) are possible, and other transitions to S _{k + 1} (1), S _{k + 1} (−1), and S _{k + 1} (−2) are not possible.

  The eigenvector calculation unit 126 calculates the right eigenvector R of the transition matrix T set by the transition matrix generation unit 125.

  The maximum eigenvalue calculation unit 127 calculates the maximum right eigenvalue λ of the set transition matrix T.

The weight calculation unit 113 receives the eigenvector R and the maximum eigenvalue λ of the transition matrix T set by the parameter setting unit 121, and calculates the weight W _k (s) of the state S _k by the following equation. The following equation can be derived based on the transition matrix T.
(Equation 2)
W _k (s) = Ceil {(λ _max ) ^Nk · R (s)}

The transition matrix T is determined based on the structure of the trellis diagram. For a transition matrix T for a given trellis diagram, one maximum right eigenvalue λ _max (= constant) and state (eg, S _k (2), S _k (1),..., S _k (−2) ) To obtain the right eigenvector having the number of components corresponding to the number of. The eigenvector can be calculated relatively easily from the transition matrix. Usually, the component of the eigenvector is normalized so that the maximum value is 1. The component of the eigenvector corresponds to each state and is a function of s which is the value of RDS. In this example, there are five possible values of s (s = integer of −2 to 2). Correspondingly, it has five components. This is called R (s).

FIG. 7 shows a flowchart of the weight calculation method as described above. As described above, the transition matrix T is obtained. In order to apply the Peron Frobenius theorem to this transition matrix, a strongly connected state transition graph is required. In other words, looking at each of all states, a certain state must always be connected from some previous state, so that it is possible to go to some later state. From a transition matrix perspective, this means that there are no rows or columns where all elements are zero. Therefore, when generating a transition matrix, it should be checked for such rows or columns and, if any, such rows or columns should be deleted. Then, the above equation 2 is applied. That is, the maximum value λ _max of the right eigenvalues of the transition matrix T is obtained, and the component R (s) of the right eigenvector is obtained. These can be calculated by known solutions or algorithms.

Here, in the calculation of the weight W _k (s) by the above equation 1, first, since the transition matrix T is known, its maximum eigenvalue λ _max and eigenvector R (s) are known. As the eigenvector, a value obtained by normalizing the size of the maximum vector to 1 can be used. What needs to be calculated is (λ _max ) ^Nk . However, if such a power is calculated by a circuit, a lot of multipliers are used, and the circuit design becomes complicated. Therefore, after setting N−k = y, new variables q and Q are introduced so that λ _max ^y = 2 ^(yQ) · 2 ^{(−r / q)} . Then, if Q is also an integer, y (= N−k) is an integer as well as 2 ^(y−Q) , and 2 ^(y−Q) can be easily calculated by a bit shift, and thus is easily realized by a circuit. be able to. For the remaining 2 ^{(−r / q)} , the calculation can be omitted by previously collecting the calculation results in a lookup table. That is, when the value of r is known, the value of 2 ^{(−r / q)} can be obtained by referring to the lookup table.

That is, q which is an integer satisfying the following formula is obtained.
(Equation 3)
2 ^{(−1 / q)} ≦ λ _max / 2
Then, for a given y and q, Q and r (integer) satisfying the following expression are obtained. Incidentally, Q and r depend on the time point k, but q does not.
(Equation 4)
y = Q · q + r
Here, 0 ≦ r ≦ q−1.
Then, the above weight system is calculated using λ ₀ = 2 · 2 ^{(−1 / q)} instead of λ _max . At this time, the error between λ _max and λ ₀ is small. For example, if M = 8 and q = 45, it is known that the error is on the order of 10 to the fifth power. Then
(Equation 5)
λ ₀ ^y = 2 ^(yQ) · 2 ^{(−r / q)}
Here, 1/2 <2 ^{(−r / q)} <1,1 <r <q.

2 ^{(−r / q)} can take q values, but is in a range of ½ to 1, and can be calculated in advance and stored in a lookup table. When r is obtained from the equation (4 ^), a value of 2 ^{(−r / q)} can be obtained using this lookup table. Since 2 ^{( yQ} ) can be easily calculated by bit shift, (λ ₀ ) ^Nk that is well approximated to (λ _max ) ^Nk can be calculated by the floating point method.

According to the present embodiment, if q and 2 ^{(−r / q)} are obtained and stored in advance for a certain state transition matrix T, λ _max can be easily calculated. Further, it is easy to calculate and store eigenvectors in advance, and the storage is not difficult. Therefore, since the weight W _k can be calculated for each state transition, the capacity of the storage element for storing the weight W _k for each state can be reduced. In other words, in the counting method, encoding and decoding of a large numerical value such as N = 4000 can be realized by the present invention.

  Hereinafter, two embodiments of the decoding method of the present invention will be described. In this embodiment, a code c having a code length N set including redundant bits under a predetermined constraint condition (for example, an RDS constraint condition of M = 2) is converted into n-bit original data (source data). (FIG. 2).

[Decryption from left to right]
FIG. 9 is a flowchart showing the operation of the left-to-right algorithm of the decoding apparatus according to this embodiment.

First, in S21, as initialization, the index I is set to 0, the time point k is set to 0, and the state is set to S ₀ (0). The RDS value s is zero.

  In S22, it is determined whether or not the corresponding numerical value c (k + 1) in the input code is “1”. If it is “1”, the process proceeds to S23, and if it is not “1”, the process proceeds to S24.

In S23, the state S _k is shifted to the state S _{k + 1} along the path in the direction in which the RDS increases (s becomes s + 1), and the weight W _{k + 1} (s−1) of the state following the path in the direction in which the RDS decreases. Is added to the index I.
(Equation 6)
I = I + W _{k + 1} (s−1)

In S24, it shifts to state _{S k + 1} along the direction of the path reduces the state _{S k} is RDS (s becomes s-1). The index I maintains the current value (I = I).

  In S25, the time point k is advanced by 1, and it is determined whether k obtained by adding 1 is equal to or less than (N−1). If it is (N-1) or less, the process returns to S22, and if it is greater than (N-1), the decoding process is terminated.

  In this way, the path through which the state S transitions on the trellis diagram during encoding can be specified based on the individual numerical values (0 or 1) in the code to be decoded. Therefore, according to the present embodiment, it is possible to calculate the decimal index I of the original data i for the code based on the path where the state S transitions. Then, by predetermining the relationship between possible values of the input data and their decimal indexes, the correspondence between the index and the code can be determined by calculation, and the code can be decoded into the original data. In such a manner, a lookup table for storing the correspondence between the index and the code becomes unnecessary.

Here, this weight integration will be described with reference to the trellis diagram of FIG. 4 as an example in which the code c1 = (0011100111) is input. In the inputted code c1, since the first two numerical values are 0, I = 0 remains. The third value is 1, but the value of W ₃ (−3) becomes zero as described above, and therefore I = 0. The fourth value is also 1, and the state is S ₄ (0). Since this state S ₄ (0) is the starting point and the weight W ₅ (−1), which is the number of paths that continue in the direction in which RDS decreases, is 18, this is integrated as the number of paths that were truncated at time 4. When this is performed one after another, I is accumulated as 35 (time point 5), 39 (time point 8), 41 (time point 9), and finally it can be seen that I = 41 until time point 9. The fact that this index is 41 indicates that it is the 42nd code of the original data, so that it can be decoded into the original data.

  Then, the index calculation unit 214 sets the calculated weight integrated value to the index I, and converts the index I to the original data i based on a predetermined relationship between the original data i and the index I. ,Output. In the present embodiment, since the index I is a decimal conversion value of the original data i, the original data i is directly related to the index I.

In the second embodiment described above, the weight W, which is the number of paths that have been truncated by specifying a path from the head to the tail of the code and making the state transition along the path in the direction in which the RDS decreases. _{k + 1} (s-1) was integrated. The decoding can be executed not only by such a method but also by specifying a path from the tail of the code toward the head. A decoding method according to the third embodiment, in which a path is selected from the tail of the code toward the head, will be described below.

  FIG. 10 is a block diagram of a decoding device for executing the second embodiment.

The state update unit 211 receives the code c, and specifies the path on which the state transitions on the trellis diagram (FIG. 4) according to the individual numerical value 0 or 1 in the input code c. The weight calculation unit 212 calculates the weight W _k (s) of the state S _k (s) at the time point k. In the present embodiment, the weight calculation unit 212 calculates the weight W _k (s) for each state S _k (s) on the trellis diagram. The parameter setting unit 221 that supplies necessary data to the weight calculation unit 212 is provided. The parameter setting unit 221 includes a transition matrix generation unit 225, an eigenvector calculation unit 226, and a maximum eigenvalue calculation unit 227. The parameter setting unit 221 has the same configuration as the parameter setting unit 121 (FIG. 1) of the encoding device according to the first embodiment, and is not necessarily included in the device of the present invention, as in the case of the first embodiment. It is a part that is not necessary.

The index calculation unit 214 obtains the weights W _{k + 1} (s + 1) and W _{k + 1} (s−1) of the states following the path that is truncated by changing the state according to the path specified by the state update unit 211, and calculates this for each time point. Accumulate. Here, this weight integration will be described with reference to the trellis diagram of FIG. 4 as an example in which the code c1 = (0011100111) is input. In the input code c1, the state at the present moment 4 is S ₄ (s) = S ₄ (0). Since the numerical value in the code c1 corresponding to the current point 4 is “1”, the weight W ₅ (−1) = 18, which is the number of paths that continue in the direction in which RDS decreases starting from this state S ₄ (0), is set. This is integrated as the number of paths that were truncated at time 4. This is performed for the next time point, and the number of rounds calculated for each time point is integrated.

  Then, the output unit 215 sets the calculated weight integrated value to the index I, converts the index I into the original decoded data i based on a predetermined relationship between the decoded data i and the index I, and outputs To do. In the present embodiment, since the index I is a decimal conversion value of the original data i, the original data i is directly related to the index I. As described above, here, the index is displayed in decimal. However, this is for the purpose of explanation, and in the actual calculation, the numerical value in the binary system may be used. Can be omitted.

In the present embodiment, in calculating the weight integrated value, the number of paths to be rounded down by selecting a negative path is integrated, so that the calculated weight integrated value can be substituted for the index I. In other words, the weight integrated value calculated in the present embodiment is equal to the index I. However, it is also possible to calculate the index I by accumulating the number of paths that are discarded by selecting the positive path. In that case, the minus the weight accumulated value from the weight W ₀ of the state at time 0 as an index I, is converted into the original data i.

[Decoding from right to left]
FIG. 11 is a flowchart showing the steps of a right-to-left decoding algorithm according to the third embodiment of the present invention. First, it is necessary to obtain the state Sf at the right end point. This state Sf can be determined from the sign. For example, if the code is c = (c (1) c (2) c (3)... C (f)), +1 is associated with 1 of each code value, and −1 is associated with 0, By taking the sum, RDS can be calculated. By taking the sum of +1 and −1 corresponding to code values c (1) to c (f), the value of RDS at Sf can be obtained, and this is set as the value of s in the final state (step S30). . In S31, as initialization, the index I is set to 0, the time point k is set to N, and the state at the final time point is set to Sf.

In S32, from the value of c (k), it is determined from which state S _k-1 (s ′) of the previous time the state S _k (s) at the current k has transitioned.

  In S33, it is determined whether or not the corresponding numerical value c (k) in the input code is 1. When it is 1, it progresses to S34, and when it is not 1, it progresses to S35.

In S34, the state s is changed to the state s ′ at the previous time point, and the weight W _k (s′−1), which is the number of paths that are truncated by changing the state from s ′ to s, is indexed. Add to I.
(Equation 7)
I = I + W _k (s′−1)

  In S35, the state s is transitioned to the previous state s'. The index I maintains the current value (I = I).

  In S36, the time point k is returned to the previous one, and it is determined whether or not k obtained by subtracting 1 is 1 or more. When it is 1 or more, the process returns to S33, and when it is smaller than 1, the decoding process for data i is terminated.

According to this embodiment, the weight W _k can be set by calculation, and decoding can be performed by reusing the calculation result such as the maximum eigenvalue λ calculated at the time of conversion to the code. The circuit configuration can be simplified. In the case of the above left-to-right decoding algorithm, when calculating I = I + W _{k + 1} (s−1), the value of W _{k + 1} at time k = 0 is very large due to (λ _max ) ^Nk . The size of the wear increases. The right-to-left decoding algorithm has the advantage that the hardware size can be reduced.

  According to the present invention, as another embodiment, in order to increase the processing speed during encoding and decoding, the input signals are parallelized and m bits ( It is also possible to encode or decode m> 1) simultaneously (this is called high-radix). In this case, the shape of the transition matrix T changes accordingly, but the encoding or decoding method itself does not change.

DESCRIPTION OF SYMBOLS 111 ... Index calculation part, 112 ... Comparison / output part, 113 ... Weight calculation part, 115 ... State update part, 121 ... Parameter setting part, 125 ... Transition matrix generation part, 126 ... Eigen vector calculation part, 127 ... Maximum eigenvalue calculation part , 211 ... state update unit, 212 ... weight calculation unit, 213 ... weight storage unit, 214 ... index calculation unit, 215 ... output unit, 221 ... parameter setting unit, 225 ... transition matrix generation unit, 226 ... eigenvector calculation unit, 227 ... Maximum eigenvalue calculation part.

Claims (8)

An encoding method for converting n-bit input data into an N-bit code including redundant bits under a predetermined constraint condition,
receiving n-bit data and performing initialization;
An index determination step for determining an index for the received n-bit data;
In the trellis diagram determined under the constraint conditions, the total number of paths that can be taken to reach the end point in the trellis diagram when a state at the next time point is defined as the start point is defined as the weight of the state at the next time point. A weight calculation step for numerically calculating the weight or a value approximate thereto,
A path that is determined by selecting one of a plurality of paths that continue from the current state based on the index and the weight of the state at the next time point or a value that approximates the state transition from the current time point to the next time point A decision step;
A symbol value determining step for determining a symbol value of a code with a value assigned in advance to the determined path;
A normalization step for normalizing the index if the path meets a predetermined condition based on the determined path;
A state update step for updating the state by transitioning the state to the next time point according to the path determined in the path determination step;
A repetition step of repeating N times from the weight calculation step to the state update step;
And a code output step of outputting the sequence of numerical values determined in the determination step as a code. A decoding method for decoding a code encoded with redundant bits under a predetermined constraint condition into original n-bit data,
Receiving a code and initializing;
In the trellis diagram determined under the constraint conditions, a path that specifies a path whose state advances one point to the right on the trellis diagram according to the symbol value of the bit corresponding to each time point included in the code Specific steps,
In the trellis diagram, the number of paths up to all possible end points when a state at time k is the start point is defined as the weight of the state at that time k. A weight calculation step for numerically calculating the weight of the state following the path that is truncated when the numerical value in the value is a predetermined value or a value approximate thereto;
An index addition step of adding the truncated weight or a value approximate thereto to the index when there is a truncated weight;
A state update step for updating the state by transitioning the state to the next time point according to the path selected in the path determination step;
An index integrated value calculating step for repeating all the symbol values included in the code from the path specifying step to the state updating step;
Determining the calculated index value as an index of the original data, and outputting the original data based on a predetermined relationship between the original data and the index. Decryption method. A decoding method for decoding a code encoded with redundant bits under a predetermined constraint condition into original n-bit data,
Receiving a code;
In the trellis diagram defined under the constraint conditions, based on the code, determining a final state corresponding to the code;
An initialization step of setting the index to zero, starting from the final state;
A path specifying step for specifying a path whose state returns one time point to the left on the trellis diagram according to a symbol value of a bit corresponding to each time point included in the code;
In the trellis diagram, the total number of paths up to all possible end points when a state at time k is set as the start point is defined as a weight of the state at that time k. A weight calculation step for numerically calculating a weight of a state following a path that is rounded down when a point in time is returned or a value approximate thereto, by the numerical value in
An index addition step of adding the value of the truncated weight or an approximate value to the index only when there is a truncated weight or an approximate value thereof;
A state update step for updating the state by transitioning the state to a previous time point according to the path determined in the path specifying step;
An index integrated value calculating step for repeating all the symbol values included in the code from the path specifying step to the state updating step;
Determining the integrated value of the calculated index as an index of the original data, and outputting the original data based on a predetermined relationship between the original data and the index. How to be. In weight calculation step, determined by calculating the value of power of 2 I by the performing a bit shift are calculated already associated with the maximum eigenvalue of the transition matrix corresponding to the trellis diagram is stored in the storage means Using a lookup table containing the calculated values, and without performing a power calculation anew each time the weight is calculated, determine a value of a power of 2 and the resulting power of 2 and a further power of 2 using power values and the value of each component of eigenvectors of the transition matrix a method according to any one of claims 1 to 3, characterized that you obtained by calculation numerical weights or values approximating that . An encoding device for converting n-bit input data into an N-bit code including redundant bits under a predetermined constraint condition,
an index calculation unit that accepts n-bit data, performs initialization, and calculates an index indicating a rank in the data series for the data;
In the trellis diagram determined under the constraint conditions, the total number of paths that can be taken to reach the end point in the trellis diagram when a state at the next time point is defined as the start point is defined as the weight of the state at the next time point. A weight calculation unit for numerically calculating the weight or a value approximate thereto,
The transition of the state from the current time point to the next time point is determined by selecting any one of a plurality of paths continuing from the current state based on the index and the weight of the next time point state or a value approximate thereto, A comparison / output unit that determines a value assigned in advance to the determined path as a symbol value of the code, and normalizes the index when the path meets a predetermined condition based on the determined path;
A state update unit that changes the state to the next time point according to the determined path and updates the state, and
An encoding apparatus that repeats N times from weight calculation to state update. A decoding device that decodes a code encoded with redundant bits under a predetermined constraint condition into original n-bit data,
Accepts the code, initializes it, and in the trellis diagram determined under the constraint condition, the state is shown on the trellis diagram according to the symbol value of the bit corresponding to each time point included in the code. A state update unit that identifies a path that advances to one point in time and updates the state;
In the trellis diagram, the total number of paths up to all possible end points when the state at the time point k is set as the start point is defined as the weight of the state at the time point k. A weight calculation unit that numerically calculates a weight of a state following a path that is truncated when the numerical value is a predetermined value, or a value approximate thereto,
An index calculation unit that adds a truncated weight or an approximate value to the index when there is a truncated weight or an approximate value;
A decoding device that repeats index calculation from state update for all symbol values included in a code, and outputs original data based on an integrated value of a final index. A decoding device that decodes a code encoded with redundant bits under a predetermined constraint condition into original n-bit data,
In a trellis diagram that accepts a code and is determined under the constraint condition, a final state specifying unit that specifies a state at the final time point based on the code and performs initialization,
In the trellis diagram, a state update unit that performs state update by identifying a path whose state returns to the left by one point on the trellis diagram in accordance with a symbol value of a bit corresponding to each time point included in the code When,
In the trellis diagram, the total number of paths up to all possible end points when the state at the time point k is set as the start point is defined as the weight of the state at the time point k. A weight calculation unit that numerically calculates a weight of a state following a path that is truncated when the numerical value is a predetermined value, or a value approximate thereto,
An index calculation unit that adds a value of the truncated weight to the index when there is a truncated weight;
A decoding device that repeats index calculation from state update for all symbol values included in a code, and outputs original data based on an integrated value of a final index. Weight calculator is determined by calculating the value of power of 2 I by the performing a bit shift are calculated already associated with the maximum eigenvalue of the transition matrix corresponding to the trellis diagram is stored in the storage means Using a lookup table containing the calculated values, and without performing a power calculation anew each time the weight is calculated, determine a value of a power of 2 and the resulting power of 2 and a further power of 2 apparatus according to any one of power of using the value of each component of eigenvectors of values and the transition matrix, 5 to claim, characterized that you obtained by calculation numerical weights or values approximating that 7 .

Images