Butterfly processor used when decoding communication

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to decoding in wireless communication, and more particularly to a butterfly processor for decoding in wireless communication systems.

【0002】

[Conventional technology]

Communication systems handle the transmission of information from transmitters to receivers. Communication media through which information passes often include many sources of noise such as cosmic rays, Additive White Gaussian Noise (AWGN), Rayleigh scattering (multipath propagation) and electromagnetic noise. The presence of these noise sources impedes or interferes with the transmission of desired information and limits the ability to communicate.

【0003】

As is well known to those skilled in the art, the addition of redundant information calculated from source information improves the ability to correctly receive transmitted information by encoding the information to be transmitted. Decoding is the use of this redundant information in the received data to detect the presence of errors or estimate the most probable transmission bits. An error is detected when the transmitted redundant information is different from what was later calculated from the received data.

【0004】

Codeword weights are a measure of the ability to recover data from a codeword. Codewords with a large number of bits have a high weight. Low-weight codewords have a low ability to recover data, whereas high-weight codewords have a high ability to recover data.

【0005】

The automatic repeat request (ARQ) coding scheme uses an error detection code. If the presence of an error is detected in the received information, a message is sent from the receiver to the transmitter requesting that the relevant information be retransmitted. Although the ARQ coding method is relatively simple, it requires the use of feedback channels and the throughput is variable and relatively low.

【0006】

Forward error correction (FEC) coding schemes are used to encode information in systems where propagation delay and latency are an issue. The receiver can detect and correct errors without the need for a feedback channel.

【0007】

Coding methods can be broadly classified into block codes and convolutional codes.

【0008】

The block code maps a message of k information bits into a structured n-bit (where n> k) sequence. This code is called the (n, k) code. The ratio (nk) / k is called the redundancy of the code, and the ratio k / n of the number of information bits to the total number of bits is called the code rate (coding rate). The additional bits inserted provide redundancy and are used by the decoder to perform error detection and correction. The redundant bits added during coding depend only on the k information bits in the message block. Block codes are often used to detect errors when ARQ is implemented.

【0009】

Convolutional coding produces a block of n sign bits in a given period from k information bits. However, n and k are generally small. The n-bit block generated by the encoder depends not only on the k information bits of the period, but also on a predetermined number of message blocks generated during the preceding period. The memory provided for this coding makes it possible to correct errors based on the allowed code sequence. Convolution decoding can be performed using either the Viterbi algorithm or the logarithmic MAP algorithm.

【0010】

Convolution decoding is preferred for wireless voice communication systems where data retransmission and associated delays are not tolerated. Block codes are preferred for data transmission, where high throughput can be achieved and latency is less of an issue.

【0011】

A turbo code (also called a parallel articulated code) is a class of codes whose performance is very close to the Shannon capacitance limit. Turbo code is realized by connecting convolutional coders in parallel or in series to generate a concatenated output. The bit sequence that moves from one encoder to the next is replaced (sorted) by the interleaver. Thus, low-weight codewords produced by a single encoder are converted to high-weight codewords. Thus, turbo decoding receives two low-weight codewords and obtains the effect of much higher-weight codewords.

【0012】

Currently, wireless communication methods for consumers are mainly related to voice transmission. Such wireless communication methods include AMPS (Advanced Mobile Phone Services), GSM (Global System for Mobile Communication), and CDMA (Code Division Multiple Access). These represent first generation (1G) and second generation (2G) schemes. With the combination of data and voice communication methods, the 2.5th generation (2.5G) and 3rd generation (3G) methods, in which data transmission becomes more important, are beginning to emerge. Turbo block coding is preferred to achieve excellent error performance at high transmission rates. The latency inherent in block coding is not as important as in the case of voice transmission. UMTS (Universal Mobile Telecommunication) New third-generation mobile wireless standards such as Service) and CDMA2000 require turbo coding for data streams and convolutional coding for voice streams. These schemes require a complex turbo decoder for data and a Viterbi decoder for voice. In addition, backward compatibility requires support for second generation standards.

【0013】

[Problems to be Solved by the Invention]

Voice and data transmission presents competing requirements for transmission rate and latency / propagation delay. The current mainstream for solving such problems is to provide different coding schemes, namely turbo coding for data streams and convolutional coding for audio streams. As a result, different decoders are also required, resulting in multiple hardware platforms and increased carrier costs.

【0014】

A butterfly processor generally consists of a branch metric calculator and a large number of additive comparison and selection units. Known butterfly processors can perform Viterbi or logarithmic MAP calculations. Therefore, two butterfly processors are required to perform the Viterbi calculation and the logarithmic MAP calculation, resulting in extra hardware costs.

【0015】

[Means for solving problems]

According to the present invention, the butterfly processor device can perform convolution calculations and logarithmic MAP calculations. The butterfly processor device of the present invention includes a logarithmic sum correction device connected to a well-known comparison and selection element.

【0016】

A controllable switch that selectively connects to the output of the selection element and the log sum corrector is provided to produce the desired output of the butterfly processor. The present invention provides a reduction in hardware such that one butterfly processor can perform calculations that currently require two butterfly processors.

【0017】

BEST MODE FOR CARRYING OUT THE INVENTION

Preferred embodiments provide an integrated decoder architecture for wireless communication systems. The integrated decoder provides the decoding required for convolutional and turbo coded data streams. The integrated decoder architecture can support multiple data streams and multiple audio streams at the same time. In addition, the decoder can be dynamically split as needed to decode different standard audio streams. The preferred embodiment is modular and therefore easily scalable.

【0018】

Figure 1 shows the wireless communication network 100. The UMTS base station 110 has a transmitter / receiver 112, which has a decoder module 150a. The transmitter / receiver 112 communicates with another UMTS transmitter / receiver 146 having the decoder module 150f located at the remote base station 140 through the switching network 160. The transmitter / receiver 112 also communicates with the mobile handset 160a having the decoder module 150i. The transmitter / receiver 146 communicates with another mobile handset 160f having a decoder unit 150 m.

【0019】

The base station 140 further includes a transmitter / receiver 142 having the decoder unit 150d and a transmitter / receiver 144 having the decoder unit 150e. The transmitter / receiver 142 operates as a CDMA transmitter / receiver and is configured to communicate with a remote CDMA base station 130 having a CDMA transmitter / receiver 132 and a decoder unit 150c through an exchange network 160. The transmitter / receiver 142 also communicates with the mobile handset 160d having the decoder unit 150j. The transmitter / receiver 132 communicates with a mobile handset 160c having a decoder unit 150 g.

【0020】

The transmitter / receiver 144 communicates with a remotely located base station 120 having a transmitter / receiver 122 and a decoder unit 150b through an exchange network 160. The transmitter / receiver 144 also communicates with the mobile handset 160e having the decoder unit 150k. The transmitter / receiver 122 communicates with a mobile handset 160b having a decoder unit 150h.

【0021】

Decoder units 150a, 150b, 150c, 150d, 150e, 150f, 150g, 150h, 150i, 150j, 150k and 150m located on transmitters and receivers 112, 122, 132, 142, 144 and 146 and mobile handset 160a-160f , An example of an integrated decoder architecture configured to comply with different cellular network standards.

【0022】

The integrated decoder architecture in Figure 1 offers significant benefits in terms of flexibility and cost savings for telecommunications companies operating multiple network standards. This is because the same decoder block can be used to implement many different coding schemes in different network components.

【0023】

FIG. 2 shows a conventional communication system 200 in which coding is used to improve the transmission of information from the transmitter 210 to the receiver 270. The transmitter 210 has a source 205 that supplies the input data stream to the encoder 220. The encoder 220 has redundant information in the input data stream according to a pre-defined coding algorithm to improve the ability to detect and correct errors that may occur during the transmission of information as a result of noise sources present on the communication channel 240. Is added. The coded input stream is subsequently modulated to apply the coded data stream to the transmit waveform (230). The encoded information is transmitted through channel 240. Channel 240 has many noise sources 280 acting on it. Channel 240 couples to receiver 270. The receiver 270 has a demodulator 250 corresponding to the modulator 230, the demodulator 250 produces an output to the decoder 260, and the decoder 260 outputs a received information signal 275.

【0024】

FIG. 3 shows a communication system 200 in which the decoder 260 is a general Viterbi decoder. The input to the Viterbi decoder 260 is the coding information received from channel 240. The Viterbi decoder has a branch metric calculator (BMC) unit 289. The output of BMC unit 289 is provided to additive comparison selection (ACS) unit 291. The state controller 290 provides inputs to the BMC unit 289, ACS unit 291 and pathmetric memory 292. Path metric memory 292, a double buffered act in, replacing the ACS unit 291 and information. The borrow output 294 of the ACS unit 291 is provided to the traceback memory controller 293, and the output of the traceback memory controller 293 is the received information signal 275.

【0025】

FIG. 4 shows the turbo decoding configuration of the decoder 260 of FIG. The received symbol in the turbo decoder consists of tissue data representing the actual transmitted data and parity data. The first input 261 is the parity data of the received symbol and is provided to the demultiplexer 263. The first output 264 of the demultiplexer 263 is provided to the first decoder 266. The second input 262 is the tissue data of the received symbol and is provided to the first decoder 266. Recursive input 277 is also provided to first decoder 266. The output 267 of the first decoder 266 is provided to the interleaver 268, and the output 269 of the interleaver 268 is provided to the second decoder 271. The second output 265 of the demultiplexer 263 is also provided to the second decoder 271. The first output 272 of the second decoder 271 is provided to the first deinterleaver 274, and the output of the first deinterleaver 274 is the recursive input 277. The second output 273 of the second decoder 271 is provided to the second deinterleaver 276. The output of the second deinterleaver 276 is provided to the slicer 278, which applies a threshold value to the soft output and converts it to a hard output, which is used as the received information signal 275.

【0026】

The integrated decoder architecture of the preferred embodiment is intended to replace the decoder 260 in a wireless communication system that has both voice and data capabilities, providing the computational similarity required for Viterbi decoding and logarithmic MAP turbo decoding. Leverage to ensure that memory and processing units are used efficiently when configured for either of these schemes. Logarithmic MAP is an algorithm that can be used to decode the convolutional code. Log MAP is also used for half a cycle of turbo decoding iterations. By stacking the processors in a preferred embodiment and interconnecting them using a hierarchical switching structure, the processors can also operate independently as separate decoders, and one predetermined processor. It is also possible to combine processors to form a single fast decoder with the main processor as the primary processor.

【0027】

FIG. 5 shows the block architecture of the integrated decoder structure 900 according to the embodiment of the present invention. A multi-bit input symbol 901 from a pre-agreed encoding alphabet for a particular transmission is broadcast to the butterfly decoding processor bank 920. The butterfly decryption processor bank 920 also receives the output of the first store bank 940 as input. The control unit 960 provides inputs to the intermediate decoding result memory 910, the butterfly decoding processor bank 920, the first store bank 940, and the second store bank 950, respectively. The control unit 960 issues appropriate control signals through their inputs to perform convolutional or turbo coding as needed.

【0028】

The example of FIG. 5 is for a 1-row (row) decoder. When a plurality of decoder rows are interconnected to form a single decoder, the same multi-bit input symbol 901 is provided for each decoder row within the single decoder. When multiple decoder rows act as multiple decoders, each realized decoder is provided with a separate multi-bit input symbol 901.

【0029】

Butterfly decoding processor bank 920 produces first outputs 962, 964, 966 and 968, which are sent to second store bank 950 via bus 990. The output of the second store bank 950 is input to the first store bank 940. A typical example of a decoder typically uses a first store bank 940 and a second store bank 950 in double buffering mode.

【0030】

Butterfly decoding processor bank 920 produces second outputs 961, 963, 965 and 967, which are the intermediate decoding results provided to control unit 960.

