[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

WO2011048997A1 - 軟出力復号器 - Google Patents

軟出力復号器 Download PDF

Info

Publication number
WO2011048997A1
WO2011048997A1 PCT/JP2010/068021 JP2010068021W WO2011048997A1 WO 2011048997 A1 WO2011048997 A1 WO 2011048997A1 JP 2010068021 W JP2010068021 W JP 2010068021W WO 2011048997 A1 WO2011048997 A1 WO 2011048997A1
Authority
WO
WIPO (PCT)
Prior art keywords
soft output
processing unit
backward
code
memory
Prior art date
Application number
PCT/JP2010/068021
Other languages
English (en)
French (fr)
Inventor
利彦 岡村
Original Assignee
日本電気株式会社
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 日本電気株式会社 filed Critical 日本電気株式会社
Publication of WO2011048997A1 publication Critical patent/WO2011048997A1/ja

Links

Images

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/3905—Maximum a posteriori probability [MAP] decoding or approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm, log-MAP decoding, max-log-MAP decoding

Definitions

  • the present invention relates to soft output decoding, and more particularly, to reduction of load due to processing related to error correction processing at the time of decoding.
  • the error correction coding technique is a technique for protecting data from errors such as bit inversion occurring on a communication path during data transmission through operations such as data coding and decoding.
  • Encoding is an operation of converting information to be transmitted into a codeword with redundancy added.
  • Decoding is an operation of estimating the original codeword (information) from the codeword (received word) in which an error is mixed using the redundancy.
  • This technology has already been widely used in communications and storage media, especially in speeding up wired communications such as wireless communications or ADSL (Asymmetric Digital Subscriber Line), or increasing the capacity of storage media such as optical disks. It is an indispensable technology.
  • decoding is a process of estimating an original codeword, and a plurality of methods can be considered even if the same code is used.
  • the decoding result is given as a code word or an information bit string for generating it, but a decoding method for estimating each information bit with a weight with respect to a received sequence is also known. This is called a soft output decoding method.
  • Optimal soft-output decoding is decoding that outputs a conditional probability of the information bit or symbol based on the received sequence for the code word under the constraint that the bit string constitutes the code word for each information symbol. . This is called posterior probability decoding.
  • a posterior probability decoding method with a relatively small amount of calculation is known in decoding processing, particularly in decoding of a code that can be represented by a code trellis with a small number of states.
  • This method can be logically realized as a process on a code trellis, similarly to Viterbi decoding known as a maximum likelihood decoding method of a convolutional code.
  • This method is called BCJR (Bahl, Cocke, Jelinek, Raviv) algorithm or MAP (Maximum A Posteriori probability) algorithm described in Non-Patent Document 1.
  • the input received word Y is not a hard decision result in which each bit is determined to be 0 or 1, but a value obtained by adding reliability to the determination of each bit, that is, a soft decision result (soft input value). It can be a decoding method. For this reason, this method is also called a soft input / soft output decoding method.
  • This technique is an important element in the decoding of the turbo code described in Non-Patent Document 2.
  • Non-Patent Document 2 for ease of explanation, a case where a symbol is a binary code will be described. However, the present invention can be extended to a case where a symbol is composed of multi-level symbols.
  • FIG. 22 is an explanatory diagram showing the structure of a general turbo encoder 900 and decoder 1000.
  • a turbo encoder 900 shown in FIG. 22A is configured by connecting two systematic convolutional encoders 901 and 902 having feedback via an interleaver 903 in parallel.
  • This convolutional code is called an element code of a turbo code, and a code having 4 or less memories is usually used.
  • FIG. 22 shows an example in the case of 2 memories.
  • the convolutional encoder 901 includes two memories 901a and 901b and three adders 901c and 901e.
  • the convolutional encoder 902 is composed of two memories 902a-b and three adders 902c-e.
  • the convolutional encoder 901 is referred to as element code 1 and 902 as element code 2, and the parity sequences generated by them are referred to as parity 1 and parity 2, respectively.
  • Interleaver 903 rearranges the output bits from convolutional encoders 901 and 902. The size and design of the interleaver 903 greatly affects the encoding performance.
  • a turbo decoder 1000 shown in (b) of FIG. 22 corresponds to soft input / soft output decoding means 1001 corresponding to the element code output from the turbo encoder 900, and corresponds to the information sequence, parity 1, and parity 2, respectively. And memories 1012, 1013, and 1014 that hold received values.
  • the turbo code decoding method is to use a soft output value obtained by soft output decoding of one element code as a soft input value (preliminary information) of the other element code and repeat this.
  • the soft output value exchanged in the process of this repetition is not the value L (t) of Equation 1 but a value Le (t) called external information represented by Equation 2 calculated from L (t). .
  • y (t) is a received value for information bit u (t)
  • La (t) is a soft output value obtained by soft output decoding of the other element code used as prior information of u (t)
  • C is It is a constant determined according to the SN ratio of the communication path.
  • the processing of the interleaver 1003 and the deinterleaver 1016 is realized as memory address generation processing.
  • the above MAP algorithm (BCJR algorithm) will be described in detail.
  • the MAP algorithm is an algorithm using a code trellis as in the Viterbi algorithm well known as the maximum likelihood decoding method.
  • the code word for the input information changes according to the value of the memory in the encoder. This memory value in the encoder is called the “state” of the encoder. Coding using a convolutional code is performed while changing the state according to the information sequence.
  • the code trellis is a graph representing a combination of transitions of this state, and is configured by assigning an edge to a pair of states where a transition exists, with each state of the encoder at each point as a node.
  • the edge is determined by input information in each state, and the code word at that time is assigned as a label.
  • the connection of edges is called a path, and a codeword sequence corresponds to the path.
  • the state of all transmitted data is related to the state before and after that. For this reason, if a code trellis is used, an error occurring in the transmission path can be corrected with higher accuracy.
  • a time-invariant convolutional code has a feature that has a trellis structure that is invariant with respect to a point in time. Therefore, if the number of states is small, it is easy to execute an algorithm using a code trellis.
  • FIG. 23 is an explanatory diagram showing a more detailed configuration of the turbo encoder 900 shown in FIG.
  • FIG. 23A shows a convolutional code (number of memories 2) of the element code shown in FIG. 22, and FIG. 23B shows a corresponding code trellis.
  • the initial state is that all the values of the memories 1012 to 1014 are 0, and the encoder state is expressed by a series of memory bits.
  • the convolutional encoder 901 shown in FIG. 23A is composed of the two memories 901a and 901b and the three adders 901c and 901e as described above.
  • the MAP algorithm is roughly divided into a forward process for calculating a path metric that reaches each node from the head of the code trellis, a backward process for calculating a path metric that reaches each node from the end of the code trellis, and the results of both.
  • the soft output generation process for calculating the soft output (posterior probability ratio) of the information symbol at each point of time, and the above three types of processes.
  • the path metric in forward processing relatively represents the logarithmic value of the probability of reaching each node from the top of the trellis under the received sequence and prior information.
  • the path metric in backward processing relatively represents the logarithmic value of the probability of reaching each node from the end of the trellis.
  • path metrics calculated by forward processing and backward processing at nodes at time t and state s are represented by ⁇ ( t, s) and ⁇ (t, s).
  • the transition at the time t from the state s to the state s ′, calculated from the received value and prior information (soft output of the other element code in the case of a turbo code) by ⁇ (t, s, s ′) Represents a branch metric corresponding to a probability.
  • This can be calculated as the likelihood between the codeword corresponding to the transition from s to s ′ and the received value, and ⁇ (t, s, s ′) is the transition from s to s ′ in the white Gaussian channel. It can be easily calculated using the Euclidean distance between the modulation value and the reception value of the output codeword and the prior information on the information bits.
  • Equation 3 represents forward processing
  • Equation 4 represents backward processing
  • Equation 5 represents soft output generation processing
  • Equation 3 An algorithm that improves the MAP algorithm and performs the processing shown in Equations 3 to 5 by changing the calculation of the sum by an operation that takes the maximum value is referred to as a Max-Log-MAP algorithm.
  • Equation 3 is simplified as shown in Equation 6 in the Max-Log-MAP algorithm.
  • a correction value for the result of Expression 6 is obtained by referring to the table from the path metric difference value compared in Expression 6.
  • An algorithm to be calculated is described in Non-Patent Document 3, and this is called a Log-MAP algorithm.
  • FIG. 24 is an explanatory diagram showing the order of forward processing, backward processing, and soft output generation processing performed by the MAP algorithm (or Max-Log-MAP algorithm). If the forward processing ⁇ and the backward processing ⁇ are not prepared at each time point, the soft output generation processing is impossible.
  • backward processing is performed from the end of the code trellis to generate ⁇ at each time point (time T1), and then forward processing and soft output generation processing are performed from the beginning of the trellis (time T2). ) Shows an example of a simple scheduling process.
  • FIG. 24 (b) shows an example of a scheduling process for improving this defect, dividing the trellis into blocks at the time point of size W, and performing backward processing, forward processing, and soft output generation processing for each block. .
  • backward processing is performed on the block W1.
  • backward processing is performed on the block W2 while performing forward processing and soft output generation processing on the block W1.
  • the backward process is performed on the block W3 while the forward process and the soft output generation process are performed on the block W2. Thereafter, the processing is continued in the same manner.
  • Non-Patent Document 3 describes a technique called radix-2 ⁇ n that improves this drawback.
  • radix-2 ⁇ n is a technique of reducing the number of cycles and increasing the speed by performing forward processing, backward processing, and soft output generation processing for n time points in one cycle.
  • n is an integer of 2 or more.
  • Radix-2 ⁇ n has not only the effect of speeding up, but also the effect of reducing the power consumption of the decoding device because the clock frequency can be lowered by reducing the number of cycles if the throughput is the same.
  • Non-Patent Document 3 describes simplification by approximation processing based on the Log-MAP algorithm using table references in equations 7-8.
  • FIG. 25 is an explanatory diagram showing a trellis representing transitions for two time points of time points 2t and 2 (t + 1) in the convolutional encoder with two memories shown in FIG. Time point 2t and time point 2 (t + 1) are indicated by ⁇ , and the time point (2t + 1) in between is indicated by ⁇ .
  • FIG. 26 is an explanatory diagram showing the backward processing unit 1100 in soft output decoding by radix-4 shown in equations 7-9.
  • the backward processing unit 1100 performs scheduling for storing the backward processing path metric as shown in FIG. As many path metrics as the number of states are generated for even time points.
  • the backward processing unit 1100 includes a two-time backward processor 1102 that executes the processing shown in Equation 8 and a register 1103 that temporarily stores ⁇ every two time points. At the same time, a branch metric memory 1101 for storing the branch metric ⁇ and a path metric memory 1104 are provided.
  • the branch metric memory 1101 uses the branch metrics ⁇ for two time points in one cycle of processing. ⁇ every two points stored in the register 1103 is also held in the path metric memory 1104 until the generation of the soft output is completed.
  • the register 1103 holds the number of path metrics corresponding to the number of states.
  • FIG. 27 is an explanatory diagram showing a forward processing / soft output generation unit 1200 in soft output decoding by radix-4 shown in equations 7 to 9.
  • the forward processing / soft output generation unit 1200 performs forward processing / soft output generation processing as shown in FIG. 24A in radix-4, and simultaneously executes forward processing and soft output generation processing. Is.
  • the forward processing / soft output generation unit 1200 executes a two-time forward processor 1202 that executes the processing shown in Expression 7, a register 1203 that temporarily stores ⁇ every two time points, and a processing shown in Expression 9. And a two-time soft output generation processor 1204.
  • the branch metric memory 1101 for storing the branch metric ⁇ and the path metric memory 1104 are the same as those shown in FIG.
  • the branch metric memory 1101 uses the branch metrics ⁇ for two time points in one cycle of processing.
  • the 2-time soft output generation processor 1204 generates a soft output from ⁇ and ⁇ at time t and from ⁇ at time t and t + 1.
  • Patent Document 1 describes a soft output decoding device that reduces the amount of calculation by performing in parallel the processing within the truncation length and processing that goes back beyond the truncation length.
  • Patent Document 2 describes a Viterbi decoding apparatus that reads out surviving path information from only the bank corresponding to the state having the maximum likelihood metric, performs traceback, and does not read out other unnecessary surviving path information. ing.
  • Patent Document 3 describes a soft output decoding apparatus that can reduce the number of repetitions of decoding processing by including local soft input / soft output decoding means capable of local input / output of element codes.
  • Patent Document 4 describes a soft output decoding device in which a circuit scale is reduced by providing a memory capable of simultaneously writing and reading data.
  • Non-Patent Documents 1 to 4 and Patent Documents 1 to 4 cannot be said to be sufficient in this respect, and the above-described problems cannot be solved.
  • An object of the present invention is to provide a soft output decoder capable of performing soft output generation processing in soft output decoding by radix-2 ⁇ n at high speed with a simple circuit configuration.
  • a soft output decoder is a soft output decoder that receives an encoded and transmitted bit stream, decodes the bit stream, and outputs the decoded bit stream to the outside.
  • Received value memory for storing, branch metric generating means for generating a branch metric for each time point in the trellis diagram based on the contents stored in the received value memory, and soft output including the posterior probability ratio by decoding the branch metric
  • a soft output decoding means for outputting a code
  • a hard output determining means for converting the soft output code into a hard output code not including a posteriori probability ratio and outputting the hard output code to an upper layer.
  • a backward processing unit that estimates a path metric that reaches the node, a forward processing unit that estimates a path metric that reaches each node from the top of the branch metric code trellis stored in the branch metric memory, and a backward processing
  • a path metric memory for storing the estimation processing results by the processing unit, and calculating the posterior probability ratio of the information symbols at each time point from the estimation processing results by the backward processing unit and the forward processing unit, and outputting this as a soft output code And a soft output generation processing unit.
  • the backward processing unit includes a plurality of backward processors connected to each other and corresponding to the estimation processing for each time point of the code trellis.
  • a path metric memory is provided in each backward processor. Featuring multiple corresponding storage areas .
  • the path metric for each time point is stored in the path metric memory, and the decoding process is performed on the basis of the path metric memory. Therefore, the decoding device does not require a complicated circuit configuration, and speeding up is easy. Thus, it is possible to provide a soft output decoder having an excellent feature that a decoding process based on a code trellis can be performed at high speed with a simple circuit configuration.
  • FIG. 5 is an explanatory diagram showing a configuration of a backward processing unit in which the configuration of the backward processing unit shown in FIG. 4 is expanded for a general radix-2 ⁇ n (n is an integer of 2 or more).
  • the configurations of the forward processing unit and the soft output generation processing unit shown in FIG. 5 are expanded for the general radix-2 ⁇ n (n is an integer of 2 or more).
  • FIG. 18 is an explanatory diagram showing a more detailed configuration of the backward processing unit shown in FIG.
  • FIG. 19 is an explanatory diagram showing in more detail the configuration for the state “00” of the configuration of the first one-time backward processor shown in FIG. 18;
  • FIG. 20 is an explanatory diagram showing a more detailed configuration of the forward processing unit and the soft output generation unit shown in FIG.
  • FIG. 20 is an explanatory diagram showing the configuration of the first soft output generation processor shown in FIG. 19 in more detail.
  • FIG. 22A shows a turbo encoder
  • FIG. 22B shows a turbo decoder
  • FIG. 23A shows a convolutional encoder (number of memories 2) of the element code of FIG. 22, and
  • FIG. 23B shows a corresponding code trellis.
  • FIG. 24 (a) shows an example of a simple scheduling process
  • FIG. 24 (b) shows an example of a scheduling process in which the drawbacks are improved.
  • FIG. 25 is an explanatory diagram showing a trellis representing transitions for two time points of time points 2t and 2 (t + 1) in the convolutional encoder with two memories shown in FIG.
  • FIG. 10 is an explanatory diagram showing a backward processing unit in soft output decoding by radix-4 shown in equations 7-9.
  • FIG. 10 is a block diagram of a forward processing / soft output generation unit in soft output decoding by radix-4 shown in equations 7-9.
  • the soft output decoder 10 is a soft output decoder that decodes a bit stream and outputs the decoded bit stream to the outside.
  • This soft output decoder 10 includes received value memories 101 to 103 for storing a bit stream and branch metric generating means 105 for generating a branch metric for each time point in the trellis diagram based on the contents stored in the received value memory.
  • a soft output decoding unit 110 that decodes the branch metric and outputs a soft output code including the posterior probability ratio; and a hard output determination that converts the soft output code into a hard output code that does not include the posterior probability ratio and outputs the same to the outside Means 106.
  • the soft output decoding means stores a branch metric memory 150 that temporarily stores a branch metric, a backward processing unit 120 that estimates a path metric that reaches each node from the end of a code trellis of the stored branch metric, and A forward processing unit 130 for estimating a path metric reaching each node from the head of the code trellis of the branch metric, a path metric memory 160 for storing a result of estimation processing by the backward processing unit, a backward processing unit and a forward A soft output generation processing unit 140 that calculates a posteriori probability ratio of the information symbols at each time point from the estimation processing result by the processing unit and outputs the information symbol as a soft output code.
  • the backward processing unit is connected to each other and includes a plurality of backward processors 121 to 122 corresponding to the estimation processing for each time point of the code trellis, and the path metric memory 160 includes a plurality of backward processors corresponding to each of the backward processors.
  • Storage areas 161 to 162 are provided.
  • this backward processing unit and forward processing unit perform path metric estimation processing for a plurality of time points for one cycle.
  • the forward processing unit includes a plurality of forward processors 131 to 132 that are connected to each other and correspond to estimation processing for each time point of the code trellis.
  • the path metric memory 160 includes a plurality of storage areas 161 to 162 corresponding to each of the forward processors, and the soft output generation processing unit is based on the estimation processing result by the backward processing unit and the forward processing unit stored in the path metric memory. A posteriori probability ratio of information symbols at each time point is calculated.
  • the soft output decoder 10 can perform the decoding process based on the code trellis at high speed with a simple circuit configuration. Hereinafter, this will be described in more detail.
  • FIG. 2 is an explanatory diagram showing a configuration of a transmission system 1 including a turbo code decoder 10 which is a soft output decoder according to the first embodiment of the present invention.
  • the transmission system 1 shown in FIG. 2A includes an antenna 20 that receives radio signals by wireless communication, a demodulator 30 that extracts a bit stream from the radio signals received by the antenna 20, and an extracted bit stream.
  • the turbo code decoder 10 performs error correction and decoding.
  • the antenna 20 shown in FIG. 2A may be replaced with a wired transmission system such as ADSL. Further, as shown in FIG. 2B, the antenna 20 may be replaced with an optical pickup 20a that reads recorded data from a storage medium such as an optical disk. That is, the turbo code decoder 10 can be widely applied to all uses for decoding a bitstream.
  • the bit stream output from the demodulator 30 to the turbo code decoder 10 includes an information reception value and first and second parity reception values.
  • FIG. 1 is an explanatory diagram showing the configuration of the turbo code decoder 10 according to the present embodiment shown in FIG.
  • the turbo code decoder 10 includes an information reception value memory 101 for storing the reception value from the demodulator 30, first and second parity reception value memories 102 and 103, and an interleaver 104 for generating an interleave output from the information reception value.
  • a branch metric generation unit 105 that generates a branch metric from the information reception value and its interleaved output, the first and second parity reception values, and a soft output decoding unit 110 that decodes the branch metric and outputs a soft output code With.
  • the turbo code decoder 10 also converts the soft output code output from the soft output decoding unit 110 into a hard output code and outputs the hard output code to an upper layer, and generates a deinterleaved output from the soft output code.
  • the branch metric generation means 105 also uses this external information and its interleaved output to generate branch metrics.
  • FIG. 3 is an explanatory diagram showing a more detailed configuration of the soft output decoding unit 110 described in FIG.
  • the soft output decoding unit 110 includes a backward processing unit 120, a forward processing unit 130, a soft output generation processing unit 140, a branch metric memory 150, and a path metric memory 160.
  • the branch metric output from the branch metric generation unit 105 is stored in the branch metric memory 150 and then input to each of the backward processing unit 120, the forward processing unit 130, and the soft output generation processing unit 140.
  • the processing contents of these units will be described later.
  • the content processed by the backward processing unit 120 is stored in the path metric memory 160 and then input to the soft output generation processing unit 140.
  • the soft output generation processing unit 140 generates content that is finally output by the soft output decoding unit 110.
  • the soft output decoding unit 110 is configured to perform processing in the order of backward processing, forward processing, and soft output generation processing as described with reference to FIG. 24.
  • the path metric ⁇ may be generated by first performing forward processing and stored in the path metric memory 160, and then backward processing and soft output generation processing may be performed.
  • the path metric memory 160 has a plurality of storage areas according to the processing stage of the backward processing.
  • ⁇ (t) represents a set of ⁇ (t, s) for all states s at time t. The same applies to ⁇ (t).
  • ⁇ (t) represents a set of all branch metrics at time t.
  • FIG. 4 is an explanatory diagram showing a more detailed configuration of the backward processing unit 120 shown in FIG.
  • the backward processing unit 120 performs two-time backward processing when the present embodiment is applied to radix-4, and includes first and second one-time backward processors 121 and 122, and ⁇ every second time. Is stored temporarily.
  • the path metric memory 160 has first and second path metric storage areas 161 and 162 that hold path metrics generated by the respective one-time backward processors 121 and 122.
  • Each one-time backward processor and 122 may perform the same processing or different processing.
  • the branch metric memory 150 uses the branch metrics ⁇ for two time points in one cycle of processing. When the register 123 holds ⁇ (2 (t + 1)), the backward processing unit 120 completes the next processing in one cycle.
  • the first one-time backward processor 121 uses the equation shown in the above equation 4 using ⁇ (2 (t + 1)) stored in the register 123 and ⁇ (2t + 1) stored in the branch metric memory 150.
  • a metric ⁇ (2t + 1) is generated and stored in the first path metric storage area 161.
  • the second one-time backward processor 122 uses the intermediate path metric ⁇ (2t + 1) generated by the first one-time backward processor 121 and ⁇ (2t) stored in the branch metric memory 150 to ⁇ (2t) is generated by the processing shown, and the register 123 is updated and stored in the second path metric storage area 162.
  • FIG. 5 is an explanatory diagram showing a more detailed configuration of the forward processing unit 130 and the soft output generation processing unit 140 shown in FIG.
  • the forward processing unit 130 performs two-time point forward processing when the present embodiment is applied to radix-4, and includes first and second one-time point forward processors 131 and 132, and these one-time point forward processors 131.
  • And 132 have first and second registers 133 and 134 for temporarily storing intermediate path metrics generated.
  • the soft output generation processing unit 140 performs soft output generation processing when the present embodiment is applied to radix-4, and includes a register 141 that temporarily stores the branch metric memory output from the branch metric memory 150, a path First and second soft output generation processing is performed from the contents stored in the first and second path metric storage areas 161 and 162 of the metric memory 160 and the contents stored in the respective registers 133, 134 and 141.
  • Soft output generation processing processors 142 and 143 are Soft output generation processing when the present embodiment is applied to radix-4, and includes a register 141 that temporarily stores the branch metric memory output from the branch metric memory 150, a path First and second soft output generation processing is performed from the contents stored in the first and second path metric storage areas 161 and 162 of the metric memory 160 and the contents stored in the respective registers 133, 134 and 141.
  • the first one-time forward processing means 131 uses the intermediate path metric by ⁇ 10 (2t) held by the register 133 and ⁇ (2t) input from the branch metric memory 150 by the processing shown in the above-described Expression 10.
  • ⁇ (2t + 1) is generated and stored in the register 134.
  • the second one-time-point forward processing means 132 is based on the intermediate path metric ⁇ (2t + 1) stored in the first path metric storage area 161 in FIG. 4 and ⁇ (2t + 1) input from the branch metric memory 150.
  • ⁇ (2 (t + 1)) is generated by the processing shown in Equation 10 above, and the register 133 is updated.
  • the first and second soft output generation processing processors 142 and 143 each generate a soft output at each of the time points 2t and 2t + 1.
  • the first soft output generation processor 142 calculates the following equation 11 from ⁇ (2t) of the register 133, ⁇ (2t + 1) of the path metric memory 161, and ⁇ (2t) input from the branch metric memory 150.
  • the soft output at time 2t is generated by the processing shown in FIG.
  • the second soft output generation processor 143 calculates the above-described value from ⁇ (2t ⁇ 1) of the register 134, ⁇ (2t) of the path metric memory 161, and ⁇ (2t ⁇ 1) stored in the register 141.
  • the soft output at the time point 2t-1 is generated by the processing shown in equation (11).
  • the register 141 is updated to ⁇ (2t + 1).
  • the security policy creation method is a turbo code decoding method that decodes a bitstream encoded by a turbo code and outputs it to the outside.
  • a bit stream is stored in a reception value memory provided in advance, a branch metric for each time point in the trellis diagram is generated based on the contents stored in the reception value memory, and a code trellis is generated from the end of the branch metric code trellis.
  • the path metric reaching each node is estimated at each point of time, the result of the estimation process from the end of the code trellis is stored in a path metric memory prepared for each point in time, and the head of the branch metric code trellis Is used to estimate the path metric reaching each node at each point in time of the code trellis from the end of the code trellis and calculate the posterior probability ratio of the information symbols at each point of time from the results of the estimation process from the end and beginning of the code trellis. Is a soft output code that includes the posterior probability ratio, and the soft output code is changed to a hard output code that does not include the posterior probability ratio. To output to the outside. With this configuration and operation, the present embodiment has the following effects.
  • This embodiment can realize the soft output decoding algorithm on the code trellis based on radix-2 ⁇ n without increasing the complexity of the soft output generation process. Therefore, it is possible to increase the speed of the operation of the decoder and improve the device scale.
  • the logical depth of the soft output generation processing shown in Equation 5 is two stages of arithmetic additions, There are a total of four stages of max circuits (select one from four metrics each of which is information bits 0 and 1), and the radix-4 soft output generation processing shown in Equation 9 is three stages of arithmetic additions, max circuits There are three stages.
  • the radix-4 soft output generation process remains the two stages of arithmetic addition and the two stages of the max circuit, and the forward process and the backward process also include the two stages of arithmetic addition and the max circuit 2. It becomes a step. That is, according to the present embodiment, the maximum latency can be suppressed to about 2/3 as compared with the normal radix-4, and accordingly, the maximum clock frequency is increased and the operation speed can be increased. it can.
  • FIG. 6 is an explanatory diagram showing a configuration of the backward processing unit 120n obtained by extending the configuration of the backward processing unit 120 shown in FIG. 4 in the case of a general radix-2 ⁇ n (n is an integer of 2 or more). is there.
  • the backward processing unit 120n includes an n-time backward processing unit configured by connecting n one-time backward processors 121a, 121b,... 121n, and a register 123n for temporarily storing ⁇ every n time points.
  • the path metric memory 160 has n path metric storage areas 161a, 161b,... 161n that hold path metrics generated by the respective one-time backward processors 121a to 121n.
  • each processor When the register 123n stores ⁇ (nt), in the next step, each processor generates ⁇ (nt + 1),..., ⁇ (nt + n ⁇ 1), ⁇ (n (t + 1)) and corresponds to each. Stored in the path metric storage areas 161a to 161n. The register 123n is updated by ⁇ (n (t + 1)).
  • FIG. 7 shows a configuration of the forward processing unit 130n and the soft output generation processing unit 140 shown in FIG. 5 in the case of a general radix-2 ⁇ n (n is an integer of 2 or more) and a forward processing unit 130n and a soft processing unit 130n. It is explanatory drawing which shows the structure of the output generation process part 140n.
  • the forward processing unit 130n includes n one-time forward processors 131a, 131b,... 131n and n-1 registers 134a, 134b corresponding to the one-time forward processors 131a to 131n. ... 134 (n-1).
  • the soft output generation processing unit 140n includes n one-time soft output generation processors 142a to 142n that execute the processing shown in Equation 11 above.
  • a correction processing unit 400 is provided between the backward processor and the path metric memory, and the output data of the backward processing is transferred to the non-patent document described above. 3 is corrected based on the Log-MAP algorithm described in No. 3, and then stored in the path metric memory. As a result, the calculation amount and the memory capacity can be reduced while improving the accuracy of the soft output generation process.
  • FIG. 8 is an explanatory diagram showing the configuration of the turbo code decoder 210 according to the second embodiment of the present invention.
  • the configuration of the turbo code decoder 210 is different from the configuration of the turbo code decoder 10 according to the first embodiment described in FIG. 1 only in the internal configuration of the soft output decoding means 110. This is called decryption means 310. All other components are referred to by the same name and reference number.
  • the turbo code decoder 210 performs a decoding process on the turbo code using the Max-Log-MAP algorithm described above.
  • FIG. 9 is an explanatory diagram showing a more detailed configuration of the soft output decoding means 310 shown in FIG.
  • the configuration of the soft output decoding unit 310 differs from the configuration of the soft output decoding unit 110 according to the first embodiment described in FIG. 3 only in the internal configurations of the backward processing unit 120 and the forward processing unit 130. These are referred to as a backward processing unit 320 and a forward processing unit 330. All other components are referred to by the same name and reference number.
  • FIG. 10 is an explanatory diagram showing a more detailed configuration of the backward processing unit 320 shown in FIG.
  • the configuration of the backward processing unit 320 is different from the configuration of the backward processing unit 120 according to the first embodiment described in FIG. 4 only in the first and second one-time backward processors 121 and 122. These are referred to as first and second one-time backward processors 321 and 322, respectively. All other components are referred to by the same name and reference number.
  • FIG. 11 is an explanatory diagram showing a more detailed configuration of the first and second one-time backward processors 121 and 122 shown in FIG.
  • the register 123 holds path metrics for the respective states ⁇ (2t, 00), ⁇ (2t, 10), ⁇ (2t, 01), ⁇ (2t, 11).
  • the first one-time backward processor 321 includes eight arithmetic addition circuits 321a to 321h that add the corresponding values of ⁇ and ⁇ , and max circuits 321i to 321 that compare the numerical values and output the larger numerical value. Composed.
  • the second one-time backward processor 322 also includes eight arithmetic addition circuits 322a to 322h that add the corresponding ⁇ and ⁇ values, and max circuits 322i to 322 that compare the numerical values and output the larger numerical value. It consists of.
  • the first one-time backward processor 321 uses the aforementioned Max-Log-MAP algorithm to store ⁇ (2t ⁇ 1,00), ⁇ (2t ⁇ 1,10), ⁇ held in the branch metric memory 150. For each of (2t ⁇ 1,01), ⁇ (2t ⁇ 1,11) and each numerical value held in the register 123, the processing shown in the following Expression 12 is performed.
  • ⁇ (t, xy) represents a branch metric of the codeword bit string “xy” at time t, and is collectively referred to as ⁇ (t).
  • ⁇ (t, xy) represents the path metric of the codeword bit string “xy” at time t, and is collectively referred to as ⁇ (t).
  • the second one-time backward processor 322 uses the aforementioned Max-Log-MAP algorithm to store ⁇ (2t ⁇ 2,00), ⁇ (2t ⁇ 2,10), ⁇ held in the branch metric memory 150. For each of (2t ⁇ 2,01) and ⁇ (2t ⁇ 2,11) and each numerical value output from the first one-time backward processor 321, the process shown in the above equation 12 is also performed.
  • the path metric storage area 161 generates ⁇ (2t ⁇ 1) by the first one-time backward processor 321, and the path metric storage area 162 generates ⁇ (2t ⁇ 2) by the second one-time backward processor 322. Hold. Register 123 is also updated with ⁇ (2t ⁇ 2).
  • FIG. 12 is an explanatory diagram showing in more detail the configuration for the state “00” of the first one-time backward processor 321 shown in FIG.
  • the first one-time backward processor 321 includes a simple backward processor 410 that performs the process shown in the above-described equation 12 and a correction processing unit 400 described later.
  • the simple backward processor 410 includes the max circuit 322i and adders 322a and 322b shown in FIG. The same applies to states other than “00”.
  • the correction processing unit 400 includes a difference unit 401 that takes a difference value
  • the Log-MAP algorithm realizes the second term on the right side of Equation 14 by referring to the table based on Equation 14 shown below.
  • the table reference unit 402 refers to the table 420 stored in advance, and
  • x ⁇ y for the path metric ⁇ ′ (2t ⁇ 1,00): max (x, y) selected by the max circuit 321i. Based on
  • LUT () is a table reference function.
  • the table 420 may be stored in the first one-time backward processor 321 or may be stored in an external storage device. An output between the table reference unit 402 and the adder 403 is stored in the path metric memory 161.
  • FIG. 13 is an explanatory diagram showing a more detailed configuration of the forward processing unit 330 shown in FIG.
  • the configuration of the forward processing unit 330 is different from the configuration of the forward processing unit 130 according to the first embodiment described in FIG. 4 only in the first and second one-time forward processors 131 and 132.
  • first and second one-time forward processors 331 and 332 are referred to as first and second one-time forward processors 331 and 332. All other components are referred to by the same name and reference number.
  • FIG. 14 is an explanatory diagram showing a more detailed configuration of the first and second one-time forward processors 131 and 132 shown in FIG.
  • the register 133 holds path metrics for the respective states ⁇ (2t, 00), ⁇ (2t, 10), ⁇ (2t, 01), and ⁇ (2t, 11).
  • the first one-time forward processor 331 includes eight arithmetic addition circuits 331a to 331h that add corresponding values of ⁇ and ⁇ , and max circuits 331i to 331 that compare the numerical values and output a larger numerical value. Composed.
  • the second one-time forward processor 332 adds eight arithmetic addition circuits 332a to 332h that add the corresponding ⁇ and ⁇ values, and max circuits 332i to 332 that compare the numerical values and output the larger numerical value. It consists of.
  • the first one-time forward processor 331 uses the aforementioned Max-Log-MAP algorithm to store ⁇ (2t, 00), ⁇ (2t, 10), ⁇ (2t, 01) held in the branch metric memory 150. ), ⁇ (2t, 11) and each numerical value held in the register 133.
  • the path metric memory 161 holds ⁇ (2t + 1) generated by the one-time forward processor 331.
  • the register 133 storing ⁇ at time 2t is updated to ⁇ (2t + 2) in the next cycle.
  • the register 141 stores ⁇ (2t + 1) generated in the process.
  • FIG. 15 is a table showing the forward processing means and soft output generation means shown in FIG. 9, the information stored in each register, the data read from the memory, and the generated soft output at each time point. It is.
  • the branch metric ⁇ (1) at time 0 is used to generate ⁇ (1) and is held in the register 141.
  • L (1) is calculated using ⁇ (1) of register 141 and ⁇ (1) and ⁇ (2) of register 134.
  • the correction processing unit 400 described above can be operated in parallel with the second one-time backward processor 322, the overall processing time is not affected, and the processing speed is not deteriorated. Does not occur. The same applies to the second one-time forward processor 332.
  • the accuracy of the path metric value can be further improved, and at the same time, the output characteristics can be improved.
  • the third embodiment of the present invention further adds a path memory 670 to the first one-time forward processor, and stores an index of a state corresponding to the selected path metric. It is configured to memorize.
  • the max circuit used in the second embodiment can be replaced with a selector, so that the circuit configuration can be further simplified.
  • FIG. 16 is an explanatory diagram showing a configuration of a turbo code decoder 510 according to the third embodiment of the present invention.
  • the configuration of the turbo code decoder 510 differs from the configuration of the turbo code decoder 10 according to the first embodiment described in FIG. 1 only in the internal configuration of the soft output decoding means 110. This is called decoding means 610. All other components are referred to by the same name and reference number.
  • the turbo code decoder 510 performs a decoding process on the turbo code using the Max-Log-MAP algorithm described above.
  • FIG. 17 is an explanatory diagram showing a more detailed configuration of the soft output decoding means 610 shown in FIG.
  • the configuration of the soft output decoding unit 610 differs from the configuration of the soft output decoding unit 110 according to the first embodiment described in FIG. 3 in the internal configurations of the backward processing unit 120 and the soft output generation unit 140. These are referred to as a backward processing unit 620 and a soft output generation unit 640.
  • the forward processing unit 330 is the same as that of the second embodiment described with reference to FIG. Furthermore, a path memory 670 described later is added. All other components are referred to by the same name and reference number.
  • FIG. 18 is an explanatory diagram showing a more detailed configuration of the backward processing unit 620 shown in FIG.
  • the configuration of the backward processing unit 620 is different from the configuration of the backward processing unit 320 according to the second embodiment described above with reference to FIG. 10 only in the first one-time backward processor 321.
  • the one-time backward processor 621 All other components are referred to by the same name and reference number.
  • the first one-time backward processor 621 uses the information stored in the path memory 670 to perform backward processing using ⁇ (2 (t + 1)) to ⁇ (2t + 1) of the path metric memory 161 at the time t.
  • An intermediate metric ⁇ (2t + 1) is generated, and ⁇ (2t) and ⁇ (2t) in the register 133 are combined to generate L (2t).
  • the first one-time backward processor 621 stores, in the path memory 670, an index in a state corresponding to the selected path metric generated in this generation process together with the path metric of the previous time.
  • FIG. 19 is an explanatory diagram showing in more detail the configuration for the state “00” of the configuration of the first one-time backward processor 621 shown in FIG.
  • the first soft output generation processor 621 performs an arithmetic addition circuit 621a that arithmetically adds ⁇ (2t, 00) and ⁇ (2t, 00), and ⁇ (2t, 10).
  • An arithmetic addition circuit 621b that arithmetically adds ⁇ (2t, 11), a comparator 624i that compares outputs from these arithmetic addition circuits 621a and 621b, and a selector that switches an output according to the output from the comparator 624i 621i.
  • the first one-time backward processor 621 has the same configuration except for “00”.
  • the first one-time backward processor 621 stores this in the path memory 670.
  • FIG. 20 is an explanatory diagram showing a more detailed configuration of the forward processing unit 330 and the soft output generation unit 640 shown in FIG.
  • the forward processing unit 330 is the same as that of the second embodiment already described in FIG.
  • the configuration of the soft output generation unit 640 is different from the configuration of the soft output generation unit 340 according to the second embodiment described above with reference to FIG. This is referred to as a soft output generation processor 642. Further, a register 645 described later is included. All other components are referred to by the same name and reference number.
  • the path metric memory 670 requires a much smaller storage capacity than the path metric memory 161.
  • FIG. 21 is an explanatory diagram showing the configuration of the first soft output generation processor 642 shown in FIG. 19 in more detail.
  • the first soft output generation processor 642 passes eight arithmetic addition circuits 642a to 642h for adding the corresponding ⁇ and ⁇ values, and a path metric obtained by arithmetic addition of ⁇ (2t) and ⁇ (2t ⁇ 1). It is composed of selectors 642i to 642l that switch outputs in accordance with the stored contents of the memory 670. By combining the path memory 670 and the selectors 642i to l, the max circuits 322i to l in the second embodiment described in FIG. 11 are substituted.
  • the register 645 temporarily stores ⁇ (2 (t + 1)).
  • the first soft output generation processor 642 uses the information stored in the path memory 670 to perform backward processing using ⁇ (2 (t + 1)) to ⁇ (2t + 1) stored in the register 645 at time t.
  • An intermediate metric ⁇ (2t + 1) is generated, and L (2t) is generated using ⁇ (2t) and ⁇ (2t) stored in the register 123.
  • the path memory 670 since the path memory 670 is added, it is necessary to slightly increase the capacity of the memory as compared with the first and second embodiments described above, but instead, a soft output generation circuit is provided. It can be configured more simply.
  • a soft output decoder that receives a coded and transmitted bitstream, decodes it, and outputs it to the outside.
  • a reception value memory for storing the received bitstream; branch metric generation means for generating a branch metric for each time point in the trellis diagram based on the contents stored in the reception value memory; and decoding the branch metric Soft output decoding means for outputting a soft output code including a posterior probability ratio, and hard output determining means for converting the soft output code into a hard output code not including a posterior probability ratio and outputting the same to the outside,
  • a branch metric memory that temporarily stores the branch metric, and a backward processing unit that estimates a path metric that reaches each node from the end of a code metric of the branch metric stored in the branch metric memory.
  • a forward processing unit that estimates a path metric that reaches each node from the top of the branch metric code trellis stored in the branch metric memory, and a path metric memory that stores a result of estimation processing by the backward processing unit
  • a soft output generation processing unit that calculates a posteriori probability ratio of the information symbols at each time point from the estimation processing results by the backward processing unit and the forward processing unit and outputs the information symbol as the soft output code.
  • the backward processing unit includes a plurality of backward processors connected to each other and corresponding to the estimation processing for each time point of the code trellis,
  • the soft output decoder wherein the path metric memory comprises a plurality of storage areas corresponding to each of the backward processors.
  • the forward processing unit includes a plurality of forward processors connected to each other and corresponding to the estimation processing for each time point of the code trellis,
  • the path metric memory comprises a plurality of storage areas corresponding to each of the forward processors;
  • the soft output generation processing unit calculates an a posteriori probability ratio of information symbols at each time point from a result of estimation processing by the backward processing unit and the forward processing unit stored in the path metric memory.
  • the soft output decoder according to appendix 1.
  • the backward processing unit performs correction processing based on the Log-MAP algorithm for the path metric stored in the path metric memory by the backward processor that is not the last stage among the plurality of backward processors.
  • the soft output decoding unit includes a path memory in which the backward processor that is not the last stage among the plurality of backward processors stores an index indicating selection information of the path metric,
  • the soft output decoder according to appendix 4, wherein the soft output generation processing unit calculates an a posteriori probability ratio of the information symbol based on the path metric and the index.
  • the present invention can be widely applied to all uses for decoding a bit stream, such as wireless and wired communication, or an optical disc.

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)