【0031】

The butterfly decoding processor bank 920 and the loop feedback connection through at least one store form a loop function as a trellis processor.

【0032】

The intermediate decoding result memory 910 generates a decoding output 999. The intermediate decoding result memory 910 can provide a recursive result to the control unit 960 when calculating the logarithmic MAP algorithm (described later).

【0033】

FIG. 6 shows the block architecture of the integrated decoder 1200 according to a preferred embodiment of the present invention. The control unit 1210 of the integrated decoder 1200 receives multiple inputs including rate 1201, constraint length 1202, convolution / turbo selector 1203, polypoly 1204, trellis direction 1205, iterations 1206, block length 1207, clock 1208 and reset 1209. receive. Rate 1201 indicates the amount of information used to represent a single data bit present in the transmit block. The constraint length 1202 indicates the number of pre-input symbols used to encode the input information bits provided, and thus the complexity of the trellis processed to decode a given input symbol. It is also an indicator. Polynomial 1204 is a generated polynomial coefficient used in the decoding process. The number of iterations 1206 determines the number of loops performed by the decoder 1200 when operating in turbo mode. The larger the number of iterations 1206, the higher the accuracy of the decoding output 1294 at the expense of increased computation time.

【0034】

Control unit 1210 includes intermediate decoding memory processors 1240, log likelihood processors 1250a and 1250b, multiplexer bank 1250c, comparator 1247, butterfly decoding processor 1260, inverse address processor 1270, normalization subtractor 1278, multiplexer bank 1278a, pathmetric. Interconnected with store 1280, forward address processor 1290, log likelihood processor 1297 and input symbol history 1298. The control unit 1210 can implement either a convolutional decoder or a turbo decoder, if desired, by reconfiguring the architecture of the integrated decoder 1200 through these connections.

【0035】

Input symbol 1299 is provided in input symbol history 1298. The input symbol history 1298 acts as a double buffer to ensure that a constant data flow is maintained. The input symbol history 1298 also receives the input symbol history bank select 1211, the input symbol history address 1219, the input symbol history clock 1223 and the input symbol history reset 1225 from the control unit 1210. The input symbol history 1298 produces the first output 1291a and the second output 1291b. The first output 1291a is provided to the butterfly decoding processor 1260 and the second output 1291b is provided to the log-likelihood processor 1250a.

【0036】

The butterfly decoding processor 1260 also receives inverse trellis pathmetric 1265 from the inverse address processor 1270 and external information from the intermediate decoding memory processor 1240 as input. The control unit 1210 also provides the butterfly decoding processor 1260 with multiple inputs, including butterfly reset 1215, butterfly rate 1216, butterfly clock 1217, butterfly polynomial 1218, butterfly constraint 1220, butterfly mode 1221 and beta phase enable 1235.

【0037】

The butterfly decoding processor 1260 generates a new multi-bit path metric for a corresponding state in the trellis diagram. This new path metric is output on the 32-bit buses 1266 and 1267. The 32-bit buses 1266 and 1267 are connected to the comparator 1247 and the multiplexer bank 1250c. The butterfly decoding processor 1260 also generates decision bit 1255. The determination bit 1255 is input to the intermediate decoding memory processor 1240.

【0038】

In the first phase of the logarithmic MAP calculation, the butterfly decoding processor 1260 calculates gamma and alpha. In the second phase, the butterfly decoding processor 1260 calculates the beta using the dummy beta calculated by the log-likelihood processor 1250a and the log-likelihood processor 1250b in the first phase.

【0039】

As shown in FIG. 7, each butterfly processor in the butterfly processor bank 1260 includes two additive comparison and selection units (shown as ACS) 320 and an intermediate branch metric calculator (BMC) 330. The BMC330 performs the same functions as the Branch Metric Unit (BMU) in well-known Viterbi decoders, and each ACS320 performs pathmetric calculations for trellis decoding.

【0040】

FIG. 7 shows an exemplary butterfly unit of the butterfly processor 1260 of FIG. It has two additive comparison selection units 320 and one intermediate branch metric calculator 330. Each additive comparison selection unit 320 is provided with an input path metric of 0 (1265a) and an input path metric of 1 (1265b). The input symbol 1291a and the external information 1242 are broadcast to the respective branch metric calculator 330 in the butterfly processor bank 1260. The intermediate branch metric calculator is also provided with a butterfly rate 1216, a butterfly constraint 1220 and a butterfly polynomial 1218.

【0041】

Each state in one column of trellis has a pair of branch metrics leading to it. One symbol is associated with each branch metric. Therefore, following the trellis in a given orientation, one of the two possible symbols is expected for one state of interest, depending on the previous state. The BMC330 determines the measure of proximity of the received input symbol 1291a to the expected symbol. The BMC330 produces an output branch metric of 0 (406), which is provided to the first ACS unit 0 (320) and the second ACS unit 1 (320) via an m-bit wide bus. The BMC330 takes advantage of the trellis symmetry to generate a second branch metric 1 (402) by arithmetically flipping the branch metric 0 (406). Branch metric 1 (402) is also provided to first ACS unit 0 (320) and second ACS unit 1 (320) through an m-bit wide bus. Butterfly mode 1221 is provided for each ACS unit 320 and sets them appropriately for the encoding used. ACS unit 320 and BMC unit 330 also receive butterfly reset 1215, butterfly clock 1217 and beta phase enable 1235.

【0042】

.. Each ACS unit 320 produces two outputs. These outputs, in the case of ACS0 in FIG. 7, consist of a first output 1255a and a second output 1267a. The first output 1255a is a determination bit that takes the value of the comparison borrow bit, and indicates whether to select the upper or lower possible path metric. The determination bit with a value of 0 corresponds to the selection of the lower possible path metric, while the determination bit with a value of 1 corresponds to the selection of the upper possible path metric. The second output, 1267a, is a new multi-bit path metric for a corresponding state in the trellis diagram. ACS1 produces the corresponding outputs 1255b and 1267b.

【0043】

Figure 8 shows the architecture of ACS unit 0 (320) in Figure 7. Two pairs of inputs 402 and 1265b, and 406 and 1265a are provided for adders 410 and 412, respectively. The first input pair consists of the branch metric 1 (402) and the path metric 1 (1265b), and the second input pair consists of the branch metric 0 (406) and the path metric 0 (1265a). The components of each input pair are added by the adders 410 and 412, respectively, and the corresponding outputs 411 and 413 of the adders 410 and 412 are provided to the full subtractor 414. Outputs 411 and 413 are also provided in the first 2 to 1 multiplexer 420. The borrow output 1255a of the full subtractor 414 is supplied to the first multiplexer 420 to calculate the maximum input value MAX. Borrow bit 1255a is also provided as the output of ACS unit 320, with a value of 0 indicating that the lower path metric was selected and a value of 1 indicating that the upper path metric was selected.

【0044】

The second output 415 of the full subtractor 414 represents the difference between the two adder results 411 and 413 and is provided in the log sum correction table 440. The log sum correction table 440 adjusts the result of the new path metric to improve the accuracy of the result in the log region in the case of log MAP decoding when the output of the total subtractor 414 is small. The output 441 of the log sum correction table 440 is provided to the adder 460. Output 421 of the first multiplexer 420 is provided to the adder 460 and the second 2: 1 multiplexer 450. Result 461 from adder 460 is provided as a second input to the second multiplexer 450. The control signal in butterfly mode 1221 is also input to the second multiplexer 450 and is used to determine whether the Viterbi coding method or the logarithmic MAP coding method is being executed. The second multiplexer 450 produces output 451 which is fed to the cumulative register 470 and another multiplexer 480. The cumulative register 470 receives a butterfly reset 1215 and produces an output 472 to the multiplexer 480. The multiplexer 480 receives a beta phase enable 1235 as a select signal that selects output 451 when inactive and output 472 from cumulative register 470 when active. The selected output from the multiplexer 480 is the output path metric 1267a for ACS unit 320.

【0045】

The multiplexer bank 1250c receives the select signal 1258 from the control unit 1210. The select signal 1258 either has the butterfly path metrics 1266 and 1267 output from the butterfly processor 1260, or the path metrics generated by the log likelihood processor 0 (1250a) and the log likelihood processor 1 (1250b). Used to select. Butterfly path metrics 1266 and 1267 are selected during the Viterbi calculation. In the first phase of the logarithmic MAP calculation, the butterfly path metrics 1266 and 1267 are selected, while the butterfly decoding processor 1260 calculates gamma and alpha. At the same time, the log-likelihood processor 0 (1250a) computes the dummy beta. At the end of the first phase, the pathmetric generated by the log-likelihood processor 0 (1250a) is selected by the multiplexer bank 1205c to allow the beta to be calculated in the second phase of the log-likelihood calculation. Be broadcast.

【0046】

The multiplexer bank 1205c outputs a new path metric on the lower path metric bus 1295 and the upper path metric bus 1296. Buses 1295 and 1296 are connected to log-likelihood processors 1250a and 1250b, multiplexer bank 1278a and forward address processor 1290.

【0047】

The forward address processor 1290 receives forward trellis select 1232, forward trellis hold 1234, forward trellis transparent bit 1236 and pathmetric input MUX select 1238 from control unit 1210. These are used to configure the forward address processor 1290, depending on whether the integrated decoder 1200 is used to follow the trellis in the forward or reverse direction.

【0048】

Buses 1295 and 1296 provide a pathmetric apparently sequential list to the butterfly processor 1260 for the calculation of the next column of the trellis when the forward address processor 1290 is traversing the trellis in the forward direction. Sort the new path metrics received through. The forward address processor 1290 works transparently when following the trellis in the opposite direction.

【0049】

The pathmetric store 1280 receives the forward trellis pathmetric 1285 output from the forward address processor 1290, as well as the addressing information ADDR0 (1228a) and ADDR1 (1228b), pathmetric reset 1230, and pathmetric read / write from the control unit 1210. Receives clock 1231. The pathmetric store 1280 outputs the stored pathmetric 1276 to the multiplexer bank 1278a and the log-likelihood processors 1250a and 1250b.

【0050】

Multiplexer bank 1278a is used as an interconnect point for multiple decoder row configurations to receive storage path metrics 1276, control signals 1278b from control unit 1210, and new path metrics on buses 1295 and 1296. The multiplexer bank 1278a initializes the beta calculation during the logarithmic MAP calculation and produces output 1277 to the normalization subtractor 1278.

【0051】

The comparator 1247 receives the butterfly path metric from the butterfly decoding processor 1260 through buses 1266 and 1267 and determines the largest new path metric. This maximum new path metric is compared to the maximum stored path metric, and the larger of those two values is provided as normalized output 1246. The normalized output 1246 is sent to the normalized subtractor 1278 and the intermediate decoding memory processor 1240.

【0052】

The normalization subtractor 1278 receives the output 1277 from the multiplexer bank 1278a and subtracts the normalized output 1246 to ensure that the pathmetric is within the dynamic range of the architecture. The normalized pathmetric 1275 is output to the inverse address processor 1270 and the log-likelihood processors 1250a and 1250b. The inverse address processor 1270 also has a log-likelihood enable 1214 and a log-likelihood 0 enable 1203 as inputs.₀And log-likelihood 1 enable 1203₁, Reverse trellis select 1222, reverse trellis hold 1224 and reverse trellis transmission bit 1226 are received from the control unit 1210. The input from control unit 1210 is used to properly configure the reverse address processor 1270, depending on whether the decoder 1200 is following the trellis in the forward or reverse direction. The output of the reverse address processor 1270 is provided to the butterfly decoding processor 1260 as a reverse trellis path metric 1265.

【0053】

The inverse address processor 1270 rearranges the normalized path metrics so that the preferred sequence of path metrics is presented to the butterfly processor 1260 for the next column of trellis calculations as the trellis is traversed in the opposite direction. To. When following the trellis in the forward direction, the inverse address processor 1270 acts transparently.

【0054】

The log-likelihood processor 1250a has a log-likelihood mode 1214a, an inverse trellis hold 1224a, an inverse trellis transmission bit 1226a, a log-likelihood rate 1248a, a log-likelihood constraint 1249a, a log-likelihood clock 1251a, a log-likelihood reset 1252a, and a log-likelihood. Degree polypoly 1253a, log likelihood 0 enable 1203a₀, Log Likelihood Enable 1203a₁, Reverse trellis select 1222a, and select signal 1258a are received from the control unit 1210. The log-likelihood processor 1250a also receives as inputs the normalized path metric 1275, the output 1291b from the input symbol history 1298, the storage path metric 1276, the new path metric on buses 1296 and 1295, and the interleaver external information 1256. The log-likelihood processor 1250a produces a first output 1245a, which is provided to the log-likelihood ratio processor 1297. The log-likelihood processor 1250a also provides inputs 1266'and 1267' to the multiplexer bank 1250c.

【0055】

The second log-likelihood processor 1250b has corresponding inputs 1214b, 1224b, 1226b, 1248b, 1249b, 1251b, 1252b, 1253b, 1203b.₀, 1203b₁, 1222b and 1258b are received from the control unit. The log-likelihood processor 1250b also receives as inputs normalized path metrics 1275, stored path metrics 1276, interleaver external information 1256, and new path metrics on buses 1296 and 1295. The log-likelihood processor 1250b produces an output 1245b, which is provided to the log-likelihood ratio processor 1297.

【0056】

The log-likelihood processor 1250a is used to calculate the dummy beta in the first phase of the log-like MAP calculation. In the second phase of the log-map calculation, the log-likelihood processors 1250a and 1250b are used with the butterfly decoding processor 1260 to produce log-likelihood results for "1" and "0", respectively.

【0057】

The intermediate decoding memory processor 1240 acts as a buffer for producing output during the Viterbi calculation. During the logarithmic MAP calculation, the intermediate decryption memory processor 1240 acts as an extended store for the pathmetric store 1280. The intermediate decoding memory processor 1240 receives an intermediate decoding mode 1212, an intermediate decoding direction 1237, a spread input 1243, a read / write clock 1257, a reset 1259, and a clocking signal 1254 from the control unit 1210. Intermediate decoding memory processor 1240 also receives normalized output 1246 and decision bit 1255. Intermediate decoding memory processor 1240 provides external information 1242 and traceback processor output 1567 to log-likelihood-ratio processor 1297 and receives input 1293 from log-likelihood-ratio processor 1297. The intermediate decoding memory processor 1240 also outputs interleaver external information 1256 to log-likelihood processors 1250a and 1250b.

【0058】

The log-likelihood-ratio processor 1297 receives outputs 1245a and 1245b from log-likelihood processors 1250a and 1250b, as well as hard-soft output select 1213 and diffuse input 1243 from control unit 1210. The log-likelihood ratio processor 1297 also receives external information 1242 of the intermediate decoding memory processor 1240 and scrambled address data 1286 as inputs. The log-likelihood ratio processor 1297 produces a decoding output of 1294 and an output of 1293 to the intermediate decoding memory processor 1240.

【0059】

Outputs 1245a and 1245b represent the probabilities that the decoded output is "1" and "0", respectively. The log-likelihood ratio processor 1297 performs subtraction of outputs 1245a and 1245b in the log region. This is equivalent to performing division in the antilogarithm region. The result of this subtraction provides the decryption output 1294. The log-likelihood ratio processor 1297 also subtracts outputs 1245a and 1245b from external information 1242 to produce output 1293. This represents new external information.

【0060】

The sign of the maximum constraint length k is 2^k-1Generate a trellis diagram of the state. Figure 9 shows the 32-state raw trellis diagram 1000 corresponding to the code with a maximum constraint length of 6. Time S_tEach of the 32 states 1002 in the time S_{t + 1}Has two possible branch metrics that map to one of the 32 states 1004 in. For example, time S_tState 0 (1003) in is time S_t₊₁It has branch metrics 1006 and 1008 leading to state 0 (1009) and state 16 (1007) in.

【0061】

The 32-state raw trellis diagram 1000 can also be represented by 16 corresponding butterfly connections 1010 of the same trellis. As can be seen, the state pair in one column 1012 of the trellis is mapped to the corresponding state pair in the next column 1014 of the trellis. Time S_{t + 1}The trellis state 1014 in represents the resulting path metric. Each butterfly connection 1010 can also be processed by a single butterfly processor 1260. According to a preferred embodiment of the present invention, as shown in FIG. 6, four butterfly processors 1260 are provided. This makes it possible to calculate eight result pathmetric positions in each clock cycle.

【0062】

Figure 10 shows the resulting pathmetric position 1014 for a 32-state trellis diagram. The 32 result pathmetric positions are sorted into 4 columns 1022, 1024, 1026 and 1028. Each column contains eight result pathmetric positions generated by four butterfly processors.

【0063】

The trellis operation includes several sub-trellis operations, each corresponding to one clock cycle. 11A, 11B, 11C, 11D and 11E show a process in which preferred embodiments of the invention perform in-place pathmetric addressing. FIG. 11A shows the time t = 1. This corresponds to the first subtrellis operation, which inputs eight new path metrics 1112. New path metrics 1112 representing 0, 1, 2 and 3 are written to the first column of memory 1102 corresponding to upper memory block B0 in path metric store 1280, while path metrics 16, 17, 18 and 19 are 4 Written to hold registers 1114. Path metrics 16, 17, 18 and 19 are retained for one clock cycle before being written to memory. This is because the memory locations where they will be written will not be available until the next clock cycle when the calculation of the new path metric for trellis states 8-15 is complete.

【0064】

As shown in FIG. 11B, at the next clock cycle t = 2, eight more new path metrics 1122 are input. The pathmetric 1122 corresponding to the new pathmetric positions 4, 5, 6 and 7 is written to the first column of memory 1104 corresponding to the lower memory block B1 of the pathmetric store 1280. The contents of hold register 1114 are written to the second column of memory 1102 corresponding to B0 of the path metric store 1280, and new path metrics corresponding to pass metric positions 20, 21, 22 and 23 are new contents of hold register 1114. Written as.

【0065】

In the third clock cycle shown in Figure 11C, yet another group of new path metrics 1134 is provided. New path metrics corresponding to states 8, 9, 10 and 11 are written to the third column of memory 1102 corresponding to B0 in path metric store 1280, and the contents of hold register 1114 in states 20, 21, 22 and 23. Is written to the second column of memory 1104, which corresponds to B1 of the pathmetric store 1280.

【0066】

FIG. 11D shows the fourth clock cycle. During this clock cycle, the last eight new path metrics 1144 are provided. These new path metrics, corresponding to states 12, 13, 14 and 15, are written to the third column of memory 1104, which corresponds to B1 of the path metric store 1280, and hold registers corresponding to states 24, 25, 26 and 27. The contents of are written to the fourth column of memory 1102 corresponding to B0 of the path metric store 1280, and the new path metrics corresponding to states 28, 29, 30 and 31 are written to the holding register 1114.

【0067】

As shown in Figure 11E, the next clock cycle corresponding to t = 5 is required to write the contents of hold register 1114 to the fourth column of memory 1104 corresponding to B1 of the pathmetric store 1280.

【0068】

FIG. 12 shows the addressing of pathmetric columns for a 32-state trellis according to a preferred embodiment of the present invention. The addressing sequence 1150 of the pathmetric column corresponds to the read / write address of the pathmetric column. Each row in table 1160 has a symbol time n (S)._n), Symbol time n + 1 (S_{n + 1}) And symbol time n + 2 (S)_{n + 2}) Corresponds to different columns of the trellis diagram. As is clear, the movement of the address of the pathmetric column is periodic.

【0069】

Figures 11A to E are S_nFrom S_{n + 1}Shows progress to. The next clock cycle t = 6 is S_{n + 1}From S_{n + 2}Columns 0, 2, 1, and 3 will be executed to initiate the transition to and provide a sequential list of states to the ACS unit.

【0070】

13, 14a, 14b, 14c, 14d and 14e show the process of performing in-place pathmetric addressing while a preferred embodiment of the invention follows a reverse trellis. FIG. 13 shows the notation used in FIGS. 14a-e. FIG. 14a shows the time t = 1 and corresponds to the first subtrellis operation. First column C of memory A_0AThe path metric at is shifted to hold register 3010. In FIG. 14b, at time t = 2, the first column C of memory B_0BIs moved to hold register 3010, C_0AAnd C_2AFunction results in path metric C_0A And C_0B Are formed and these resulting path metrics are written to the first columns of memories A and B, respectively. In Figure 14c, the second column C of memory A_1AIs placed in the holding register 3010. Contents before the holding register C₀_BAnd C_2BFunction is the new path metric C_1A And C_1BForming a', these new path metrics are written back to the third columns of A and B, respectively.

【0071】

In Figure 14d, at time t = 4, C_1BIs written to the holding register 3010. C_1AAnd C_3AFunction is new path metric C_2A And C_2B Is generated and these new path metrics are written to the second columns of memories A and B, respectively. Figure 14e shows the inverse subtrellis operation corresponding to time t = 5, and at this time C_1BAnd C_3BFunction results in path metric C_3A And C_3B Are formed and these resulting path metrics are written to the fourth column of memories A and B, respectively. In the inverse trellis calculation, the path metric is scrambled and provided to the four butterfly processors, and the in-place path metric addressing described in FIGS. 14a-14e provides that the resulting path metric is provided sequentially (sequentially). Guarantee.

【0072】

FIG. 15 is a high-level schematic block diagram of an embodiment of the intermediate decryption memory processor 1240. It performs the traceback and interleaver functions of each decryption method. The intermediate decoding memory processor 1240 receives, as inputs, a determination bit 1255, a normalized output 1246, a spread input 1243, an intermediate decoding direction 1237, an intermediate decoding mode 1212, a clocking signal 1254, a read / write clock 1257, a reset signal 1259, and , Receives output 1293 from log-to-order likelihood processor 1297. The intermediate decoding memory processor 1240 produces an output that includes external information 1242, interleaver external information 1256, and traceback processor output 1567.

【0073】

FIG. 16 is an exploded view of the intermediate decoding memory processor 1240. The traceback address controller 1510 has input judgment bits 1255, intermediate decoding direction 1237, normalized output 1246, clock signal 1254, reset signal 1259, read / write clock 1257, and intermediate decoding mode 1212 inverted. receive. The traceback address controller 1510 produces output 1567.

【0074】

The traceback address controller 1510 writes decision bit 1255 to the window memory subsystem 1530 every clock cycle. During traceback, the traceback address controller 1510 inspects the trellis section to determine the maximum value to use as a starting point. It is not necessary to completely store the value for each state. This is because the new traceback byte address can be generated using one of the determination bits 1255.

【0075】

The interleaver controller 1520 also receives a clocking signal 1254, a reset signal 1259, a read / write clock 1257 and an intermediate decoding mode 1212. In addition, the interleaver controller 1520 also receives an output 1293 from the log-likelihood ratio processor 1297, a spread input 1243, and an intermediate decoding direction 1237. The interleaver controller 1520 generates external information 1242 and 1256. The external data 1242 is used as a recursive input to the butterfly processor 1260 when the decoder 1200 acts as a turbo decoder.

【0076】

The interleaver controller 1520 generates external information 1242 and 1256 at the beginning of each clock cycle. At the end of each clock cycle, the interleaver controller 1520 receives new external information in the form of output 1293 from the log-likelihood ratio processor 1297 and writes it to memory.