Abstract

【課題】復号化処理を簡単な回路構成で高速に行うことを可能とする軟出力復号器を提供する。 【解決手段】　本発明に係る軟出力復号器１０が備える軟出力復号手段１１０は、ブランチメトリックを一時記憶するブランチメトリックメモリ１５０と、このブランチメトリックの符号トレリスの終端からパスメトリックを推定処理するバックワード処理部１２０と、先頭からパスメトリックを推定処理するフォワード処理部１３０と、推定処理の結果を記憶するパスメトリックメモリ１６０と、推定処理の結果から各時点での情報シンボルの事後確率比を算出してこれを前記軟出力符号として出力する軟出力生成処理部１３０とを有すると共に、バックワード処理部が１時点ごとの推定処理に対応する複数個のバックワードプロセッサ１２１～１２２を備え、パスメトリックメモリがその各々に対応する複数の記憶域１６１～１６２を備える。

Description

軟出力復号器
　本発明は軟出力復号化に関し、特に復号化の際の誤り訂正処理にかかる処理による負荷の軽減に関する。
　誤り訂正符号化技術は、データの符号化および復号化という操作を通じてデータ伝送時の通信路上で発生したビット反転等のエラーからデータを保護する技術である。符号化は送信する情報に冗長を付加した符号語に変換する動作である。復号化はその冗長性を利用して、エラーが混入した符号語（受信語）から元の符号語（情報）を推定する動作である。この技術は、通信や記憶媒体などで既に幅広く利用されており、特に無線通信もしくはＡＤＳＬ（Asymmetric Digital Subscriber Line）などのような有線通信の高速化、あるいは光ディスクなどの記憶媒体の大容量化などにおいて、不可欠とされる技術である。
　前述のように、復号化は元の符号語を推定する処理であり、同一の符号であっても複数の方法が考えられる。通常、復号結果は符号語またはそれを生成する情報ビット列として与えられるが、受信系列に対して各情報ビットを重み付きで推定する復号方法も知られている。これを軟出力復号法という。最適な軟出力復号は、各情報シンボルに対して符号語を構成するビット列であるという制約条件の下、符号語に対する受信系列に基づきその情報ビットもしくシンボルの条件付き確率を出力する復号である。これを事後確率復号法という。
　２値の場合には事後確率復号は次の数１で示す対数尤度比Ｌ（ｔ）を生成すれば十分である。ここで、ｕ（ｔ）は時点ｔの情報ビット、Ｙは符号語に対する受信値の系列、Ｐ（ｕ（ｔ）＝ｂ｜Ｙ）（ｂ＝０，１）は受信系列Ｙの下でｕ（ｔ）＝ｂとなる条件付確率である。
Figure JPOXMLDOC01-appb-M000001
　復号化処理で、特に状態数の小さい符号トレリスで表すことが可能な符号の復号化では、比較的計算量の小さい事後確率復号方法が知られている。この手法は、畳込み符号の最尤復号法として知られているヴィタビ復号と同様に、論理的には符号トレリス上の処理として実現できる。この手法は、非特許文献１に記載されているＢＣＪＲ（Bahl, Cocke, Jelinek, Raviv）アルゴリズム、もしくはＭＡＰ（Maximum A Posteriori probability）アルゴリズムと呼ばれる。
　ＭＡＰアルゴリズムでは、入力となる受信語Ｙは各ビットを０，１に判定した硬判定結果ではなく、各ビットの判定に信頼度を付けた値、つまり軟判定結果（軟入力値）を用いた復号法とすることができる。このため、この手法は軟入力軟出力復号法とも呼ばれる。この手法は、非特許文献２に記載されているターボ符号の復号における重要な要素である。以下、説明を容易とするために、シンボルがバイナリ符号である場合について説明するが、多値のシンボルで構成される符号の場合にも拡張することができる。
　図２２は、一般的なターボ符号器９００および復号器１０００の構造を示す説明図である。図２２の（ａ）に示すターボ符号器９００はインターリーバ９０３を介してフィードバックを持つ組織的な畳込み符号化器９０１および９０２を２個並列に連接して構成する。この畳込み符号はターボ符号の要素符号と呼ばれ、メモリ数４以下の符号が通常使用され、図２２はメモリ数２の場合の例を示している。
　畳込み符号化器９０１は、２個のメモリ９０１ａ～ｂと、３個の加算器９０１ｃ～ｅで構成される。畳込み符号化器９０２は、２個のメモリ９０２ａ～ｂと、３個の加算器９０２ｃ～ｅで構成される。畳込み符号化器９０１を要素符号１、９０２を要素符号２といい、それぞれで生成されるパリティ系列をパリティ１、パリティ２という。インターリーバ９０３は畳込み符号化器９０１および９０２による出力ビットを並び替える。このインターリーバ９０３の大きさと設計で、符号化の性能が大きく左右される。
　一方、図２２の（ｂ）に示すターボ復号器１０００は、ターボ符号器９００から出力される要素符号に対応する軟入力軟出力復号手段１００１と、各々情報系列、パリティ１、パリティ２に対応する受信値を保持するメモリ１０１２、１０１３、１０１４とを含む。ターボ符号の復号法は、一方の要素符号の軟出力復号で得られる軟出力値を他方の要素符号の軟入力値（事前情報）として利用し、これを繰り返すことにある。この繰り返しの過程で交換される軟出力値は、数１の値Ｌ（ｔ）そのものではなく、Ｌ（ｔ）から算出される数２で表される外部情報と呼ばれる値Ｌｅ（ｔ）である。
Figure JPOXMLDOC01-appb-M000002
　ここでｙ（ｔ）は情報ビットｕ（ｔ）に対する受信値、Ｌａ（ｔ）はｕ（ｔ）の事前情報として用いた他方の要素符号の軟出力復号で得られた軟出力値、Ｃは通信路のＳＮ比に応じて決まる定数である。インターリーバ１００３およびデインターリーバ１０１６の処理はメモリのアドレス生成処理として実現される。
　前述のＭＡＰアルゴリズム（ＢＣＪＲアルゴリズム）について詳しく述べる。ＭＡＰアルゴリズムは最尤復号法としてよく知られたヴィタビアルゴリズムと同様、符号トレリスを利用したアルゴリズムである。畳込み符号は符号器におけるメモリの値に応じて入力情報に対する符号語が変化する。この符号器内部におけるメモリの値を符号器の「状態」という。畳込み符号による符号化は情報系列に応じて状態を変化させながら出力を行う。
　符号トレリスはこの状態の遷移の組み合わせをグラフで表現したものであり、各時点における符号器の各状態をノードとして、遷移が存在する状態のペアにエッジをアサインすることで構成される。エッジはそれぞれの状態での入力情報で決定され、そのときの符号語がラベルとして割り当てられる。エッジの連結をパスと呼び、パスには符号語系列が対応する。
　即ち、送出された全てのデータの状態は、その前後の状態と関連していることになる。そのため、符号トレリスを利用すれば伝送経路において発生したエラーを、より高い精度で訂正できるという特質がある。特に、時不変の畳込み符号は時点に対して不変のトレリス構造を持つ特徴があり、このため状態数が小さければ符号トレリスを利用したアルゴリズムを実行することが容易となる。
　図２３は、図２２に示したターボ符号器９００のより詳細な構成を示す説明図である。　図２３（ａ）は図２２の要素符号の畳込み符号（メモリ数２）であり、図２３（ｂ）はそれに対応する符号トレリスである。初期状態はメモリ１０１２～１０１４の値を全て０とし、符号器の状態をメモリのビットを並べた系列で表現するとする。図２３（ａ）に示す畳込み符号化器９０１は、前述の通り２個のメモリ９０１ａ～ｂと、３個の加算器９０１ｃ～ｅで構成される。
　図２３（ｂ）に示す畳込み符号では、最初の情報ビットが０であれば符号語「００」を出力して時点１で状態「００」となる。一方、情報ビットが１であれば符号語「１１」を出力して時点１の状態は「１０」となる。時点２では時点１の状態「００」と「１１」のそれぞれに対して情報ビットの０もしくは１に応じた符号語の出力と時点２への状態遷移が行われる。
　ＭＡＰアルゴリズムは大きく分けて、符号トレリスの先頭から各ノードへ到達するパスメトリックを算出するフォワード処理と、符号トレリスの終端から各ノードへ到達するパスメトリックを算出するバックワード処理と、これら両者の結果を用いて各時点での情報シンボルの軟出力（事後確率比）を算出する軟出力生成処理、以上の３種類の処理からなる。
　フォワード処理におけるパスメトリックは、受信系列と事前情報の下、トレリスの先頭から各ノードへ到達する確率の対数値を相対的に表す。バックワード処理におけるパスメトリックは、トレリスの末尾から各ノードへ到達する確率の対数値を相対的に表す。
　以下、畳込み符号の状態の集合をＳ＝｛０，１，…，｜Ｓ｜－１｝，時点ｔ，状態ｓのノードにおけるフォワード処理およびバックワード処理で算出されるパスメトリックをそれぞれα（ｔ，ｓ），β（ｔ，ｓ）と定義する。また、γ（ｔ，ｓ，ｓ’）で受信値と事前情報（ターボ符号の場合は他方の要素符号の軟出力）から計算される、状態ｓから状態ｓ’への時点ｔでの遷移の確率に対応するブランチメトリックを表す。
　これはｓからｓ’への遷移に対応する符号語と受信値との間の尤度として計算でき、白色ガウス通信路ではγ（ｔ，ｓ，ｓ’）はｓからｓ’への遷移で出力される符号語の変調値と受信値の間のユークリッド距離および情報ビットに対する事前情報を用いて容易に計算することができる。
　このときフォワード処理、バックワード処理および軟出力生成処理は、１時点前もしくは１時点後の値を用いて、以下の数３～５に示すように表される。数３はフォワード処理、数４はバックワード処理、数５は軟出力生成処理をそれぞれ示す。
Figure JPOXMLDOC01-appb-M000003
Figure JPOXMLDOC01-appb-M000004
Figure JPOXMLDOC01-appb-M000005
　以後、本明細書の数式以外の行では、たとえばサフィックスとして「ｓ’：τ（ｓ’，ｂ）＝ｓ，ｂ＝０，１」の指定されたΣを、Σ＿｛ｓ，ｓ’：τ（ｓ，ｂ）＝ｓ’｝という形で表す。τ（ｓ’，ｂ）＝ｓは状態ｓ’から情報ビットｂでｓへ遷移することを表し、Σ＿｛ｓ’：τ（ｓ’，ｂ）＝ｓ，ｂ＝０，１｝は次の時点でｓ’となるすべての状態ｓに対して和をとることを表す。またΣ＿｛ｓ，ｓ’：τ（ｓ，ｂ）＝ｓ’｝はｓからｓ’への状態遷移における情報ビットがｂとなる状態のペア｛ｓ，ｓ’｝に対して和をとることを表す。
　このＭＡＰアルゴリズムを改良し、数３～５に示す処理を、和の計算を最大値をとる操作によって変更することによって行うアルゴリズムを、Ｍａｘ－Ｌｏｇ－ＭＡＰアルゴリズムという。これによって、ｅｘｐとｌｏｇへの変換が不要となり、ヴィタビアルゴリズムにおけるＡＣＳ（Add-Compare-Select）処理と同様の処理で計算の処理が可能となり、計算を大幅に簡易化することができる。たとえば、前述の数３は、Ｍａｘ－Ｌｏｇ－ＭＡＰアルゴリズムでは数６に示すように簡易化される。
Figure JPOXMLDOC01-appb-M000006
　Ｍａｘ－Ｌｏｇ－ＭＡＰアルゴリズムからＭＡＰアルゴリズムへの近似の精度を上げて効率よく復号特性を向上させるアルゴリズムとして、数６で比較されるパスメトリックの差分値からテーブル参照によって数６の結果に対する補正値を算出するアルゴリズムが非特許文献３に記載されており、これをＬｏｇ－ＭＡＰアルゴリズムという。
　図２４は、ＭＡＰアルゴリズム（またはＭａｘ－Ｌｏｇ－ＭＡＰアルゴリズム）で行われるフォワード処理、バックワード処理および軟出力生成処理の順序を示す説明図である。各時点でフォワード処理のαとバックワード処理のβとが揃っていなければ、軟出力生成処理は不可能である。図２４（ａ）は、符号トレリスの終端からバックワード処理を行って各時点のβを生成しておいてから（時点Ｔ１）、トレリスの先頭からフォワード処理および軟出力生成処理を行う（時点Ｔ２）という、単純なスケジューリング処理の一例を示す。
　ただし、図２４（ａ）に示した例では、この処理のためにトレリス長、つまり情報長分の遅延が発生するので、高速化には向かない。また、βを情報長分保持する必要もあるため、その分だけの容量のメモリを必要とする。
　図２４（ｂ）は、この欠点を改良し、トレリスを大きさＷ時点のブロックに分割し、そのブロックごとにバックワード処理、フォワード処理・軟出力生成処理を行っていくスケジューリング処理の一例を示す。時点Ｔ１ではブロックＷ１に対してバックワード処理を行う。時点Ｔ２ではブロックＷ１に対してフォワード処理および軟出力生成処理を行いつつ、ブロックＷ２に対してバックワード処理を行う。時点Ｔ３ではブロックＷ２に対してフォワード処理および軟出力生成処理を行いつつ、ブロックＷ３に対してバックワード処理を行う。以後同様に処理を継続する。
　図２４（ｂ）に例示した処理では、遅延の発生およびメモリ容量をある程度削減することはできる。しかしながら、少なくとも情報長分の処理サイクル数が必要であることには変わりはない。非特許文献３には、この欠点を改良したｒａｄｉｘ－２＾ｎと呼ばれる手法が記載されている。ｒａｄｉｘ－２＾ｎとは、１サイクルでｎ時点分のフォワード処理、バックワード処理および軟出力生成処理を行うことでサイクル数を削減して高速化を図るという手法である。ｎは２以上の整数である。
　ｒａｄｉｘ－２＾ｎには、高速化という効果のみならず、同一スループットであればサイクル数の削減によってクロック周波数を低くできるので、復号装置の消費電力を削減できるという効果もある。非特許文献４には、ｒａｄｉｘ－４、即ちｎ＝２時点分の処理を１サイクルで行うという例が記載されている。数７はフォワード処理、数８はバックワード処理、数９は軟出力生成処理をそれぞれ示す。
Figure JPOXMLDOC01-appb-M000007
Figure JPOXMLDOC01-appb-M000008
Figure JPOXMLDOC01-appb-M000009
Figure JPOXMLDOC01-appb-I000010
　非特許文献３では数７～８におけるテーブル参照を用いたＬｏｇ－ＭＡＰアルゴリズムに基づく近似処理による簡易化について述べている。図２５は図２３（ａ）に示したメモリ数２の畳込み符号器で、時点２ｔおよび２（ｔ＋１）という２時点分の遷移を表すトレリスについて示す説明図である。時点２ｔと時点２（ｔ＋１）は●印、その間の時点（２ｔ＋１）は○印で示している。
　図２６は、数７～９に示したｒａｄｉｘ－４による軟出力復号におけるバックワード処理部１１００について示す説明図である。バックワード処理部１１００は、図２４（ａ）に示したようなバックワード処理のパスメトリックをメモリに格納するスケジューリングを、ｒａｄｉｘ－４にて行うものである。パスメトリックは偶数時点に対して状態の個数だけ生成される。
　バックワード処理部１１００は、数８に示した処理を実行する２時点バックワードプロセッサ１１０２と、２時点おきのβを一時的に格納するレジスタ１１０３からなる。同時に、ブランチメトリックγを格納するブランチメトリックメモリ１１０１と、パスメトリックメモリ１１０４とを併設している。
　ブランチメトリックメモリ１１０１は、２時点分のブランチメトリックγを１サイクルの処理で使用する。レジスタ１１０３に格納されている２時点おきのβは、軟出力生成が済むまで、パスメトリックメモリ１１０４にも保持される。またレジスタ１１０３にも、状態の個数に対応する個数のパスメトリックが保持される。
　図２７は、数７～９に示したｒａｄｉｘ－４による軟出力復号におけるフォワード処理・軟出力生成部１２００について示す説明図である。フォワード処理・軟出力生成部１２００は、図２４（ａ）に示したようなフォワード処理・軟出力生成処理をｒａｄｉｘ－４にて行うものであり、フォワード処理と軟出力生成処理とを同時に実行するものである。
　フォワード処理・軟出力生成部１２００は、数７に示した処理を実行する２時点フォワードプロセッサ１２０２と、２時点おきのαを一時的に格納するレジスタ１２０３と、数９に示した処理を実行する２時点軟出力生成プロセッサ１２０４とからなる。ブランチメトリックγを格納するブランチメトリックメモリ１１０１と、パスメトリックメモリ１１０４は、図２６に示したものと同一である。
　ブランチメトリックメモリ１１０１は、２時点分のブランチメトリックγを１サイクルの処理で使用する。また２時点軟出力生成プロセッサ１２０４は、時点ｔのαおよびβ、時点ｔおよびｔ＋１のγから軟出力を生成する。
　これに関連する技術文献として、前述の非特許文献１～４の他には、次の特許文献がある。特許文献１には、打切り長内と打切り長以上遡った処理を並行して行うことによって、計算量を削減するという軟出力復号装置が記載されている。特許文献２には、最尤メトリックを有するステートに対応するバンクのみから生残りパス情報を読出してトレースバックを行ない、それ以外の不要な生残りパス情報を読出さないというビタビ復号装置が記載されている。
　特許文献３には、要素符号の局所的な入出力が可能である局所的な軟入力軟出力復号手段を備えることによって復号処理の繰り返し回数を削減できるという軟出力復号装置が記載されている。特許文献４には、データの書き込みと読み出しとを同時に行えるメモリを備えることにより回路規模を小さくしたという軟出力復号装置が記載されている。
再特ＷＯ９９／６２１８３号公報 特開２００１－１８６０２５号公報 特開２００７－００６５４１号公報 特開２００８－１８２４４２号公報
L.R.Bhalet.al, "Optimal decoding of linear codes for minimizing symbol error rate",IEEE Transaction on Information Theory, pp.284-287, 1974. C.Berrou et.al, "Near Shannon limit error-correcting coding and decoding: Turbocodes", Proc. IEEE International Conference of Communications (ICC),pp.1064-1070, 1993. P.Robertson et.al, "A Comparison of Optimal and Sub-Optimal MAP DecodingAlgorithms Operating in the Log Domain", Proc. IEEE International Conference ofCommunications (ICC), pp.1009-1013, 1995. C.Thomas et.al, "Integrated Circuits for Channel Coding in 3G Cellular MobileWireless Systems", IEEE Communication Magazine, vol.41, no.8, pp.150-159, 2003.
　しかしながら、符号トレリスに基づいて数７～９に示したｒａｄｉｘ－４による軟出力復号に係る復号処理を行うには、２時点分の処理を伴うため、特に数９の軟出力生成処理の回路構成が複雑になり、復号処理の高速化が困難である。ｒａｄｉｘ－２＾ｎとして、ｎを３以上の値として高速化を図ることはさらに困難である。
　非特許文献１～４、および特許文献１～４として説明した技術では、この点で十分であるとは言えず、上記の問題を解決することはできない。
　本発明の目的は、ｒａｄｉｘ－２＾ｎによる軟出力復号における軟出力生成処理を簡単な回路構成で高速に行うことを可能とする軟出力復号器を提供することにある。
　上記目的を達成するため、本発明に係る軟出力復号器は、符号化されて送信されたビットストリームを受信して復号化して外部に出力する軟出力復号器であって、受信したビットストリームを記憶する受信値メモリと、受信値メモリに記憶された内容に基づいてトレリス線図における各時点ごとのブランチメトリックを生成するブランチメトリック生成手段と、ブランチメトリックを復号化して事後確率比を含む軟出力符号を出力する軟出力復号手段と、軟出力符号を事後確率比を含まない硬出力符号に変換して上位レイヤに出力する硬出力判定手段とを備え、軟出力復号手段が、ブランチメトリックを一時記憶するブランチメトリックメモリと、ブランチメトリックメモリに記憶されたブランチメトリックの符号トレリスの終端から各ノードへ到達するパスメトリックを推定処理するバックワード処理部と、ブランチメトリックメモリに記憶されたブランチメトリックの符号トレリスの先頭から各ノードへ到達するパスメトリックを推定処理するフォワード処理部と、バックワード処理部による推定処理の結果を記憶するパスメトリックメモリと、バックワード処理部およびフォワード処理部による推定処理の結果から各時点での情報シンボルの事後確率比を算出してこれを軟出力符号として出力する軟出力生成処理部とを有すると共に、バックワード処理部が、相互に連結され符号トレリスの１時点ごとの推定処理に対応する複数個のバックワードプロセッサを備え、パスメトリックメモリが、バックワードプロセッサの各々に対応する複数の記憶域を備えることを特徴とする。
　本発明は、上記したように１時点ごとのパスメトリックをパスメトリックメモリに記憶して、これに基づいて復号化処理を行うように構成したので、２段階以上の状態を推定する処理を必要とせず、そのため復号装置に複雑な回路構成を必要とせず、高速化が容易である。これによって、符号トレリスに基づく復号化処理を簡単な回路構成で高速に行うことを可能であるという、優れた特徴を持つ軟出力復号器を提供することができる。
本発明の第１の実施形態に係る軟出力復号器（ターボ符号復号器）の構成を示す説明図である。 本発明の第１の実施形態に係るターボ符号復号器を含む伝送系統の構成を示す説明図である。図２（ａ）は無線通信による伝送系統、図２（ｂ）は光学ディスクなどの記憶媒体による伝送系統をそれぞれ示す。 図１で説明した軟出力復号手段のさらに詳しい構成を示す説明図である。 図３に示したバックワード処理部のより詳しい構成を示す説明図である。 図３に示したフォワード処理部および軟出力生成処理部のより詳しい構成を示す説明図である。 図４に示したバックワード処理部の構成を、一般のｒａｄｉｘ－２＾ｎ（ｎは２以上の整数）の場合について拡張したバックワード処理部の構成を示す説明図である。 図５に示したフォワード処理部および軟出力生成処理部の構成を、一般のｒａｄｉｘ－２＾ｎ（ｎは２以上の整数）の場合について拡張したフォワード処理部および軟出力生成処理部の構成を示す説明図である。 本発明の第２の実施形態に係るターボ符号復号器の構成を示す説明図である。 図８で示した軟出力復号手段のより詳しい構成を示す説明図である。 図９で示したバックワード処理部のより詳しい構成を示す説明図である。 図１０で示した第１および第２の１時点バックワードプロセッサのより詳しい構成を示す説明図である。 図１１で示した第１の１時点バックワードプロセッサの状態「００」に対する構成をより詳しく示す説明図である。 図９で示したフォワード処理部のより詳しい構成を示す説明図である。 図１３で示した第１および第２の１時点フォワードプロセッサのより詳しい構成を示す説明図である。 図９に示した本実施形態におけるフォワード処理手段および軟出力生成手段で、各時点においてレジスタに格納されている情報、メモリから読み出されるデータ、および生成される軟出力を示す表である。 本発明の第３の実施形態に係るターボ符号復号器の構成を示す説明図である。 図１６で示した軟出力復号手段のより詳しい構成を示す説明図である。 図１８は、図１７で示したバックワード処理部のより詳しい構成を示す説明図である。 図１８で示した第１の１時点バックワードプロセッサの構成の状態「００」に対する構成をより詳しく示す説明図である。 図２０は、図１７で示したフォワード処理部および軟出力生成部のより詳しい構成を示す説明図である。 図１９で示した第１の軟出力生成プロセッサの構成をさらに詳しく示す説明図である。 一般的なターボ符号器および復号器の構造を示す説明図である。図２２（ａ）はターボ符号器、（ｂ）はターボ復号器をそれぞれ示す。 図２２に示したターボ符号器のより詳細な構成を示す説明図である。図２３（ａ）は図２２の要素符号の畳込み符号器（メモリ数２）であり、図２３（ｂ）はそれに対応する符号トレリスをそれぞれ示す。 ＭＡＰアルゴリズム（またはＭａｘ－Ｌｏｇ－ＭＡＰアルゴリズム）で行われるフォワード処理、バックワード処理および軟出力生成処理の順序を示す説明図である。図２４（ａ）は単純なスケジューリング処理の一例、図２４（ｂ）はその欠点を改良したスケジューリング処理の一例を示す。 図２５は図２３（ａ）に示したメモリ数２の畳込み符号器で、時点２ｔおよび２（ｔ＋１）という２時点分の遷移を表すトレリスについて示す説明図である。 数７～９に示したｒａｄｉｘ－４による軟出力復号におけるバックワード処理部について示す説明図である。 数７～９に示したｒａｄｉｘ－４による軟出力復号におけるフォワード処理・軟出力生成部のブロック図である。
　（第１の実施形態）
　以下、本発明の第１の実施形態の構成について添付図１～２に基づいて説明する。
　最初に、本実施形態の基本的な内容について説明し、その後でより具体的な内容について説明する。
　本実施形態に係る軟出力復号器１０は、ビットストリームを復号化して外部に出力するする軟出力復号器である。この軟出力復号器１０は、ビットストリームを記憶する受信値メモリ１０１～１０３と、受信値メモリに記憶された内容に基づいてトレリス線図における各時点ごとのブランチメトリックを生成するブランチメトリック生成手段１０５と、ブランチメトリックを復号化して事後確率比を含む軟出力符号を出力する軟出力復号手段１１０と、軟出力符号を事後確率比を含まない硬出力符号に変換して外部に出力する硬出力判定手段１０６とを備える。この軟出力復号手段は、ブランチメトリックを一時記憶するブランチメトリックメモリ１５０と、記憶されたブランチメトリックの符号トレリスの終端から各ノードへ到達するパスメトリックを推定処理するバックワード処理部１２０と、記憶されたブランチメトリックの符号トレリスの先頭から各ノードへ到達するパスメトリックを推定処理するフォワード処理部１３０と、バックワード処理部による推定処理の結果を記憶するパスメトリックメモリ１６０と、バックワード処理部およびフォワード処理部による推定処理の結果から各時点での情報シンボルの事後確率比を算出してこれを軟出力符号として出力する軟出力生成処理部１４０とを有する。そして、バックワード処理部が、相互に連結され、符号トレリスの１時点ごとの推定処理に対応する複数個のバックワードプロセッサ１２１～１２２を備え、パスメトリックメモリ１６０がバックワードプロセッサの各々に対応する複数の記憶域１６１～１６２を備える。
　またこのバックワード処理部およびフォワード処理部は、１サイクルに対して複数時点分のパスメトリックを推定処理する。そしてフォワード処理部は、相互に連結され、符号トレリスの１時点ごとの推定処理に対応する複数個のフォワードプロセッサ１３１～１３２を備える。さらにパスメトリックメモリ１６０がフォワードプロセッサの各々に対応する複数の記憶域１６１～１６２を備え、軟出力生成処理部はパスメトリックメモリに記憶されたバックワード処理部およびフォワード処理部による推定処理の結果から各時点での情報シンボルの事後確率比を算出する。
　以上の構成を備えることにより、軟出力復号器１０は、符号トレリスに基づく復号化処理を簡単な回路構成で高速に行うことが可能となる。
　以下、これをより詳細に説明する。
　図２は本発明の第１の実施形態に係る軟出力復号器であるターボ符号復号器１０を含む伝送系統１の構成を示す説明図である。図２（ａ）に示す伝送系統１は、無線通信で電波信号を受信するアンテナ２０と、アンテナ２０が受信した電波信号からビットストリームを抽出する復調器３０と、抽出されたビットストリームに対して誤り訂正と復号化の処理を行うターボ符号復号器１０とからなる。
　また、図２（ａ）に示すアンテナ２０を、ＡＤＳＬなどのような有線伝送系統に置き換えてもよい。さらに、図２（ｂ）に示すように、アンテナ２０を、光学ディスクなどの記憶媒体から記録データを読み出す光ピックアップ２０ａに置き換えてもよい。即ち、ターボ符号復号器１０は、ビットストリームを復号化する用途全般に対して幅広く適用することができるものである。復調器３０からターボ符号復号器１０に対して出力されるビットストリームは、情報受信値と、第１および第２のパリティ受信値とが含まれる。
　図１は、図２で示した本実施形態に係るターボ符号復号器１０の構成を示す説明図である。ターボ符号復号器１０は、復調器３０からの受信値を記憶する情報受信値メモリ１０１、第１および第２のパリティ受信値メモリ１０２および１０３と、情報受信値からインターリーブ出力を生成するインターリーバ１０４と、情報受信値とそのインターリーブ出力と、第１および第２のパリティ受信値からブランチメトリックを生成するブランチメトリック生成手段１０５と、ブランチメトリックを復号化して軟出力符号を出力する軟出力復号手段１１０とを備える。
　ターボ符号復号器１０はまた、軟出力復号手段１１０から出力された軟出力符号を硬出力符号に変換して上位レイヤに出力する硬出力判定手段１０６と、この軟出力符号からデインターリーブ出力を生成するデインターリーバ１０７と、軟出力符号およびそのデインターリーブ出力とを外部情報として記憶する外部情報メモリ１０８と、外部情報からさらにインターリーブ出力を生成するインターリーバ１０９とを備える。ブランチメトリック生成手段１０５は、この外部情報とそのインターリーブ出力も、ブランチメトリックの生成に使用する。
　図３は、図１で説明した軟出力復号手段１１０のさらに詳しい構成を示す説明図である。軟出力復号手段１１０は、バックワード処理部１２０、フォワード処理部１３０、軟出力生成処理部１４０、ブランチメトリックメモリ１５０、パスメトリックメモリ１６０の各々を含む。
　ブランチメトリック生成手段１０５から出力されたブランチメトリックは、ブランチメトリックメモリ１５０に記憶された上で、バックワード処理部１２０、フォワード処理部１３０、軟出力生成処理部１４０の各々に入力される。これら各部の処理内容については後述する。バックワード処理部１２０が処理した内容は、パスメトリックメモリ１６０に記憶され、その上で軟出力生成処理部１４０に入力される。軟出力生成処理部１４０は、最終的に軟出力復号手段１１０が出力する内容を生成する。
　軟出力復号手段１１０は、図２４で説明したようにバックワード処理、フォワード処理、軟出力生成処理という順序で処理を行う構成を示しているが、このバックワード処理部１２０とフォワード処理部１３０とを入れ替え、先にフォワード処理を行ってパスメトリックαを生成してパスメトリックメモリ１６０に保持し、その後にバックワード処理と軟出力生成処理を行うようにしてもよい。
　そして、後述するように、パスメトリックメモリ１６０はバックワード処理の処理段階に応じて複数の記憶域を持つ。
　以下、α（ｔ）は時点ｔにおける、すべての状態ｓに対するα（ｔ，ｓ）の集合を表す。β（ｔ）も同様である。また、γ（ｔ）は時点ｔにおけるブランチメトリック全体の集合を表す。
　図４は、図３に示したバックワード処理部１２０のより詳しい構成を示す説明図である。バックワード処理部１２０は、本実施形態をｒａｄｉｘ－４に適用した場合の２時点バックワード処理を行うものであり、第１および第２の１時点バックワードプロセッサ１２１および１２２と、２時点おきのβを一時的に格納するレジスタ１２３を有する。そしてパスメトリックメモリ１６０は、各々の１時点バックワードプロセッサ１２１および１２２で生成されるパスメトリックを保持する第１および第２のパスメトリック記憶域１６１および１６２を持つ。
　各々の１時点バックワードプロセッサおよび１２２は、同一の処理を行う場合もあれば、異なる処理を行う場合もある。ブランチメトリックメモリ１５０は、２時点分のブランチメトリックγを１サイクルの処理で使用する。レジスタ１２３がβ（２（ｔ＋１））を保持している場合、バックワード処理部１２０は１サイクルで次の処理を完了する。
　第１の１時点バックワードプロセッサ１２１は、レジスタ１２３に記憶されたβ（２（ｔ＋１））とブランチメトリックメモリ１５０に記憶されたγ（２ｔ＋１）を用いて前述の数４に示した数式によって中間パスメトリックβ（２ｔ＋１）を生成し、第１のパスメトリック記憶域１６１に格納する。
　第２の１時点バックワードプロセッサ１２２は、第１の１時点バックワードプロセッサ１２１によって生成された中間パスメトリックβ（２ｔ＋１）とブランチメトリックメモリ１５０に記憶されたγ（２ｔ）を用いて以下の数１０に示す処理によってβ（２ｔ）を生成し、レジスタ１２３を更新するとともに第２のパスメトリック記憶域１６２に格納する。
Figure JPOXMLDOC01-appb-M000011
　図５は、図３に示したフォワード処理部１３０および軟出力生成処理部１４０のより詳しい構成を示す説明図である。フォワード処理部１３０は、本実施形態をｒａｄｉｘ－４に適用した場合の２時点フォワード処理を行うものであり、第１および第２の１時点フォワードプロセッサ１３１および１３２と、これらの１時点フォワードプロセッサ１３１および１３２が生成した中間パスメトリックを一時保存する第１および第２のレジスタ１３３および１３４を有する。
　軟出力生成処理部１４０は、本実施形態をｒａｄｉｘ－４に適用した場合の軟出力生成処理を行うものであり、ブランチメトリックメモリ１５０から出力されるブランチメトリックメモリを一時保存するレジスタ１４１と、パスメトリックメモリ１６０の第１および第２のパスメトリック記憶域１６１および１６２に記憶された内容と各々のレジスタ１３３、１３４および１４１に記憶された内容とから軟出力生成処理を行う第１および第２の軟出力生成処理プロセッサ１４２および１４３とを有する。
　レジスタ１３３がα（２ｔ）を保持している場合の動作を説明する。まず第１の１時点フォワード処理手段１３１は、レジスタ１３３が保持するα（２ｔ）と、ブランチメトリックメモリ１５０から入力されるγ（２ｔ）とから、前述の数１０に示した処理によって中間パスメトリックα（２ｔ＋１）を生成し、これをレジスタ１３４に記憶する。
　第２の１時点フォワード処理手段１３２は、図４の第１のパスメトリック記憶域１６１に記憶された中間パスメトリックα（２ｔ＋１）と、ブランチメトリックメモリ１５０から入力されるγ（２ｔ＋１）とから、前述の数１０に示した処理によってα（２（ｔ＋１））を生成し、レジスタ１３３を更新する。
　第１および第２の軟出力生成処理プロセッサ１４２および１４３は各々、時点２ｔ、２ｔ＋１の各１時点の軟出力を生成する。第１の軟出力生成処理プロセッサ１４２は、レジスタ１３３のα（２ｔ）と、パスメトリックメモリ１６１のβ（２ｔ＋１）と、ブランチメトリックメモリ１５０から入力されるγ（２ｔ）とから、以下の数１１に示した処理によって時点２ｔの軟出力を生成する。
Figure JPOXMLDOC01-appb-M000012
　第２の軟出力生成処理プロセッサ１４３は、レジスタ１３４のα（２ｔ－１）と、パスメトリックメモリ１６１のβ（２ｔ）と、レジスタ１４１に格納されているγ（２ｔ－１）とから、前述の数１１に示した処理によって時点２ｔ－１の軟出力を生成する。レジスタ１４１はγ（２ｔ＋１）に更新される。
（第１の実施形態の全体的な動作）
　次に、上記の実施形態の全体的な動作について説明する。本実施形態に係るセキュリティポリシー作成方法は、ターボ符号によって符号化されたビットストリームを復号化して外部に出力するターボ符号復号化方法である。まずビットストリームを予め備えられた受信値メモリに記憶し、受信値メモリに記憶された内容に基づいてトレリス線図における各時点ごとのブランチメトリックを生成し、ブランチメトリックの符号トレリスの終端から符号トレリスの１時点ごとに各ノードへ到達するパスメトリックを推定処理し、符号トレリスの終端からの推定処理の結果を１時点ごとに予め備えられたパスメトリックメモリに記憶し、ブランチメトリックの符号トレリスの先頭からから符号トレリスの１時点ごとに各ノードへ到達するパスメトリックを推定処理して、符号トレリスの終端および先頭からの推定処理の結果から各時点での情報シンボルの事後確率比を算出してこれを事後確率比を含む軟出力符号とし、軟出力符号を事後確率比を含まない硬出力符号に変換して外部に出力する。
　この構成および動作により、本実施形態は以下のような効果を奏する。
　本実施形態は、ｒａｄｉｘ－２＾ｎに基づく符号トレリス上の軟出力復号アルゴリズムを、軟出力生成処理の複雑度を上げることなく実現することができる。従って、復号器の動作の高速化と、装置規模の改善を図ることができる。
　例えば、図２の畳込み符号で通常の１時点毎のＭａｘ－Ｌｏｇ－ＭＡＰアルゴリズムに基づく軟出力復号であれば数５に示した軟出力生成処理の論理的な深さは算術加算２段、ｍａｘ回路２段（情報ビット０、１となるそれぞれ４個のメトリックから１個を選択）の計４段となり、数９に示したｒａｄｉｘ－４の軟出力生成処理は算術加算３段、ｍａｘ回路３段となる。
　これに対して本実施形態を利用すれば、ｒａｄｉｘ－４の軟出力生成処理は算術加算２段、ｍａｘ回路２段のままであり、フォワード処理およびバックワード処理も算術加算２段、ｍａｘ回路２段となる。つまり、本実施形態によれば、通常のｒａｄｉｘ－４と比較して最大レイテンシを２／３程度に抑制することができるので、その分最大クロック周波数を上昇させ、動作の高速化を図ることができる。
（第１の実施形態の拡張）
　前述の第１の実施形態は、ｒａｄｉｘ－４の場合についてのみ説明したが、これはｒａｄｉｘ－２＾ｎ（ｎは２以上の整数）の場合についても容易に拡張が可能である。
　図６は、図４に示したバックワード処理部１２０の構成を、一般のｒａｄｉｘ－２＾ｎ（ｎは２以上の整数）の場合について拡張したバックワード処理部１２０ｎの構成を示す説明図である。バックワード処理部１２０ｎは、ｎ個の１時点バックワードプロセッサ１２１ａ、１２１ｂ、…１２１ｎを連結して構成されたｎ時点バックワード処理手段と、ｎ時点おきのβを一時的に格納するレジスタ１２３ｎとを有する。そしてパスメトリックメモリ１６０は、各々の１時点バックワードプロセッサ１２１ａ～ｎで生成されるパスメトリックを保持するｎ個のパスメトリック記憶域１６１ａ、１６１ｂ、…１６１ｎを持つ。
　レジスタ１２３ｎがβ（ｎｔ）を格納しているとき、次のステップでは各プロセッサでβ（ｎｔ＋１），…，β（ｎｔ＋ｎ－１），β（ｎ（ｔ＋１））を生成して、各々対応するパスメトリック記憶域１６１ａ～ｎに保持する。また、レジスタ１２３ｎはβ（ｎ（ｔ＋１））によって更新される。
　図７は、図５に示したフォワード処理部１３０および軟出力生成処理部１４０の構成を、一般のｒａｄｉｘ－２＾ｎ（ｎは２以上の整数）の場合について拡張したフォワード処理部１３０ｎおよび軟出力生成処理部１４０ｎの構成を示す説明図である。フォワード処理部１３０ｎは、連結して構成されたｎ個の１時点フォワードプロセッサを１３１ａ、１３１ｂ、…１３１ｎと、各々の１時点フォワードプロセッサ１３１ａ～ｎに対応するｎ－１個のレジスタ１３４ａ、１３４ｂ、…１３４（ｎ－１）とを有する。
　レジスタ１３３にα（ｎｔ）が記憶されている場合に、レジスタ１３４ａ～（ｎ－１）には、α（ｎｔ－１）、α（ｎｔ－２）、…、α（ｎｔ－ｎ＋１）が格納されている。軟出力生成処理部１４０ｎは前述の数１１に示した処理を実行するｎ個の１時点軟出力生成プロセッサ１４２ａ～ｎを含む。
　以上の構成により、一般のｒａｄｉｘ－２＾ｎ（ｎは２以上の整数）の場合についても、前述の第１の実施形態と同じ効果を持つターボ符号復号器を得ることができる。
（第２の実施形態）
　本発明の第２の実施形態は、前述した第１の実施形態に比べて、バックワードプロセッサとパスメトリックメモリとの間に補正処理部４００を設け、バックワード処理の出力データを前述の非特許文献３に記載されたＬｏｇ－ＭＡＰアルゴリズムに基づいて補正してからパスメトリックメモリに記憶する構成とした。このことにより、軟出力生成処理の精度を向上しつつ、計算量やメモリ容量の削減を図ることができる。
　図８は、本発明の第２の実施形態に係るターボ符号復号器２１０の構成を示す説明図である。ターボ符号復号器２１０の構成は、図１で既述した第１の実施形態に係るターボ符号復号器１０の構成と比べて、軟出力復号手段１１０の内部構成のみが異なるので、これを軟出力復号手段３１０という。これ以外の構成要素は全て同一の名称および参照番号でいう。ターボ符号復号器２１０は、前述したＭａｘ－Ｌｏｇ－ＭＡＰアルゴリズムを利用したターボ符号に対して、復号化処理を行うものである。
　図９は、図８で示した軟出力復号手段３１０のより詳しい構成を示す説明図である。軟出力復号手段３１０の構成は、図３で既述した第１の実施形態に係る軟出力復号手段１１０の構成と比べて、バックワード処理部１２０およびフォワード処理部１３０の内部構成のみが異なるので、これをバックワード処理部３２０およびフォワード処理部３３０という。これ以外の構成要素は全て同一の名称および参照番号でいう。
　図１０は、図９で示したバックワード処理部３２０のより詳しい構成を示す説明図である。バックワード処理部３２０の構成は、図４で既述した第１の実施形態に係るバックワード処理部１２０の構成と比べて、第１および第２の１時点バックワードプロセッサ１２１および１２２のみが異なるので、これを第１および第２の１時点バックワードプロセッサ３２１および３２２という。これ以外の構成要素は全て同一の名称および参照番号でいう。
　図１１は、図１０で示した第１および第２の１時点バックワードプロセッサ１２１および１２２のより詳しい構成を示す説明図である。レジスタ１２３は、β（２ｔ，００），β（２ｔ，１０），β（２ｔ，０１），β（２ｔ，１１）という各々の状態に対するパスメトリックを保持している。
　第１の１時点バックワードプロセッサ３２１は、対応するβとγの値を加算する８個の算術加算回路３２１ａ～ｈと、数値を比較して大きい方の数値を出力するｍａｘ回路３２１ｉ～ｌとで構成される。第２の１時点バックワードプロセッサ３２２も同様に、対応するβとγの値を加算する８個の算術加算回路３２２ａ～ｈと、数値を比較して大きい方の数値を出力するｍａｘ回路３２２ｉ～ｌとで構成される。
　第１の１時点バックワードプロセッサ３２１は、前述したＭａｘ－Ｌｏｇ－ＭＡＰアルゴリズムを利用して、ブランチメトリックメモリ１５０に保持されたγ（２ｔ－１，００），γ（２ｔ－１，１０），γ（２ｔ－１，０１），γ（２ｔ－１，１１）の各々と、レジスタ１２３に保持された各々の数値に対して、以下の数１２に示す処理を行う。
　ここでγ（ｔ，ｘｙ）は時点ｔにおける符号語ビット列「ｘｙ」のブランチメトリックを表し、これを総称してγ（ｔ）という。β（ｔ，ｘｙ）も同様に、時点ｔにおける符号語ビット列「ｘｙ」のパスメトリックを表し、これを総称してβ（ｔ）という。
Figure JPOXMLDOC01-appb-M000013
　第２の１時点バックワードプロセッサ３２２は、前述したＭａｘ－Ｌｏｇ－ＭＡＰアルゴリズムを利用して、ブランチメトリックメモリ１５０に保持されたγ（２ｔ－２，００），γ（２ｔ－２，１０），γ（２ｔ－２，０１），γ（２ｔ－２，１１）の各々と、第１の１時点バックワードプロセッサ３２１から出力される各々の数値に対して、やはり上記の数１２に示す処理を行う。
　パスメトリック記憶域１６１は第１の１時点バックワードプロセッサ３２１で生成されるβ（２ｔ－１）を、パスメトリック記憶域１６２は第２の１時点バックワードプロセッサ３２２で生成されるβ（２ｔ－２）を保持する。レジスタ１２３もβ（２ｔ－２）で更新される。
　図１２は、図１１で示した第１の１時点バックワードプロセッサ３２１の状態「００」に対する構成をより詳しく示す説明図である。第１の１時点バックワードプロセッサ３２１は、前述の数１２で示した処理を行う簡易バックワードプロセッサ４１０と、後述の補正処理部４００とを含む。
　簡易バックワードプロセッサ４１０は、図１１で示したｍａｘ回路３２２ｉと、加算器３２２ａ～ｂとを含む。「００」以外の状態についても同様である。補正処理部４００は、数１３で示すｍａｘ回路３２１ｉに対する入力値ｘとｙの差分値｜ｘ－ｙ｜を取る差分手段４０１と、予め備えられたテーブルに基づいてこの差分値を補正するテーブル参照手段４０２と、ｍａｘ回路３２１ｉの出力とテーブル参照手段４０２の出力とを加算する加算器４０３とで構成されている。
Figure JPOXMLDOC01-appb-M000014
　Ｌｏｇ－ＭＡＰアルゴリズムは、下に示す数１４に基づき、この数１４の右辺の第２項をテーブル参照によって実現する。
Figure JPOXMLDOC01-appb-M000015
　テーブル参照手段４０２は予め記憶されたテーブル４２０を参照して、ｍａｘ回路３２１ｉで選択されたパスメトリックβ’（２ｔ－１，００）：＝ｍａｘ（ｘ，ｙ）に対して、｜ｘ－ｙ｜に基づいて数１５で示す補正値を出力する。ここでＬＵＴ（）はテーブル参照関数である。テーブル４２０は、第１の１時点バックワードプロセッサ３２１の内部に記憶されていても、外部の記憶装置に記憶されていてもよい。テーブル参照手段４０２と加算器４０３との間の出力が、パスメトリックメモリ１６１に記憶される。
Figure JPOXMLDOC01-appb-M000016
　図１３は、図９で示したフォワード処理部３３０のより詳しい構成を示す説明図である。フォワード処理部３３０の構成は、図４で既述した第１の実施形態に係るフォワード処理部１３０の構成と比べて、第１および第２の１時点フォワードプロセッサ１３１および１３２のみが異なるので、これを第１および第２の１時点フォワードプロセッサ３３１および３３２という。これ以外の構成要素は全て同一の名称および参照番号でいう。
　図１４は、図１３で示した第１および第２の１時点フォワードプロセッサ１３１および１３２のより詳しい構成を示す説明図である。レジスタ１３３は、β（２ｔ，００），β（２ｔ，１０），β（２ｔ，０１），β（２ｔ，１１）という各々の状態に対するパスメトリックを保持している。
　第１の１時点フォワードプロセッサ３３１は、対応するβとγの値を加算する８個の算術加算回路３３１ａ～ｈと、数値を比較して大きい方の数値を出力するｍａｘ回路３３１ｉ～ｌとで構成される。第２の１時点フォワードプロセッサ３３２も同様に、対応するβとγの値を加算する８個の算術加算回路３３２ａ～ｈと、数値を比較して大きい方の数値を出力するｍａｘ回路３３２ｉ～ｌとで構成される。
　第１の１時点フォワードプロセッサ３３１は、前述したＭａｘ－Ｌｏｇ－ＭＡＰアルゴリズムを利用して、ブランチメトリックメモリ１５０に保持されたγ（２ｔ，００），γ（２ｔ，１０），γ（２ｔ，０１），γ（２ｔ，１１）の各々と、レジスタ１３３に保持された各々の数値に対して処理を行う。
　パスメトリックメモリ１６１は１時点フォワードプロセッサ３３１で生成されるα（２ｔ＋１）を保持する。時点２ｔのαを格納しているレジスタ１３３は、次のサイクルでα（２ｔ＋２）に更新される。レジスタ１４１は、その過程で生成されるα（２ｔ＋１）を格納する。
　図１５は図９に示した、本実施形態におけるフォワード処理手段および軟出力生成手段で、各時点において各レジスタに格納されている情報、メモリから読み出されるデータ、および生成される軟出力を示す表である。時点０のブランチメトリックγ（１）はα（１）を生成するために使用され、レジスタ１４１に保持される。時点１ではレジスタ１４１のγ（１）とレジスタ１３４のα（１）およびβ（２）を使用してＬ（１）を計算する。
　以上に示した、補正処理部４００による動作は、第２の１時点バックワードプロセッサ３２２と並列に動作させることが可能であるため、全体の処理時間に影響を与えることはなく、処理速度の劣化は発生しない。第２の１時点フォワードプロセッサ３３２についても同様である。
　これによって、本実施形態ではパスメトリック値の精度をさらに向上することができ、これと同時に出力特性の改善を図ることができる。
（第３の実施形態）
　本発明の第３の実施形態は、前述した第２の実施形態に比べて、第１の１時点フォワードプロセッサにさらにパスメモリ６７０を追加し、これに選択したパスメトリックに対応する状態のインデックスを記憶するように構成している。このことにより、第２の実施形態で使用したｍａｘ回路をセレクタに置き換えることが可能となるので、回路構成をさらに簡素化できる。
　図１６は、本発明の第３の実施形態に係るターボ符号復号器５１０の構成を示す説明図である。ターボ符号復号器５１０の構成は、図１で既述した第１の実施形態に係るターボ符号復号器１０の構成と比べて、軟出力復号手段１１０の内部構成のみが異なるので、これを軟出力復号手段６１０という。これ以外の構成要素は全て同一の名称および参照番号でいう。ターボ符号復号器５１０は、前述したＭａｘ－Ｌｏｇ－ＭＡＰアルゴリズムを利用したターボ符号に対して、復号化処理を行うものである。
　図１７は、図１６で示した軟出力復号手段６１０のより詳しい構成を示す説明図である。軟出力復号手段６１０の構成は、図３で既述した第１の実施形態に係る軟出力復号手段１１０の構成と比べて、バックワード処理部１２０および軟出力生成部１４０の内部構成が異なるので、これをバックワード処理部６２０および軟出力生成部６４０という。フォワード処理部３３０は、図９で既述した第２の実施形態と同一である。さらに、後述するパスメモリ６７０が追加されている。これ以外の構成要素は全て同一の名称および参照番号でいう。
　図１８は、図１７で示したバックワード処理部６２０のより詳しい構成を示す説明図である。バックワード処理部６２０の構成は、図１０で既述した第２の実施形態に係るバックワード処理部３２０の構成と比べて、第１の１時点バックワードプロセッサ３２１のみが異なるので、これを第１の１時点バックワードプロセッサ６２１という。これ以外の構成要素は全て同一の名称および参照番号でいう。
　第１の１時点バックワードプロセッサ６２１は、パスメモリ６７０に記憶された情報を利用して、時点ｔにおいてパスメトリックメモリ１６１のβ（２（ｔ＋１））からγ（２ｔ＋１）を用いてバックワード処理の中間メトリックβ（２ｔ＋１）を生成し、レジスタ１３３のα（２ｔ）とγ（２ｔ）を併せてＬ（２ｔ）を生成する。第１の１時点バックワードプロセッサ６２１は、１時点前のパスメトリックとともにこの生成過程で発生する、選択したパスメトリックに対応する状態のインデックスをパスメモリ６７０に格納する。
　図１９は、図１８で示した第１の１時点バックワードプロセッサ６２１の構成の状態「００」に対する構成をより詳しく示す説明図である。第１の軟出力生成プロセッサ６２１は、状態「００」に対しては、β（２ｔ，００）とγ（２ｔ，００）とを算術加算する算術加算回路６２１ａと、β（２ｔ，１０）とγ（２ｔ，１１）とを算術加算する算術加算回路６２１ｂと、これらの算術加算回路６２１ａ～ｂからの出力を比較する比較器６２４ｉと、比較器６２４ｉからの出力とに応じて出力を切り替えるセレクタ６２１ｉと、で構成される。第１の１時点バックワードプロセッサ６２１は、「００」以外の構成についてもこれと同一である。
　Ｍａｘ－Ｌｏｇ－ＭＡＰアルゴリズムのフォワード処理では、時点ｔにおける状態ｓのパスメトリックが時点（ｔ＋１）のいずれの状態のパスメトリックから決まるかの情報があれば、図１０で示したｍａｘ回路をセレクタ６２１ｏ～ｒに置き換えることが可能となる。このため、第１の１時点バックワードプロセッサ６２１は、パスメモリ６７０にこれを記憶する。
　図２０は、図１７で示したフォワード処理部３３０および軟出力生成部６４０のより詳しい構成を示す説明図である。フォワード処理部３３０は、図１１で既述した第２の実施形態と同一である。軟出力生成部６４０の構成は、図１３で既述した第２の実施形態に係る軟出力生成部３４０の構成と比べて、第１の軟出力生成プロセッサ１４２が異なるので、これを第１の軟出力生成プロセッサ６４２という。さらに、後述のレジスタ６４５を含む。これ以外の構成要素は全て同一の名称および参照番号でいう。
　レート１／ｎの畳込み符号ではこのインデックスは１状態につき１ビットで十分である。パスメトリックメモリは典型的には１状態を記憶するのに５～８ビットが必要になるため、パスメトリックメモリ１６１と比較して、パスメモリ６７０は非常に少ない記憶容量で済む。
　図２１は、図１９で示した第１の軟出力生成プロセッサ６４２の構成をさらに詳しく示す説明図である。第１の軟出力生成プロセッサ６４２は、対応するβとγの値を加算する８個の算術加算回路６４２ａ～ｈと、β（２ｔ）とγ（２ｔ－１）を算術加算したパスメトリックをパスメモリ６７０の記憶内容に応じて出力を切り替えるセレクタ６４２ｉ～ｌとで構成される。パスメモリ６７０とセレクタ６４２ｉ～ｌとを組み合わせることによって、図１１に記載した第２の実施形態におけるｍａｘ回路３２２ｉ～ｌを代替していることになる。レジスタ６４５は、β（２（ｔ＋１））を一時的に格納する。
　第１の軟出力生成プロセッサ６４２は、パスメモリ６７０に記憶された情報を用いて、時点ｔにおいてレジスタ６４５に記憶されたβ（２（ｔ＋１））からγ（２ｔ＋１）を用いてバックワード処理の中間メトリックβ（２ｔ＋１）を生成し、さらにレジスタ１２３に記憶されたα（２ｔ）とγ（２ｔ）を用いてＬ（２ｔ）を生成する。
　以上で説明した本実施形態では、パスメモリ６７０を追加するので、前述の第１および第２の実施形態と比べてメモリの容量をほんの少し増加させる必要はあるが、そのかわり軟出力生成回路をより簡略に構成することができる。
　これまで本発明について図面に示した特定の実施形態をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、本発明の効果を奏する限り、これまで知られたいかなる構成であっても採用することができる。
　上述した各々の実施形態について、その新規な技術内容の要点をまとめると、以下のようになる。なお、上記実施形態の一部または全部は、新規な技術として以下のようにまとめられるが、本発明は必ずしもこれに限定されるものではない。
（付記１）　符号化されて送信されたビットストリームを受信して復号化して外部に出力する軟出力復号器であって、
　受信した前記ビットストリームを記憶する受信値メモリと、前記受信値メモリに記憶された内容に基づいてトレリス線図における各時点ごとのブランチメトリックを生成するブランチメトリック生成手段と、前記ブランチメトリックを復号化して事後確率比を含む軟出力符号を出力する軟出力復号手段と、前記軟出力符号を事後確率比を含まない硬出力符号に変換して外部に出力する硬出力判定手段とを備え、
　前記軟出力復号手段が、前記ブランチメトリックを一時記憶するブランチメトリックメモリと、前記ブランチメトリックメモリに記憶されたブランチメトリックの符号トレリスの終端から各ノードへ到達するパスメトリックを推定処理するバックワード処理部と、前記ブランチメトリックメモリに記憶されたブランチメトリックの符号トレリスの先頭から各ノードへ到達するパスメトリックを推定処理するフォワード処理部と、前記バックワード処理部による推定処理の結果を記憶するパスメトリックメモリと、前記バックワード処理部および前記フォワード処理部による推定処理の結果から各時点での情報シンボルの事後確率比を算出してこれを前記軟出力符号として出力する軟出力生成処理部とを有すると共に、
　前記バックワード処理部が、相互に連結され前記符号トレリスの１時点ごとの前記推定処理に対応する複数個のバックワードプロセッサを備え、
　前記パスメトリックメモリが、前記バックワードプロセッサの各々に対応する複数の記憶域を備えることを特徴とする軟出力復号器。
（付記２）　前記バックワード処理部および前記フォワード処理部が、１サイクルに対して複数時点分の前記パスメトリックを推定処理することを特徴とする、付記１に記載の軟出力復号器。
（付記３）　前記フォワード処理部が、相互に連結され前記符号トレリスの１時点ごとの前記推定処理に対応する複数個のフォワードプロセッサを備え、
　前記パスメトリックメモリが、前記フォワードプロセッサの各々に対応する複数の記憶域を備え、
　前記軟出力生成処理部は、前記パスメトリックメモリに記憶された前記バックワード処理部および前記フォワード処理部による推定処理の結果から各時点での情報シンボルの事後確率比を算出することを特徴とする、付記１に記載の軟出力復号器。
（付記４）　前記バックワード処理部は、複数の前記バックワードプロセッサの中で最後段ではない前記バックワードプロセッサが前記パスメトリックメモリに記憶させるパスメトリックに対してＬｏｇ－ＭＡＰアルゴリズムに基づいて補正処理を行う補正処理部を備えることを特徴とする、付記１に記載の軟出力復号器。
（付記５）　前記軟出力復号手段は、複数の前記バックワードプロセッサの中で最後段ではない前記バックワードプロセッサが前記パスメトリックの選択情報を示すインデックスを記憶させるパスメモリを備え、
　前記軟出力生成処理部は、前記パスメトリックと前記インデックスとに基づいて前記情報シンボルの事後確率比を算出することを特徴とする、付記４に記載の軟出力復号器。
　以上、実施形態（及び実施例）を参照して本願発明を説明したが、本願発明は上記実施形態（及び実施例）に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
　この出願は２００９年１０月２２日に出願された日本出願特願２００９－２４２９１１を基礎とする優先権を主張し、その開示の全てをここに取り込む。
　本発明は、たとえば無線および有線通信、もしくは光ディスクなど、ビットストリームを復号化する用途全般に対して幅広く適用することができる。
　　１　伝送系統
　　１０、２１０、５１０　ターボ符号復号器
　　２０　アンテナ
　　２０ａ　光ピックアップ
　　３０　復調器
　　１０１　情報受信値メモリ
　　１０２、１０３　パリティ受信値メモリ
　　１０４、１０９　インターリーバ
　　１０５　ブランチメトリック生成手段
　　１０６　硬出力判定手段
　　１０７　デインターリーバ
　　１０８　外部情報メモリ
　　１１０、３１０、６１０　軟出力復号手段
　　１２０、１２０ｎ、３２０、６２０　バックワード処理部
　　１２１、１２２、１２１ａ、１２１ｂ、１２１ｎ、３２１、３２２、６２１　バックワードプロセッサ
　　１２３、１３３、１３４、１４１、１２３ｎ、１３４ａ、１３４ｂ、１３４（ｎ－１）、６４５　レジスタ
　　１３０、１３０ｎ、３３０　フォワード処理部
　　１３１、１３２、１３１ａ、１３１ｂ、１３１ｎ、３３１、３３２　フォワードプロセッサ
　　１４０、６４０　軟出力生成処理部
　　１４２、１４３、１４２ａ、１４２ｂ、１４２ｎ、６４２　軟出力生成プロセッサ
　　１５０　ブランチメトリックメモリ
　　１６０　パスメトリックメモリ
　　１６１、１６２、１６１ａ、１６１ｂ、１６１ｎ　パスメトリック記憶域
　　３２１ａ、３２１ｈ、３２２ａ、３２２ｈ、３３１ａ、３３１ｈ、３３２ａ、３３２ｈ、６２１ａ、６２１ｂ　算術加算回路
　　３２１ｉ、３２１ｌ、３２２ｉ、３２２ｌ、３３１ｉ、３３１ｌ、３３２ｉ、３３２ｌ　ｍａｘ回路
　　４００　補正処理部
　　４０１　差分手段
　　４０２　テーブル参照手段
　　４０３　加算器
　　４１０　簡易バックワードプロセッサ
　　４２０　テーブル
　　６２１ｉ、６２１ｏ、６２１ｒ　セレクタ
　　６２４ｉ　比較器
　　６７０　パスメモリ