【0077】

The traceback address controller 1510 and interleaver controller 1520 are interconnected to supply the coupled read / write signal 1515 to the window memory subsystem 1530. The traceback address controller 1510, interleaver controller 1520 and window memory subsystem 1530 are further interconnected by the bidirectional data bus 1526 and address bus 1525. The interleaver controller 1520 has a second address bus 1535 connected to the window memory subsystem 1530, and the window memory subsystem 1530 produces output to the interleaver controller 1520 on the second data bus 1536.

【0078】

Figure 17 shows the traceback processor 1510. The determination bit 1255 is provided to the first multiplexer 1550. The output of the multiplexer 1550 is provided to the decision register 1555. The output of the determination register 1555 is data 1526, which is provided as the output of the traceback processor 1510, fed back as a recursive input of the first multiplexer 1550, and input to the bit select 1558.

【0079】

The intermediate decoding direction 1237 is input to the address translation unit 1560. The address translation unit 1560 also receives a read / write clock 1257 and produces an output address 1525 and a read / write signal 1515. The read / write clock 1257 is also provided as a select signal for the first multiplexer 1550.

【0080】

The normalized output 1246 is input to the status register 1562. The output of the status register 1562 is input to the address translation unit 1560 and also to the previous state unit 1564. The pre-state unit 1564 provides two inputs to the second multiplexer 1566, the output of the second multiplexer 1566 being the traceback processor output 1567.

【0081】

The output of BitSelect 1558 is input to the 1st AND gate 1568. The output of AND gate 1568 is input to status register 1562. The output of BitSelect 1558 is also provided to the second AND gate 1569, and the output of the second AND gate 1569 is also provided to the status register 1562.

【0082】

The intermediate decoding direction 1237 is provided to the first AND gate 1568 as a second input and serves as a select input for the multiplexer 1566. The intermediate decoding direction 1237 is also provided to the second AND gate 1569 via the NOT gate 1570.

【0083】

FIG. 18 shows the interleaver controller 1520 of FIG. Intermediate decoding mode 1212 is provided to AND gate 1580, and the output of AND gate 1580 is provided to two tristate buffers 1582 and 1583. The other input to the AND gate 1580 is the inverted version of the diffuse input 1243. The tristate buffer 1582 also receives a read / write clock 1257 as an input. The second tristate buffer 1583 receives the output 1293 from the log-likelihood ratio processor 1297 as its second input. The output 1293 from the log-likelihood ratio processor 1297 is also input to the two logical blocks 1584 and 1586. Spread input 1243, along with reset signal 1259 and clock signal 1254, is provided for logic blocks 1584 and 1586, respectively. The interleaver 1520 receives the data bus 1526 as input and provides the corresponding output as external information 1242. The second data bus 1536 is output as interleaver external information 1256. The data bus 1526 is bidirectional, and the output from the interleaver 1520 to the data bus 1526 is the output of the tristate buffer 1583.

【0084】

The first logical block 1584 receives the intermediate decoding mode 1212 and the intermediate decoding direction 1237 and generates the address 1525. The second logical block 1586 also receives the intermediate decoding mode 1212 and the intermediate decoding direction 1237 and generates the address 1535. Each of the logical blocks 1584 and 1586 also receives the input BETA_D. This is a low (LOW) or high (HIGH) power signal.

【0085】

FIG. 19 is an exploded view of the logic block 1584 of FIG. The logical block 1586 of FIG. 18 has the same configuration. Window count 1590 receives reset 1259, clock 1254, and enable 1212 as inputs. The window count 1590 also receives the output of the first adder 1592 as an input. The window count 1590 produces the output provided to the adders 1592 and 1593. The first adder 1592 receives the constant 1599 as the second input and provides the output to the window count 1590. Bitcount 1591 receives as inputs the outputs of reset 1259, clock 1254, enable 1212 and third adder 1594. The bit count 1591 produces the output provided to the two adders 1593 and 1594. BETA_D is provided in element 1595. Element 1595 adds 1 and, if BETA_D is active, takes a NOT value and provides the result as a second input to the 3rd adder 1594. The output of adder 1594 is provided as a recursive input to bit count 1591.

【0086】

The output of the second adder 1593 is input to the multiplexer 1596 and scramble 1597. The multiplexer 1596 receives a select signal indicating whether the architecture is acting as a first or second decoder. The second input is the output of the scrambled 1597. The output of the multiplexer 1596 is at address 1525. The scramble 1597 receives the spread input 1243 as an enable signal and the output 1293 from the log-likelihood ratio processor 1297 as data. The scramble 1597 can be a memory or logic function well known to those of skill in the art and is used to scramble addresses between the first and second decoders when performing turbo decoder calculations. To.

【0087】

FIG. 20 is a schematic block diagram of the window memory subsystem 1530 of FIG. Read / write clocks 1515, address buses 1525 and 1535, and data buses 1526 and 1536 are provided to the window address decoders 1530a and window memories 1530b to 1530d.

【0088】

FIG. 21 shows the log-likelihood processor 1250a of FIG. Banks 1410 of four butterfly units are provided, and ACS units 1412a to 1412h that make up this bank have a pair of inverse trellis path metrics 1415a to 1415h from the inverse address processor 1270b and a storage path metric 1276 that is path metric. Provided from store 1280. The storage path metric 1276 represents alpha in logarithmic MAP calculations. Each of the ACS units 1412a-1412h is also provided with a log-likelihood mode 1214a, a log-likelihood clock 1251a and a log-likelihood reset 1252a. Each of the BMC units 1414a-1414d is provided with multiple inputs including a log-likelihood rate 1248a, a log-likelihood constraint 1249a, a log-likelihood polynomial 1253a, interleaver external information 1256 and an input symbol history 1291b, respectively. The ACS units 1412a to 1412h generate the first output 1413a to 1413h. These first outputs are provided as ordered pairs to ACS node units 1420a-1420d. The ACS units 1412a to 1412h generate the second output 480a to 480h. Each of the second outputs 480a-480h is provided to the corresponding normalized subtractors 1470a-1470h. The normalized subtractors 1470a-1470h produce outputs 1266'and 1267'. These outputs are recursively fed to the inverse address processor 1270b via a multiplexer as described below and are used to ensure that the pathmetric remains within the dynamic range of the architecture.

【0089】

The multiplexers 1417a to 1417h constituting the first bank receive the corresponding normalized path metrics 1275a to 1275h from the normalized processor 1278 and the select signal 1258 from the control unit 1210, respectively. The multiplexers 1417a to 1417d also receive the corresponding path metrics 1296a to 1296d, and the multiplexers 1417e to 1417h also receive the corresponding path metrics 1295a to 1295d. Path metrics 1295a to 1295d and path metrics 1296a to 1296d represent betas in logarithmic MAP calculations. The select signal 1258 is used to determine whether the normalized path metrics 1275a to 1275h or the path metrics 1295a to 1295d and 1296a to 1296d will be output.

【0090】

The multiplexers 1416a to 1416h constituting the second bank each receive the log-likelihood mode 1214a as a select signal and the corresponding outputs from the multiplexers 1417a to 1417h in the first bank. The multiplexers 1416a to 1416d receive the third input, which is the output 1266' of the normalization subtractors 1470a to 1470d, and the multiplexers 1416e to 1416h receive the output 1267' from the normalization subtractors 1470e to 1470h. The output from the multiplexers 1416a to 1416h is input to the reverse address processor 1270b.

【0091】

The inverse address processor 1270b has log-likelihood mode 1214a, turbo-enabled 1203a for log-likelihood 0 enable.₀, Turbo enable for log likelihood 1 1203a₁, Reverse trellis select 1222a, reverse trellis transparent bit 1226a and reverse trellis hold 1224a are also received. The beta outputs 1266'and 1267' of the log-likelihood processor 1250a provide the final dummy beta value used to start the beta processing phase when the decoder 1200 is operating in log MAP / turbo mode. Represent.

【0092】

The output of ACS node units 1420a and 1420b is provided to ACS node unit 1430a, and the output of ACS node units 1420c and 1420d is provided to ACS node unit 1430b. The output of ACS node units 1430a and 1430b is input to yet another ACS node unit 1440a. The output of ACS node unit 1440a is provided in the multi-row comparator tree. This multi-row comparator tree spans the entire decoder so that when the decoder operates in a multi-row configuration, it captures the largest path metric calculated for the state of the trellis being examined. The output from the multi-low comparator tree is provided to the subtractor 1450 and register 1460. The subtractor 1450 also provides a recursive input to register 1460. The register output 1245a serves as a log-likelihood processor 1250a, and is supplied to the subtractors 1450 and the normalized subtractors 1470a to 1470h, respectively.

【0093】

FIG. 22 shows a configuration of the ACS node unit 1420a of FIG. Outputs 1413a and 1413b from the ACS leaf unit are input to comparators 1474 and multiplexer 1476. The borrow output of the comparator 1474 is supplied as a select signal of the multiplexer 1476. The difference output of the comparator 1474 is input to the logarithmic sum correction table 1478. The output of the log sum correction table 1478 is provided to the adder 1480, and the second input of the adder 1480 is the output of the multiplexer 1476. The adder 1480 calculates and outputs the sum 1425a of the two inputs. This sum 1425a, with logarithmic sum correction, represents the maximum value of the two inputs 1413a and 1413b.

【0094】

FIG. 23 shows the configuration of the log-likelihood processor 1250a of FIG. 6 for an 8-low decoder embodiment. The log-likelihood processor 1250a'of each row is interconnected via a bank of multiplexer 1490. Each multiplexer 1490 provides one input to the corresponding decoder row log-likelihood processor 1250a'. The pair of log-likelihood processor 1250a'inputs their output to the ACS node units 1420a', 1420b', 1420c' and 1420d'. The output of the log-likelihood processor 1250a'is also provided as a recursive input to the bank of the multiplexer 1490. The ACS node units 1420a', 1420b', 1420c' and 1420d' are paired in pairs and their output is input to yet another ACS node units 1430a'and 1430b'. The outputs of the ACS node units 1420a', 1420b', 1420c' and 1420d' are also provided as recursive inputs to the banks of the multiplexer 1490. ACS node units 1430a'and 1430b' provide their output to the final ACS node unit 1440' and to the bank of the multiplexer 1490 as recursive input. The output of the last ACS node unit 1440'is provided to the bank of the multiplexer 1490 as the last recursive input. A select signal is provided for each multiplexer 1490.

【0095】

Figure 24 shows one useful architecture for ACS unit 1412a in Figure 21. The first input pair, namely branch metric 1 (402 ) and branch metric 0 (406 ), is provided to the multiplexer 408, which produces output 402 . A second pair of inputs, Pathmetric 1276a and Pathmetric 1 (1415b), is provided to the multiplexer 409, which produces output 403'. Each of the multiplexers 408 and 409 receives log-likelihood mode 1214a as a select signal. When log-likelihood mode 1214a is active, branch metric 1 (402') is selected by multiplexer 408 and path metric 1415b is selected by multiplexer 409. On the other hand, when the log-likelihood mode 1214a is active, the branch metric 0 (406') is selected by the multiplexer 408 and the path metric 1276a (representing the alpha value) is selected by 409.

【0096】

The outputs 402 and 403 of the multiplexers 408 and 409 are provided to the adder 410 . The sum 411'is output from the adder 410'and is provided to the multiplexer 416' and the multiplexer 417'. The multiplexer 417'receives the branch metric 0 (406') as the second input and the log-likelihood mode 1214a as the select signal. The output 418'of the multiplexer 417' is provided to the adder 412'. Adder 412'receives pathmetric 0 (1415a) as the second input. The adder 412'generates the sum 413'. The sum 413'represents the sum of alpha, beta and gamma. The sum 413'is provided for the full subtractor 414' and the multiplexer 420'. The multiplexer 416'receives the wiring input 407' corresponding to the smallest two's complement that can be represented, and also receives the log-likelihood mode 1214a as a select signal. The full subtractor 414' also receives the output 408' of the multiplexer 416' as a second input and produces a borrow 361' and a difference 415'.

【0097】

The output 408'of the multiplexer 416' is provided as the first input of the multiplexer 420'. The multiplexer 420'receives the sum 413' of the adder 412' as the second input. The borrow output 361 of the full subtractor 414 is supplied to the multiplexer 420 to calculate the maximum input value MAX. The second output 415'of the full subtractor 414' represents the difference between the multiplexer output 408' and the sum 413' and is provided in the log sum correction table 440'. The logarithmic sum correction table 440'adjusts the result of the new path metric in order to improve the accuracy of the result in the logarithmic region in the case of logarithmic MAP decoding when the output of the total subtractor 414' is small. The output 441'of the log sum correction table 440'is provided to the adder 460'. Output 421'of multiplexer 420' is also provided for adder 460'. The result 490'from the adder 460' is input to the accumulator register 470'. Accumulation register 470'accumulates values for dummy beta logarithmic MAP calculation. The output of the cumulative register 480a is input to yet another multiplexer 475'and is provided as the output of ACS unit 1412a for use in dummy beta calculations. The multiplexer 475'receives the sum 490' as the second input and the log-likelihood mode 1214a as the select signal. The output 1413a of the multiplexer 475'is the second output of the ACS unit 1412a.

【0098】

FIG. 25 shows the butterfly decoding processor 1260 of FIG. 6 according to a preferred embodiment. Each of the component ACS units ACS0 through ACS7 is provided with multiple inputs, including butterfly mode 1221, butterfly reset 1215, butterfly clock 1217 and beta phase enable 1235. A butterfly rate 1216, a butterfly constraint 1220 and a butterfly polynomial 1218 are provided for each of the component BMC units BMC0 to BMC3. The reverse trellis path metric 1265 is fanned out to provide inputs 1265a to 1265h to ACS units ACS0 to ACS7 so that each ACS unit receives two reverse trellis path metrics. Reverse trellis path metrics 1265a and 1265b are provided for ACS units ACS0 and ACS1, respectively, reverse trellis path metrics 1265c and 1265d are provided for ACS units ACS2 and ACS3, respectively, and reverse trellis path metrics 1265e and 1265f are ACS. Provided to units ACS4 and ACS5, respectively, and inverse trellis path metrics 1265g and 1265h provided to ACS units ACS6 and ACS7, respectively. The BMC units BMC0 to BMC3 also receive external information 1242 and input symbol history input symbol 1291a as inputs.

【0099】

The butterfly decoding processor 1260 is preferably formed by eight ACS units and four BMCs and is configured as four butterfly processors as follows. (i) ACS0, BMC0, ACS1 (ii) ACS2, BMC1, ACS3 (iii) ACS4, BMC2, ACS5 (iv) ACS6, BMC3, ACS7 [0100]

The integrated decoder architecture takes advantage of the fact that each state in the trellis diagram is only affected by the other two states. The sign of the minimum constraint length k is 2^k-1Produces a trellis diagram of the state. A butterfly processor with two ACS units and one intermediate BMC unit is capable of handling two states in the trellis state diagram. Therefore, a total of eight ACS units are required to process a code with a constraint length of 4 in one clock cycle. To handle more states, processing may be performed over a larger number of clock cycles, or more butterfly processors may be provided.

【0101】

The ACS units ACS0 to ACS7 generate the corresponding outputs 1255a to 1255h, which together form the determination bit 1255. The new path metrics calculated by the ACS units ACS0 to ACS3 are provided as outputs 1267a to 1267d and sent to the upper new path metric bus 1267. The new path metrics calculated by the ACS units ACS4 to ACS7, 1266a to 1266d, are provided to the lower new path metric bus 1266.

【0102】

FIG. 26 shows the inverse address processor 1270 of FIG. The reverse address processor 1270 allows the path metrics to be delayed and rearranged to produce the desired path metric pattern. The reverse address processor 1270 can also act transparently so that the input path metrics are provided as output unchanged when the decoder 1200 is operating in forward trellis mode. The reverse address processor 1270 receives reverse trellis select 1222, reverse trellis hold 1224, reverse trellis transparent bit 1226, log likelihood mode 1214, log likelihood 0 enable 1203 as inputs.₀, Log Likelihood 1 Enable 1203₁, And receive the normalized path metric 1275. The normalized path metric 1275 fan-outs and corresponds the inputs pairs 1275a / 1275e, 1275b / 1275f, 1275c / 1275g, and 1275d / 1275h with the corresponding first bank multiplexers 1910a3, 1910b3, 1910c3 and 1910d3. Provided to multiplexers 1915a to 1915d in the second bank.

【0103】

The reverse trellis select 1222 is provided for each of the XOR gates 1920a to 1920d of the first bank. XOR gates 1920a and 1920c have log-likelihood 0 enable 1203₀The XOR gates 1920b and 1920d receive a log-likelihood of 1 enable 1203.₁To receive. Each XOR gate 1920a-1920d produces the corresponding XOR gate of the XOR gates 1925a-1925d of the second bank and the output provided to the multiplexers 1910a3-1910d3. Each of the XOR gates 1925a-1925d in the second bank receives the log-likelihood enable 1214 as the second input and produces an output to the corresponding multiplexer of the multiplexers 1915a-1915d in the second bank. As mentioned above, each multiplexer 1915a-1915d receives a pair of normalized path metrics. The output from the XOR gates 1925a-1925d acts as a select signal for selecting one of the normalized path metrics provided by each multiplexer 1915a-1915d. Each of the multiplexers 1915a to 1915d provides an output to the corresponding multiplexer of the multiplexers 1910b1, 1910d1, 1910f1 and 1910h1.

【0104】

The multiplexers 1910a3 to 1910d3 and 1915a to 1915d have a log-likelihood enable 1214 and a log-likelihood 0 enable 1203.₀And log-likelihood 1 enable 1203₁Different input pairs are provided depending on the value of. Log Likelihood 0 Enable 1203₀Is enabled for log-likelihood processor 0 and disabled for log-likelihood processor 1. Conversely, log-likelihood 1 enable 1203₁Is enabled for log-likelihood processor 1 and disabled for log-likelihood processor 0. Since the reverse address processor 1270 is used in several locations within the integrated decoder 1200, the reverse address processor 1270 must be able to handle different modes of operation. Log Likelihood Enable 1214 and Log Likelihood Enable 1203₀And 1203₁When is inactive, the inverse address processor 1270 is in Viterbi mode acting on the trellis produced by the non-organized convolutional code. When the log-likelihood enable 1214 is active, the inverse address processor 1270 performs inverse trellis switching for log-likelihood computation in the case of log-likelihood MAP decoding. Log Likelihood Enable 1214 is active, Log Likelihood Enable 1203₀And 1203₁When any of the above is active, the inverse address processor 1270 uses a recursive tissue code to perform appropriate switching for log-likelihood operations, as in turbo decoding. The XOR gate provides proper switching for the different modes of operation of the inverse address processor 1270.

【0105】

Each of the first bank multiplexers 1910a3-1910d3 produces the output provided to the corresponding latches 1910a2-1910d2. Each of the latches 1910a2 to 1910d2 receives a reverse trellis hold 1224 as an input and provides a delayed output as a second input to the corresponding multiplexer of the multiplexers 1910a1, 1910c1, 1910e1 and 1910g1.

【0106】

The inverse trellis transmission bits 1226 are broadcast to each of the multiplexers 1910a1 to 1910h1 in the third bank, and the multiplexers 1910a1 to 1910h1 in the third bank generate the corresponding path metrics 1265a to 1265h. The path metrics 1265a to 1265h are collectively provided as the reverse trellis path metric 1265, which is the output of the reverse address processor 1270. When the decoder 1200 is operating in the forward trellis direction, the reverse trellis transparent bit 1226 is set and the reverse address processor 1270 passes the normalized path metric 1275 unchanged to the reverse trellis path metric 1265.

【0107】

FIG. 27 shows the normalization subtractor 1278 of FIG. The normalized output 1246 is input to each of the subtractors 1610a to 1610h. The output 1277 of the multiplexer bank 1278a is provided as individual path metrics 1277a to 1277h, and these path metrics are provided to the corresponding subtractors 1610a to 1610h, respectively. The outputs 1275a-1275h of the subtractors 1610a-1610h form a normalized path metric 1275. The normalization subtractor 1278 subtracts the maximum pathmetric calculated while tracing the trellis and provided as the normalized output 1246 from the new pathmetric to ensure that the pathmetric value is kept within the dynamic range of the architecture. Used to do.

【0108】

FIG. 28 shows the comparator 1247 of FIG. 6 according to a preferred embodiment of the present invention. The butterfly path metric provided on bus 1267 is fanned out and produces inputs 1267a-1267d to the corresponding maximum value comparators 1710a-1710d. Similarly, the butterfly path metric provided on bus 1266 is fanned out and produces inputs 1266a-1266d to the corresponding maximum value comparators 1710e-1710h. The path metrics 1266a to 1266d and 1267a to 1267d are compared against each other, and the maximum path metric 1715 is output to the multi-low comparator tree shown in FIG. The multi-row comparator tree spans the decoder to capture the largest calculated path metric for the trellis state being examined when the decoder operates in a multi-row configuration. The output from the multi-low comparator tree is provided in register 1720. Register 1720 stores the maximum path metric calculated while traversing the trellis. Output 1716 is also input to subtractor 1730. Register 1720 provides a second input to the subtractor 1730. This input provides the maximum path metric calculated while traversing the trellis. This subtractor compares the maximum path metric calculated while traversing the trellis with the maximum path metric 1715, and if the maximum path metric just calculated 1715 is greater than the maximum path metric calculated while traversing the trellis. The load signal 1735 is enabled for register 1720 and the maximum path metric 1715 is loaded into register 1720 to be the maximum path metric calculated while traversing the trellis. This register provides another output, which is the normalized output 1246, which is supplied to the normalized subtractor 1278 and the intermediate decoding memory processor 1240. Normalized output 1246 is used to ensure that the calculated pathmetric values remain within the dynamic range of the architecture.

【0109】

FIG. 29 shows the pathmetric memory 1280 of FIG. 6 according to a preferred embodiment. A pathmetric reset 1230 and a pathmetric read / write clock 1231 are provided for memory units 1810a-1810h, respectively. The upper memory blocks 1810a to 1810d are grouped as B0 and receive the input ADDR0 (1228a). On the other hand, the lower memory blocks 1810e-1810h are grouped together to form B1 and receive the corresponding input ADDR1 (1228b). Pathmetric store 1280 receives forward trellis pathmetric 1285, which is fanned out and provides pathmetrics 1285a to 1285h for each of the corresponding memory blocks 1810a-1810h, as shown. The pathmetric store 1280 buffers the forward trellis pathmetric 1285 for one trellis processing cycle and then produces outputs 1276a to 1276h, which together form the storage pathmetric 1276.

【0110】

FIG. 30 shows the forward address processor 1290 of FIG. 6 according to a preferred embodiment of the present invention. The forward address processor 1290 allows the pathmetrics to be delayed and reordered to produce the desired pathmetric pattern. The forward address processor 1290 can also act transparently so that the input path metrics are provided as output unchanged when the decoder 1200 is operating in reverse trellis mode. The upper pathmetric bus 1296 is divided into component pathmetrics 1296a to 1296d, which are provided for two multiplexers 2010a and 2010b, as shown. Each of these multiplexers receives two input path metrics. The lower pathmetric bus 1295 is divided into component pathmetrics 1295a-1295d, which are provided for two multiplexers 2010c and 2010d, as shown. Each of these multiplexers receives two input path metrics. The multiplexers 2010a to 2010d each receive a forward trellis select 1232. The forward trellis select 1232 indicates whether the provided path metrics 1296a to 1296d or 1295a to 1295d should be selected.