Claims (5)

  1. 　符号化されて送信されたビットストリームを受信して復号化して外部に出力する軟出力復号器であって、
    　受信した前記ビットストリームを記憶する受信値メモリと、前記受信値メモリに記憶された内容に基づいてトレリス線図における各時点ごとのブランチメトリックを生成するブランチメトリック生成手段と、前記ブランチメトリックを復号化して事後確率比を含む軟出力符号を出力する軟出力復号手段と、前記軟出力符号を事後確率比を含まない硬出力符号に変換して外部に出力する硬出力判定手段とを備え、
    　前記軟出力復号手段が、前記ブランチメトリックを一時記憶するブランチメトリックメモリと、前記ブランチメトリックメモリに記憶されたブランチメトリックの符号トレリスの終端から各ノードへ到達するパスメトリックを推定処理するバックワード処理部と、前記ブランチメトリックメモリに記憶されたブランチメトリックの符号トレリスの先頭から各ノードへ到達するパスメトリックを推定処理するフォワード処理部と、前記バックワード処理部による推定処理の結果を記憶するパスメトリックメモリと、前記バックワード処理部および前記フォワード処理部による推定処理の結果から各時点での情報シンボルの事後確率比を算出してこれを前記軟出力符号として出力する軟出力生成処理部とを有すると共に、
    　前記バックワード処理部が、相互に連結され前記符号トレリスの１時点ごとの前記推定処理に対応する複数個のバックワードプロセッサを備え、
    　前記パスメトリックメモリが、前記バックワードプロセッサの各々に対応する複数の記憶域を備えることを特徴とする軟出力復号器。
  2. 　前記バックワード処理部および前記フォワード処理部が、１サイクルに対して複数時点分の前記パスメトリックを推定処理することを特徴とする、請求項１に記載の軟出力復号器。
  3. 　前記フォワード処理部が、相互に連結され前記符号トレリスの１時点ごとの前記推定処理に対応する複数個のフォワードプロセッサを備え、
    　前記パスメトリックメモリが、前記フォワードプロセッサの各々に対応する複数の記憶域を備え、
    　前記軟出力生成処理部は、前記パスメトリックメモリに記憶された前記バックワード処理部および前記フォワード処理部による推定処理の結果から各時点での情報シンボルの事後確率比を算出することを特徴とする、請求項１に記載の軟出力復号器。
  4. 　前記バックワード処理部は、複数の前記バックワードプロセッサの中で最後段ではない前記バックワードプロセッサが前記パスメトリックメモリに記憶させるパスメトリックに対してＬｏｇ－ＭＡＰアルゴリズムに基づいて補正処理を行う補正処理部を備えることを特徴とする、請求項１に記載の軟出力復号器。
  5. 　前記軟出力復号手段は、複数の前記バックワードプロセッサの中で最後段ではない前記バックワードプロセッサが前記パスメトリックの選択情報を示すインデックスを記憶させるパスメモリを備え、
    　前記軟出力生成処理部は、前記パスメトリックと前記インデックスとに基づいて前記情報シンボルの事後確率比を算出することを特徴とする、請求項４に記載の軟出力復号器。
PCT/JP2010/068021 2009-10-22 2010-10-14 軟出力復号器 WO2011048997A1 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2009242911 2009-10-22
JP2009-242911 2009-10-22

Publications (1)

Publication Number Publication Date
WO2011048997A1 true WO2011048997A1 (ja) 2011-04-28

Family

ID=43900224

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2010/068021 WO2011048997A1 (ja) 2009-10-22 2010-10-14 軟出力復号器

Country Status (1)

Country Link
WO (1) WO2011048997A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111211792A (zh) * 2018-11-22 2020-05-29 北京松果电子有限公司 Turbo译码方法、装置及系统

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002208219A (ja) * 2000-11-01 2002-07-26 Samsung Electronics Co Ltd 光ディスク用高倍速ビタビ検出器
JP2003289253A (ja) * 2002-03-28 2003-10-10 Mitsubishi Electric Corp 誤り訂正復号装置
JP2004096747A (ja) * 2002-08-30 2004-03-25 Lucent Technol Inc 高次基数のｌｏｇｍａｐプロセッサ

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002208219A (ja) * 2000-11-01 2002-07-26 Samsung Electronics Co Ltd 光ディスク用高倍速ビタビ検出器
JP2003289253A (ja) * 2002-03-28 2003-10-10 Mitsubishi Electric Corp 誤り訂正復号装置
JP2004096747A (ja) * 2002-08-30 2004-03-25 Lucent Technol Inc 高次基数のｌｏｇｍａｐプロセッサ

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
HSIANG-TSUNG CHUANG ET AL.: "A High-Troughput Radix-4 log-MAP Decoder With Low Complexity LLR Architecture", PROCEEDINGS OF THE INTERNATIONAL SYMPOSIUM ON VLSI DESIGN, AUTOMATION AND TEST, 2009. VLSI-DAT '09, 28 April 2009 (2009-04-28), pages 231 - 234, XP031485271 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111211792A (zh) * 2018-11-22 2020-05-29 北京松果电子有限公司 Turbo译码方法、装置及系统
CN111211792B (zh) * 2018-11-22 2023-05-30 北京小米松果电子有限公司 Turbo译码方法、装置及系统