【0111】

Each of the multiplexers 2010a to 2010d supplies output to the corresponding holding registers 2015a to 2015d. Hold registers 2015a to 2015d each receive forward trellis hold 1234 as input. The purpose of multiplexers 2010a-2010d and holding registers 2015a-2015d is to delay some of the pathmetrics 1296a-1296d and 1295a-1295d by one clock cycle as part of in-place pathmetric addressing.

【0112】

Each of the holding registers 2015a-2015d produces the output provided to the multiplexer bank 2020, as shown. The other input of the multiplexer bank 2020 is the path metric of the components of the upper path metric bus 1296 and the lower path metric bus 1295, as also illustrated. Pathmetric Input Multiplexer Select 1238 is broadcast to Multiplexer Bank 2020. Multiplexer bank 2020 produces output to a second multiplexer bank 2030. The other input of the second multiplexer bank 2030 is the path metric of the components of the upper path metric bus 1296 and the lower path metric bus 1295. A forward trellis transparent bit 1236 is provided to the second multiplexer bank 2030 and is used to make a transparent path when the decoder 1200 is operating in reverse trellis mode. The multiplexer bank 2030 generates path metrics 1285a to 1285h. These path metrics are combined to form the forward trellis path metric 1285, which is the output of the forward address processor 1290.

【0113】

FIG. 31 shows the comparator 1247 of FIG. 6 when used in an 8-low decoder configuration. The comparator 1247'of each row is interconnected via a bank of multiplexer 2100. Each multiplexer 2110 provides a single input to the corresponding comparator 1247'in the corresponding decoder row. A pair of comparators 1247'input their outputs 1715 into ACS node units 1420a , 1420b , 1420c and 1420d . Each of these ACS node units spans two rows of decoders. Output 1715 of comparator 1247'is also provided as a recursive input to the bank of multiplexer 2110. The ACS node units 1420a , 1420b , 1420c and 1420d are paired in pairs and their output is input to yet another ACS node unit 1430a and 1430b . The outputs of the ACS node units 1420a , 1420b , 1420c and 1420d are also provided as recursive inputs to the banks of the multiplexer 2110. ACS node units 1430a and 1430b provide their output to the final ACS node unit 1440 and to the bank of the multiplexer 2110 as recursive input. The output of the last ACS node unit 1440 is provided to the bank of the multiplexer 2110 as the last recursive input. A select signal is provided to each multiplexer 2110.

【0114】

FIG. 32 shows the configuration of the input symbol history 1298 in FIG. 6, including the address controller. The input symbol history address 1219 is input to the window decoder 2210. The window decoder 2210 decodes the address to allow access to the first double buffer memory bank 0 (2216) and the second double buffer memory bank 1 (2218). Input symbol history 1298 double buffers the received input to ensure that continuous data flow is maintained. The input symbol history clock 1223 and the input symbol history reset 1225 are provided to counter 2212, and the output 1297a of counter 2212 is also provided to double buffer memory bank 0 (2216) and double buffer memory bank 1 (2218). .. The input symbol 1299 is provided by the host processor to the demultiplexer 2214. The demultiplexer 2214 produces output 2224 to dual buffer memory bank 0 (2216) and output 2226 to dual buffer memory bank 1 (2218). The demultiplexer 2214 also receives a read / write signal 1297b as an input. The read / write signal 1297b is also supplied to the first multiplexer 2220 and the second multiplexer 2222. A bank select signal 1211 is provided for each of the double buffer memory bank 0 (2216) and the double buffer memory bank 1 (2218). However, the bank select signal 1211 is inverted at the interface to the dual buffer memory bank 1 (2218).

【0115】

Double buffer memory bank 0 (2216) produces a first output 2228 to the multiplexer 2220 and a second output 2230 to the second multiplexer 2222. The dual buffer memory bank 1 (2218) produces a corresponding first output 2232 supplied to the multiplexer 2220 and a second output 2234 provided to the second multiplexer 2222. The first multiplexer 2220 produces an output 1291b input to the log-likelihood processor 0 (1250b). The second multiplexer 2222 produces an output 1291a input to the butterfly processor 1260.

【0116】

FIG. 32 also shows an exploded view of double buffer memory bank 1 (2218). Input data 2226 is provided to the 1-to-n demultiplexer 2240. The 1-to-n demultiplexer 2240 also receives a window select, which is the output of the window decoder 2210. The n outputs from the demultiplexer 2240 are provided to n corresponding windows W0-Wn. Each of these windows produces the output provided to the first m-to-1 multiplexer 2242 and the second m-to-1 multiplexer 2244. Each of the m to 1 multiplexer 2242 and 2244 also receives a window select input signal. The first m-to-1 multiplexer 2242 produces output 2232, which output is used for dummy beta computation and is sent to the log-likelihood processor 1250a. A second m-to-1 multiplexer 2244 produces an output of 2234, which output is used to calculate alpha and beta in the branch metric unit of butterfly processor 1260.

【0117】

FIG. 33 shows the log-likelihood ratio processor 1297 of FIG. The log-likelihood ratio processor 1297 receives inputs 1245a and 1245b. These inputs are the outputs from the log-likelihood processor 1250a and the log-likelihood processor 1250b, respectively. The log-likelihood ratio processor 1297 also receives external information 1242, hardware / soft output select 1213, spread input 1243, traceback process output 1567, and scrambled address data 1286 as inputs.

【0118】

The subtractor 2310 receives inputs 1245a and 1245b, which represent the likelihoods of "1" and "0", respectively, and produces output 2315, which is supplied to the second subtractor 2320. The output 2315 of the subtractor 2310 is also supplied to the first multiplexer 2330 and forms part of the output 1294. The second input to the subtractor 2320 is external information 1242. The output 2325 of the subtractor 2320 is provided to the second multiplexer 2340.

【0119】

Traceback process output 1567 is provided as a second input to the first multiplexer 2330. The hard / soft output select 1213 is provided as the select input of the multiplexer 2330, and the output of the multiplexer 2330 forms 0 bits of the decoding output 1294. The output 2315 of the subtractor 2310 is combined with the least significant bit of the output of the multiplexer 2330 to form the multi-bit decoding output 1294.

【0120】

The second multiplexer 2340 receives the scrambled address data 1286 as the second input and the spread input 1243 as the select signal. The second multiplexer 2340 produces an output 1293, which output is supplied from the log-likelihood ratio processor 1297 to the intermediate decoding result memory 1240.

【0121】

The embodiment shown in FIG. 5 operates in a five-phase mode. Because there is no likelihood processor, in order to store more alpha and beta in the calculations performed by the log-likelihood processors 1250a and 1250b in the example of Figure 6 (which operates in two-phase mode). More pathmetric memory is needed.

【0122】

[Operation] The first step in the operation of the decoder 1200 is to initialize the decoder so that the architecture achieves the required configuration for either convolutional decoding or turbo decoding. The variables available for the operation include the number of columns required for the trellis size in question, the number of states in the trellis, the mask for the appropriate number of bits used to address the columns in pathmetric memory, and the trace. There is a judgment depth of the back process. The register holding the survival path metric of the symbol to be processed is initialized, and the sequence number whose value is replaced at each symbol time is assigned to the register bank to reflect the column address order required for each trellis operation. ..

【0123】

The decoder 1200 can operate in either the forward trellis direction or the reverse trellis direction.

【0124】

When following the trellis in the forward direction, the reverse address processor 1270 is configured to operate in transparent mode by setting the reverse trellis transparent bit 1226. When tracing the trellis forward, the sequence number is rotated to the left after the first use.

【0125】

The iterative process is started by reading the path metric from the B0 and B1 columns of the path metric store 1280 corresponding to the iteration number. A sequential list of path metrics held in the first column of 1280 B0 and 1280 B1 is provided to the butterfly processor 1260. The butterfly processor 1260 generates a new path metric via the multiplexer bank 1250c. This new path metric is no longer in destination state order, but is supplied to the forward address processor 1290. The forward address processor 1290 effectively performs a sort operation on each column of the new pathmetric, resulting in a set of sequential states as columns B0 and B1 in pathmetric memory 1280 read through the columns. Will be represented. During each column operation, half of the eight new path metrics are written directly to the path metric store 1280, while the remaining new path metrics are in the forward address processor 1290, as shown in Figures 11A-11E. It is written to the holding registers 2015a to 2015d. This alternates for each group of path metrics.

【0126】

Tracing the forward trellis requires as many iterations as there are columns. This number is one more than the number of columns required for the particular trellis in question. If the iteration number is even, the pathmetrics from buses 1296A, C, E, G are written to the column in Pathmetric Store 1280 B0 corresponding to the iteration number. The path metrics from buses 1296B, D, F, and H are written to the holding registers 2015a to 2015d of the forward address processor 1290 at the same time.

【0127】

On the other hand, in the case of the odd-numbered iteration, the path metric from the bus 1296A, C, E, G is written to the holding registers 2015a to 2015d of the forward address processor 1290, and the path metric from the bus 1296B, D, F, H is written. Is written to the pathmetric store 1280 column that corresponds to the repetition number.

【0128】

During column operation, the determination bits 1255 generated by the ACS unit of the butterfly processor 1260 are grouped into 1 byte and written to the intermediate decoding memory processor 1240. The next iteration in the process is initiated by reading the column address from B0 and B1 of the pathmetric store 1280 that corresponds to the number of the next iteration. The iterative process continues until the number of column iterations matches a number that is one greater than the number of columns required for the trellis being calculated.

【0129】

Another write operation is required at the end of the iterative process to transfer the four new path metrics in the hold register of the forward address processor 1290. These four new path metrics will be written to the final column of path metric store memory 1280B1. The end result is that the new path metrics were written to B0 and B1 of the path metric store 1280 in a different column order. The order in each column has not changed.

【0130】

When following the trellis in the opposite direction, the sequence number is used only after it has been rotated to the right. A group of four pathmetrics is fetched from the first column of the pathmetric store 1280 B0 and placed in a holding register in the inverse address processor 1270. The forward address processor 1290 is configured to operate in transparent mode by setting the forward trellis transparent bit 1236. The corresponding reverse trellis transparent bit 1226 is configured to enable the reverse address processor 1270. Tracing the reverse trellis was described in FIGS. 13 and 14.

【0131】

Tracing the trellis in the opposite direction requires a number of iterations equal to one greater than the number of columns required for that particular trellis. When tracing the trellis in the opposite direction, the in-place pathmetric method always provides a list of scrambled pathmetrics through the inverse address processor 1270 and produces a non-sequential list of pathmetrics to the butterfly processor 1260. The resulting trellis state order generated by the butterfly processor 1260 is the trellis state order.

【0132】

For even-numbered iterations, columns in pathmetric store 1280 B0 equal to the iteration number plus 1 are read and passed through the multiplexer 1278a, normalization processor 1278 and reverse address processor 1270 to butterfly processor 1260. Is passed. The path metrics currently held by the reverse address processor 1270 are also read into the butterfly processor 1260. Columns in the pathmetric store 1280 equal to the repetition number are read and written to the holding register of the inverse address processor 1270.

【0133】

If the iteration number is odd, the column in Pathmetric Store 1280 B1 equal to the iteration number plus 1 is read, passed through the multiplexer 1278a and the normalization processor 1278 to the inverse address processor 1270, and then the butterfly processor. Passed to 1260. The path metric held by the reverse address processor 1270 is also input to the butterfly processor 1260. The column of pathmetric store 1280 equal to the repetition number is read and written to the holding register of the inverse address processor 1270.

【0134】

Tracing the reverse trellis At this point, the reverse address processor 1270 is provided with a sequential list of path metrics held in the first column of B0 and B1 of the path metric store 1280. The reverse address processor 1270 performs a sort operation on each column of the new path metric in the sense that the resulting columns provided to the butterfly processor 1260 are no longer in destination state order. Butterfly processor 1260 generates eight new path metrics, which are provided to forward address processor 1290 via multiplexer bank 1250c. Because the forward address processor 1290 is in transparent mode, the pathmetric trellis state-ordered list generated by the butterfly processor 1260 is written back to B0 and B1 of the pathmetric store 1280 via the multiplexer bank 1250c. B0 and B1 of the pathmetric store 1280 represent a set of sequential states as you read through the columns.

【0135】

During column operation, the determination bits 1255 generated by the ACS unit of the butterfly processor 1260 are grouped into 1 byte and written to the intermediate decoding memory processor 1240. The next iteration begins by reading the appropriate pathmetric column from B0 and B1 of the pathmetric store 1280.

【0136】

At the end of the iterative process, the new path metric returns to B0 and B1 of the path metric store 1280 in a different column order. The order in each column has not changed.

【0137】

Since the traceback processor 1510 in the intermediate decoding memory processor 1240 performs a well-known pointer-type traceback operation, it knows the trellis processing direction and the bit position of the determination bit. The decision bit is extracted from 1 byte and used to generate the next pointer into the traceback memory 1530. Traceback ends when a predetermined traceback depth is reached. The traceback depth is generally between 5 and 9 times the constraint length of the sign.

【0138】

When the decoder 1200 is used for turbo decoding, the processing is divided into two different phases: dummy beta / alpha processing and beta / LLR processing. Either forward trellis or reverse trellis, unless the number of trellis states is degraded to be an integer (power of 2) multiple of the ACS unit size of butterfly processor 1260 and match the number of ACS units ACS0 through ACS7. The above processing is performed when the operation of is mentioned. The ACS units in the log-likelihood processor 0 (1250a) and the butterfly processor 1260 are each provided with registers that allow each ACS unit to accumulate the results required for alpha and beta calculations.

【0139】

Dummy beta and alpha calculations are done in parallel. The log-likelihood processor 0 (1250a) is free to use the leaf ACS unit to perform dummy beta calculations. This calculation requires access to the input symbol history buffer and the intermediate decryption memory processor interleaver memory, each of which is a window memory system. The input symbol history buffer is organized as banks 2216 and 2218 of the size of the processing window. The log-likelihood processor 0 (1250a) accumulates dummy betas by processing the window to be processed at time t + 1 at time t. Log-likelihood processor 0 (1250a) does not require access to the pathmetric store 1280. This is why the log-likelihood processor 0 (1250a) can operate in parallel with the ACS unit contained within the butterfly processor 1260.

【0140】

Log-likelihood processor 0 (1250a) performs normalization on dummy beta values by using an adder in the ACS tree to determine the calculated maximum beta. This maximum is subtracted from the input to the leaf ACS unit of log-likelihood processor 0 (1250a) before it is used.

【0141】

Butterfly processor 1260 performs alpha calculations and accumulates alpha values in registers within the component ACS unit. Butterfly processor 1260 performs forward trellis operations and normalization in the same way that it is done while tracing forward trellis.

【0142】

The dummy beta calculated by the log-likelihood processor 0 (1250a) is provided to the butterfly processor 1260 at the beginning of the beta calculation phase.

【0143】

During the beta calculation, both the log-likelihood processors 1250a and 1250b are used with the butterfly processor 1260. Each of the log likelihood processors 1250a and 1250b receives alpha from the pathmetric store 1280, beta from the previous clock cycle, and external information 1242 generated from the intermediate decoding memory processor 1240, respectively. Generates log likelihood results for "1" and "0". The log-likelihood calculation can span multiple rows. This is because the calculation determines the result of the maximum value over the previous state.

【0144】

The beta calculation, unlike alpha, works in the opposite direction through the input symbol history window and uses the gamma used in the alpha calculation. The beta calculation uses the same trellis branch metric assignments used in the alpha calculation.

【0145】

After the entire block of input history has been processed and the resulting output has been fed to the interleaver 1520, the process can begin the second half of the turbo decoding operation. The interleaver operations during the first decoder operation are sequential read and sequential write. On the other hand, during the second decoder operation, the interleaver reads and writes using the random address order determined by the scrambler address output. During the second decoder operation, the read (read) and write (write) addresses are the same. The interleaver operation after the first decoder is sequential in writes, but random in reads, and follows a predefined diffusion sequence used to give the first and second decoders statistical independence. .. In the interleaver operation of the second decoder, the writing is random according to the diffusion sequence, and the reading is sequential.

【0146】

Since the encoders used for turbo coding do not have to be the same, the decoding rate and constraints of the second decoder are not necessarily the same as those of the first decoder. Therefore, it may be necessary to change the configuration of the turbo decoder between the block processing operations. In that case, this is easily dealt with by manipulating the contents of the configuration register.

【0147】

Each block of input symbol history requires several complete turbo iterations to perform decoding within the acceptable bit error rate. The required number of iterations can be set to ensure that the required bit error rate is achieved.

【0148】

The advantage of the architecture of the present invention is that only two phases are required to complete one turbo decoding iteration. This provides flexibility in the use of the architecture and makes it possible to balance the number of decoder rows used with the number of iterations required. For example, a turbo decoder with four iterations can be achieved using two decoder rows that require two iterations.

【0149】

The logarithmic MAP calculation is performed using a sliding window algorithm. The sliding window algorithm is realized in two phases. For a single decoder, this results in increased latency (2 passes for each window, as shown in the configuration in Figure 34A (only a single decoder is used)). The first pass calculates the dummy beta value and the forward alpha value in parallel and stores the forward alpha value in alpha memory (Note: this memory is the same memory used by the Viterbi algorithm for pathmetric storage. Is). The second pass reads the alpha value, calculates the beta value according to the log-like MAP algorithm, and outputs the log-likelihood ratio (LLR).

【0150】

When using multiple decoders, it is possible to superimpose two-phase calculations, which can process one block with low latency. Multiple decoders can also operate individually for different data streams, or work together to increase the decoding rate of a single stream, as shown in the configuration in Figure 34B. Is also possible. The implementation shown in Figure 5 is to process 4 independent streams, 2 streams at high speed (low latency), or 1 stream at high speed (minimum latency). Is possible.

【0151】

Table 1 illustrates the flexibility of an integrated decoder that supports multiple coded streams at the same time. For example, a decoder with four decoder rows can process up to four data streams at the same time. In addition, decoder rows can work together to decode fewer streams with higher throughput. This is useful for minimizing the latency of voice decoding. Table 1 illustrates the flexibility of this approach and the appropriate decoding speeds that can be obtained in each case (note that this list is by no means complete and is even higher by combining more decoder rows with each other. Flexibility can be achieved).

[table 1]

<img file="JP2002176366A_D0001.tif" />【0152】

To illustrate how two or four decoders can work together to decode a smaller number of data streams at high speed, Figure 35 shows the interconnection between the two decoders. Is shown. The box marked "M" is a multiplexer that allows some of the path metrics from the next decoder to be swapped before being written to the path metric memory. In addition, in Figure 36, how four decoders can be interconnected to act as either a single decoder, two decoders, or four decoders. Indicates.

【0153】