Similar Documents

Publication Publication Date Title
JP3861084B2 (ja) 特に移動無線システム用とした、複合型ターボ符号／畳み込み符号デコーダ
US9337866B2 (en) Apparatus for processing signals carrying modulation-encoded parity bits
US7246298B2 (en) Unified viterbi/turbo decoder for mobile communication systems
JP4907802B2 (ja) 通信の復号化の際に用いられるバタフライプロセッサ装置
JP5840741B2 (ja) 複数のコード・タイプをプログラマブル復号する方法および装置
JP5700035B2 (ja) 誤り訂正符号復号装置、誤り訂正符号復号方法および誤り訂正符号復号プログラム
US8196006B2 (en) Modified branch metric calculator to reduce interleaver memory and improve performance in a fixed-point turbo decoder
US6487694B1 (en) Method and apparatus for turbo-code decoding a convolution encoded data frame using symbol-by-symbol traceback and HR-SOVA
US7549113B2 (en) Turbo decoder, turbo decoding method, and operating program of same
JP4432781B2 (ja) 誤り訂正復号器
KR101051933B1 (ko) 트렐리스의 버터플라이 구조를 이용한 맵 디코딩을 위한메트릭 계산
EP2339757A1 (en) Power-reduced preliminary decoded bits in viterbi decoder
JP3540224B2 (ja) ターボ復号器とターボ復号方法及びその方法を記憶した記憶媒体
KR100628201B1 (ko) 터보 디코딩 방법
Lin et al. Low power soft output Viterbi decoder scheme for turbo code decoding
WO2011048997A1 (ja) 軟出力復号器
JP2002076921A (ja) 誤り訂正符号復号方法及び装置
Weithoffer et al. Bit-level pipelining for highly parallel turbo-code decoders: A critical assessment
US7120851B2 (en) Recursive decoder for switching between normalized and non-normalized probability estimates
US7725798B2 (en) Method for recovering information from channel-coded data streams
JP7144621B2 (ja) 通信システム及び通信方法
US20050172203A1 (en) Decoder and method for performing decoding operation using map algorithm in mobile communication system
US8914716B2 (en) Resource sharing in decoder architectures
JP2001285079A (ja) 通信用誤り訂正符号復号装置
JP4525658B2 (ja) 誤り訂正符号復号装置

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 10824846

Country of ref document: EP

Kind code of ref document: A1

122 Ep: pct application non-entry in european phase

Ref document number: 10824846

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: JP