To demonstrate the multi-standard compatibility of the integrated decoder, the decoder supports any combination of standards shown in Table 2. (This list is by no means complete, but it is provided to demonstrate the flexible (and therefore useful) nature of this integrated decoder.

[Table 2]

<img file="JP2002176366A_D0002.tif" />【0154】

The integrated decoder 900 provides the decoding required for convolutional coded data streams and turbo coded data streams and can support multiple data streams and multiple audio streams simultaneously. When decoding a turbo-coded data stream, the decoder implements an iterative turbo decoder using either the maximum-log MAP algorithm or the log MAP soft output MAP algorithm. The decoder maximizes reuse of its components to enable efficient realization of both convolution and turbo decoding schemes.

【0155】

The decoders of the present invention can be dynamically partitioned as needed to decode different standard audio streams. The decoder of the present invention can process streams at different coding rates (rate 1/2, rate 1/3, rate 1/4, etc.). The decoder of the present invention can also process streams encoded with different constraint lengths. Therefore, the integrated decoder architecture of the present invention is capable of supporting each of the currently defined mobile wireless standards (1st, 2nd and 3rd generation for both voice and data).

【0156】

The integrated decoder architecture of the preferred embodiment incorporates the functionality of a non-organized (feedforward) and tissue (feedback word) encoder into a single architecture. Figure 37A shows the mixing of polynomial 3240 and state bit 3250 to generate one sign bit 3225_0 for codeword 3225. The polynomial 3240 is provided for the corresponding AND gate 3260. This AND gate 3260 also receives state 3250 as input. Each AND gate 3260 produces an output to the corresponding XOR gate 3270. Each XOR gate 3270 also receives a transition input 3280 and produces an output 3225_0 for the M-bit non-organizational encoder 3230.

【0157】

Figure 37B shows the entire encoder 3200 for codeword 3225. Polynomial 3240 is provided for the corresponding M-bit non-organizational encoder 3230. Input bit 3220 is provided to the XOR gate 3275. The RSC_ENABLE signal is provided to the AND gate 3280, and the output of this AND gate 3280 becomes the second input of the XOR gate 3275. The AND gate 3280 also receives the output of the encoder 3230 as an input. The XOR gate 3275 provides an output to the M-bit shift register 3210 and its respective encoder 3230. The M-bit shift register 3210 also receives the clock signal 3285 and the reset signal 3290 and holds the state of the encoder 3200 at time T. This state value is used with each particular polynomial 3240 (specified by a particular sign) to generate the non-structural sign bit. The output 3250 of register 3210 is broadcast to the respective encoder 3230. The outputs 3225_0 to 3225_R of the encoder 3230 are combined to form the codeword (CODE_WORD) 3225.

【0158】

By enabling RSC_ENABLE3215, the encoder 3200 becomes a recursive systematic (RS) encoder. In the recursive tissue code, the input bit 3220 forms the tissue bit of the codeword 3225. The bits generated by each M-bit encoder 3230 form the rest of the RS codeword 3225.

【0159】

For non-organizational encoders, CODE_WORD3225 will contain R bits (where R = sign rate). When RSC_ENABLE3215 is active, CODE_WORD3225 is usually 1 bit wide. The output CODE_WORD3225 (now 1 bit wide) and the input bit (INPUT_BIT) 3220 form the RS codeword.

【0160】

[Effect of the invention]

As is clear from the above description, the embodiments of the present invention are applicable to decoding multiple transmission standards using an integrated scalable architecture.

【0161】

The above description is only for examples of the present invention. Various modifications and modifications are possible without departing from the technical scope and idea of the present invention. Examples are exemplary and are not limiting.

【0162】

The number in parentheses after the requirements of the invention in the claims indicates the correspondence of one embodiment of the present invention and should not be construed as limiting the scope of the invention. ..

[Simple explanation of drawings]

[Figure 1]

It is a schematic block diagram of a communication network using a plurality of protocols.

[Figure 2]

It is a schematic block diagram of the communication system using coding.

[Fig. 3]

It is a schematic block diagram of a general Viterbi decoder in a communication system using coding.

[Fig. 4]

It is a schematic block diagram of a general turbo decoder in a communication system using coding.

[Fig. 5]

It is a schematic block diagram of an integrated decoder.

[Fig. 6]

It is a schematic block diagram of the architecture of the integrated decoder.

[Fig. 7]

It is a schematic block diagram of the butterfly processor of FIG.

[Fig. 8]

FIG. 6 is a schematic block diagram of an Add-Compare-Select (ACS) unit in FIG.

[Fig. 9]

It is a figure which shows 32 state trellis and its corresponding butterfly processor and path metric.

[Fig. 10]

It is a figure which shows the path metric position of the result.

[Fig. 11]

A to E are diagrams showing in-place path metric addressing at time t = 1 to t = 5, respectively.

[Fig. 12]

It is a figure which shows the addressing of a path metric column.

[Fig. 13]

It is a figure which shows the in-place path metric addressing of the reverse trellis configuration.

[Fig. 14]

It is a figure which shows the in-place path metric addressing of the reverse trellis configuration.

[Fig. 15]

It is a schematic block diagram of the intermediate decoding memory processor of FIG.

[Fig. 16]

FIG. 15 is an exploded schematic block diagram of FIG. 15 showing a window memory subsystem, a traceback controller, and an interleaver controller.

[Fig. 17]

It is a schematic block diagram of the traceback controller of FIG.

[Fig. 18]

It is a schematic block diagram of the interleaver of FIG.

[Fig. 19]

It is an exploded view of the interleaver address controller of FIG.

[Fig. 20]

It is a schematic block diagram of the window memory subsystem of FIG.

[Fig. 21]

It is a schematic block diagram of the log-likelihood processor of FIG. 6 for a 1-row decoder.

[Fig. 22]

It is a schematic block diagram of the addition comparison selection node unit of FIG.

[Fig. 23]

8 is a schematic block diagram of the log-likelihood processor of FIG. 6 for a raw decoder.

[Fig. 24]

It is a schematic block diagram of the ACS unit of FIG.

[Fig. 25]

It is a schematic block diagram of the butterfly decoding processor bank of FIG.

[Fig. 26]

It is a schematic block diagram of the reverse address processor of FIG.

[Fig. 27]

It is a schematic block diagram of the normalization subtractor of FIG.

[Fig. 28]

It is a schematic block diagram of the comparator of FIG.

[Fig. 29]

It is a schematic block diagram of the path metric memory of FIG.

[Fig. 30]

It is a schematic block diagram of a forward address processor.

[Fig. 31]

It is a schematic block diagram of the comparator (ACS level) of FIG.

[Fig. 32]

It is a schematic block diagram of the input symbol history of FIG.

[Fig. 33]

It is a schematic block diagram of the log-likelihood ratio processor of FIG.

[Fig. 34]

It is a figure which shows the example which realizes one turbo decoder by using a plurality of decoders.

[Fig. 35]

It is a schematic block diagram of two interconnected decoders (16 state trellis per cycle) that collectively operate as a single decoder.

[Fig. 36]

It is a schematic block diagram of four interconnected decoders (32 state trellis per cycle) that collectively operate as a single decoder to further enhance decoding performance.

[Fig. 37]

It is a schematic block diagram of a non-structured encoder.

[Explanation of symbols]

100 wireless communication network 110 UMTS base station 112 transmitter / receiver 122 transmitter / receiver 130 remote CDMA base station 132 CDMA transmitter / receiver 140 remote base station 142 transmitter / receiver 144 transmitter / receiver 146 UMTS transmitter / receiver 150a ~ 150m Decoder module (decoder unit) 160 Exchange network 160a ~ 160f Mobile handset 200 communication system 205 Source 210 transmitter 220 encoder 230 modulator 240 communication channels 250 demodulator 260 Decoder 261 First input 262 2nd input 263 Demultiplexer 264 Demultiplexer 263 first output 265 Demultiplexer 263 second output 266 1st decoder 267 Output of 1st Decoder 266 268 Interleaver 269 Output of interleaver 268 270 receiver 271 Second Decoder 272 First output of second decoder 271 273 Second output of second decoder 271 274 1st Deinterriver 275 Received information signal 276 2nd Deintariva 277 Recursive input 278 Slicer 280 noise source 289 Branch Metric Calculator (BMC) Unit 290 state controller 291 Additive Compare Selection (ACS) Unit 292 Pathmetric memory 293 Traceback memory controller 294 Borrow output 320 Additive Comparison Selection Unit (ACS) 330 Intermediate Branch Metric Calculator (BMC) Borrow of 361'total subtractor 414' 402,402 Branch metric 1 406,406'branch metric 0 408,409 Multiplexer Output of 408'multiplexer 416' 410,410 adder 411 Output of adder 410 412,412 adder 413 Output of adder 412 414,414 Total subtractor 415 Second output of full subtractor 414 416', 417' Multiplexer Output of 418'multiplexer 417' 420 1st 2 to 1 multiplexer 420'multiplexer 421 Output of 1st multiplexer 420 440,440'logarithmic sum correction table 441 Output of logarithmic sum correction table 440 450 Second 2 to 1 multiplexer 460,460'adder 461 Results from adder 460 470,470'cumulative register Output to 472 multiplexer 480 475'multiplexer 480 multiplexer 480a ~ 480h Second output of ACS unit 1412a ~ 1412h 900 integrated decoder structure 901 Multi-bit input symbol 910 Intermediate decoding result memory 920 Butterfly Decryption Processor Bank 940 1st Store Bank 950 2nd store bank 960 control unit 961,963,965,967 2nd output 962,964,966,968 1st output 990 bus 999 Decryption output 1000 32 state raw trellis diagram 1002 time S_tState in 1003 time S_tState 0 1004 time S_{t + 1}State in 1006 branch metric 1007 time S_{t + 1}State in 16 1008 branch metric 1009 time S_{t + 1}State 0 1010 butterfly connection 1102 Memory corresponding to upper memory block B0 1104 Memory corresponding to lower memory block B1 1112 New path metric 1114 Hold register 1122,1134 New path metric 1150 Pathmetric column addressing order 1200 integrated decoder 1201 rate 1202 Restraint length 1203 Folding / Turbo Selector 1203₀ Log likelihood 0 enabled 1203₁ Log likelihood 1 enabled 1204 polynomial 1205 trellis direction 1206 Number of iterations 1207 block length 1208 clock 1209 reset 1210 Control unit 1211 Input symbol history bank select 1212 Intermediate decryption mode 1213 Hard / soft output select 1214 Log Likelihood Enable 1214a, 1214b Log-likelihood mode 1215 Butterfly reset 1216 Butterfly rate 1217 Butterfly clock 1218 Butterfly polynomial 1219 Input symbol history address 1220 Butterfly restraint 1221 butterfly mode 1222,1222a,1222b Reverse trellis select 1223 Input symbol history clock 1224,1224a, 1224b Reverse trellis hold 1225 Input symbol history reset 1226,1226a, 1226b Reverse trellis transparent bit 1228a Addressing information ADDR0 1228b Addressing information ADDR1 1230 Pathmetric reset 1231 Pathmetric read / write clock 1232 forward trellis select 1234 forward trellis hold 1235 Beta Phase Enabled 1236 forward trellis transparent bit 1237 Intermediate decoding direction 1238 Pathmetric Input Multiplexer Select 1240 Intermediate Decryption Memory Processor 1242 External information 1243 Diffuse input 1245a First output of log-likelihood processor 1250a 1245b Log Likelihood Processor 1250b Output 1246 Normalized output 1247,1247'Comparator 1248a, 1248b Log Likelihood Rate 1249a, 1249b Log-likelihood constraint 1250a, 1250a , 1250b Log Likelihood Processor 1250c multiplexer bank 1251a, 1251b Log Likelihood Clock 1252a, 1252b Log-likelihood reset 1253a, 1253b Log-likelihood polynomial 1254 clocking signal 1255 Judgment bit 1255a ACS0 (320) 1st output (all subtractor 414 borrow output) 1256 Interleaver external information 1257 Read / write clock 1258,1258a, 1258b Select signal 1259 reset signal 1260 Butterfly Decoding Processor 1265 Reverse trellis path metric 1265a Input path metric 0 1265b Input path metric 1 1266 Lower new path metric bus 1267 Upper new path metric bus 2nd output of 1267a ACS0 (320) 1270,1270b reverse address processor 1275,1275a ~ 1275h Normalized path metric 1276 Memory path metric 1277 Output to normalization subtractor 1278 1278 Normalization subtractor 1278a Multiplexer bank 1278b Control signal 1280 Pathmetric Store 1285 forward trellis path metric 1286 scrambled address data 1290 forward address processor 1291a First output of input symbol history 1298 1291b Input symbol history 1298 second output 1293 Log Likelihood Ratio Output from Processor 1297 1294 Decryption output 1295 Lower path metric bus 1295a ~ 1295d Path metric 1296 Upper pathmetric bus 1296a ~ 1296d Pathmetric 1297 Log Likelihood Ratio Processor 1297b Read / write signal 1298 Input symbol history 1299 input symbol 1410 Butterfly Unit Bank 1412a ~ 1412h ACS unit 1413a ~ 1413h First output of ACS unit 1412a ~ 1412h 1414a ~ 1414d BMC unit 1415a ~ 1415h Reverse trellis path metric 1416a ~ 1416h 2nd bank multiplexer 1417a ~ 1417h Multiplexer in bank 1 1420a ~ 1420d, 1430a, 1430b, 1440a ACS node unit 1420a'~ 1420d', 1430a', 1430b', 1440' ACS node unit 1420a ~ 1420d , 1430a , 1430b , 1440 ACS node unit 1450 subtractor 1460 register 1470a ~ 1470h Normalization subtractor 1474 Comparator 1476 Multiplexer 1478 Logarithmic sum correction table 1480 adder 1490 multiplexer 1510 Traceback Address Controller (Traceback Processor) 1515 Combined read / write signal 1520 interleaver controller 1525 address bus 1526 Bidirectional data bus 1530 window memory subsystem 1530a window address decoder 1530b ~ 1530d Window memory 1535 Second address bus 1536 Second data bus 1550 1st multiplexer 1555 Judgment register 1558 Bit Select 1560 Address translation unit 1562 status register 1564 Previous state unit 1566 2nd multiplexer 1567 Traceback processor output 1568 1st AND Gate 1569 2nd AND Gate 1570 NOT gate 1580 AND gate 1582 Tri-state buffer 1583 2nd tristate buffer 1584 1st logical block 1586 2nd logical block 1590 Window count 1591 bit count 1592 1st adder 1593 2nd adder 1594 3rd adder 1596 multiplexer 1597 scramble 1599 constant 1610a ~ 1610h subtractor 1710a ~ 1710h Maximum value comparator 1715 maximum path metric 1720 register 1730 subtractor 1735 load signal 1810a ~ 1810h Memory unit 1910a1 ~ 1910h1 Multiplexer of 3rd bank 1910a2 ~ 1910d2 latch 1910a3 ~ 1910d3 First bank multiplexer 1915a ~ 1915d 2nd bank multiplexer 1920a ~ 1920d XOR gate of bank 1 2010a ~ 2010d multiplexer 2015a ~ 2015d Hold register 2020 multiplexer bank 2030 2nd Multiplexer Bank 2100, 2110 multiplexer 2210 Window decoder 2212 counter 2214 Demultiplexer 2216 Double buffer memory bank 0 2218 Double buffer memory bank 1 2220 1st multiplexer 2222 Second multiplexer 2226 Input data 2240 1 to n demultiplexer 2242 First m-to-1 multiplexer 2244 Second m-to-1 multiplexer 2310 subtractor 2320 Second subtractor 2330 1st multiplexer 2340 2nd multiplexer 3010 Hold register 3200 encoder 3210 Mbit shift register 3215 RSC_ENABLE 3220 Input bits 3225 codeword 3230 M-bit non-structural encoder 3240 polynomial 3250 state bits 3260 AND gate 3270,3275 XOR gate 3280 Transition input 3285 clock signal 3290 reset signal