HIGH SPEED ADD-COMPARE-SELECT CIRCUIT

In described embodiments, a trellis decoder includes a memory including a set of registers; and an add-compare-select (ACS) module including at least two ACS layer modules coupled in series and configured to form a feedback loop with carry components in a single clock cycle, wherein the ACS layer module includes at least two branch metrics represented by a plurality of bits and adders configured to generate a plurality of state metrics using carry-save arithmetic, and a plurality of multiplexers configured to perform a selection of a maximum state metric in carry-save arithmetic stored in memory as the carry components. A method of performing high speed ACS operation is disclosed.

DETAILED DESCRIPTION

Described embodiments of the present invention relate to a high speed ACS circuit useful in Viterbi and log-MAP decoders for decoding turbo and LDPC-codes. A set of schemes for high speed computation of ACS operation in accordance with exemplary embodiments of the present invention are developed for 2 and more trellis layers on a clock cycle. The described embodiments below are examples for 2 trellis layers. These examples, however, might be easily adapted for 3 trellis layers and more. The developed schemes might use carry-save arithmetic computations which might provide a specific structure of the ACS circuit. This feature might make it possible to recognize an inprintment of designs of the ACS circuit. In addition, the developed schemes might contain two or more identical combinatorial ACS layer submodules which might help to recognize the inprintment of these designs and further increase the calculation speed.

Note that herein, the terms “ACS design”, “ACS scheme”, “ACS circuit”, “ACS module”, “ACS layer”, “ACS technique” and “ACS operation” might be used interchangeably. It is understood that an ACS design might correspond to, or contain an ACS scheme of and ACS module, an ACS circuit and an ACS operation, and that the ACS scheme, the ACS module, the ACS layer, the ACS circuit, the ACS technique and the ACS operation might refer to the ACS design.

Referring toFIG. 2, a block diagram illustrating a single standard ACS module200with computation for an iteration. Standard ACS module200includes ACS layer202, which might comprise a set of combinatorial gates, and registers204coupled to forma loop for an iteration. ACS layer202has input vector x(t) and output vector y(t) of an ACS layer computation combinatorial part. Current and next states of standard ACS module200are denoted as q(t) and q(t+1). Registers204store the state q(t+1) computed from ACS layer202and feedback the computed state q(t+1) to ACS layer202as the next input state for the next iteration computation. ACS module200performs one calculation on single standard ACS layer202on a single clock cycle.

FIG. 3is a block diagram illustrating an exemplary embodiment of a double speed ACS module300that provides for a ACS speed-doubling technique in accordance with an exemplary embodiment of the present invention. The ACS speed-doubling technique herein might be a technique that clones twice or more substantially all combinatorial gates of an ACS module, whereas register requirements are maintained so as to stay unchanged. As shown inFIG. 3, double speed ACS module300includes first ACS layer302, second ACS layer304and registers306, which are coupled to form a loop for an iteration. First ACS layer302might receive the same input vector x(t) as ACS module200shown inFIG. 2, but the output y(t) of first ACS layer302might be applied to second ACS layer304, which also might receive the next input vector x(t+1). The computed state q(t+1) from first ACS layer302might be provided to second ACS layer304as an input state. Second ACS layer304might output the second output vector y(t+1) and save the computed state q(t+2) into registers306. Current and next states of the ACS algorithm might be denoted as q(t), q(t+1) and q(t+2). Registers306might store the computed state q(t+2) from second ACS layer304and provide the computed state q(t+2) to first ACS layer302as the input state q(t) for the next computation. Thus, double speed ACS module300might perform calculations on two ACS layers on a single clock cycle whereas standard ACS module200might perform calculations on two ACS layers for two clock cycles. Accordingly, the ACS speed double technique of the present invention might increase the speed of calculations through ACS layers.

Furthermore, in the described embodiments, carry-save arithmetic might be employed in the combinatorial part of ACS layers, which might enable a deep optimization of the ACS design with doubled combinatorial part in terms of maximal operating frequency. Thus, doubled ACS design might perform on frequencies higher than half of the working frequency of the standard ACS design. For example, a simulation of a standard ACS layer is successfully closed at 1000 MHz and a simulation of an ACS layer with double speed is closed at 650 MHz. First and second layers302,304of double speed ACS module300with carry-save arithmetic are described subsequently below in detail.

FIG. 4Ashows a block diagram illustrating a module for an ACS operation of two operands. As shown, module400includes adders402,404for branch metrics BM1and BM2and compare-select circuit406. Here, BM stands for branch metric and SM for state metric. Module400might compute each SM required for a next iteration according to the following relation (1):

where “max” denotes a maximum operation.

In some modifications of Viterbi or log-MAP algorithms, a minimum operation might be performed, for example, in relation (1) instead of a maximum operation. However, such modifications generally. do not change the design of an ACS significantly. Consequently, one skilled in the art might readily extend the teachings of embodiments of the present invention described herein to embodiments for the minimum operation case(s). The total depth of the scheme might be a depth of an adder (adder402or404) plus a depth of compare-select circuit406, which might be approximately the depth of the adder for a corresponding number of arguments. Thus, a total depth of a given ACS design might significantly depend on the number of its arguments. In general, the number of arguments of the ACS operation is typically equivalent to the number of states in the trellis layer of the ACS module. Generally, an ACS operation of four operands (ACS4), an ACS operation of eight operands (ACS8) and an ACS operation of sixteen operands (ACS16) are usually employed in modern trellis decoders. Accordingly, ACS operation of four operands (ACS4), ACS operation of eight operands (ACS8) and ACS operation of sixteen operands (ACS16) might be applied to the disclosed embodiments.

Since module400only includes adders402,404and compare-select circuit406, as shown inFIG. 4A, the ACS operation might be relatively simple. However, the simple ACS operation might be difficult to modify to make an ACS algorithm perform faster. However, register-transfer level (RTL) synthesis implements this efficiently, allowing for acceleration using a bit-level implementation.

FIG. 4Bis a block diagram for a standard implementation of an ACS module of two 4-bit operands. As shown, ACS module500includes first and second branch metrics514,516(represented as bit arrays), an array of multiplexers505,506,507,508, and an array of registers509,510,511,512for storing state metric bits. First branch metric514includes branch metric bit array515and an array of adders501,502,503,504. Bits and adders are shown for first branch metric514are shown in the figure, but bits and adders for second branch metric516are omitted inFIG. 4Bfor simplicity. The bits and adders for second branch metric516might be organized in the same structure as for first branch metric514. Multiplexers (labeled “M”)505,506,507,508, might select the largest sum computed using the above relation (1) (i.e., SM=max (BM1+SM1, BM2+SM2), and transfer the largest sum onto the respective ones of registers509,510,511,512.

As shown inFIG. 4B, a relatively critical path of computation for ACS module500, is depicted in thick lines. The critical path of ACS module500might include 4 single-bit adders501,502,503,504and 4 single-bit multiplexers505,506,507,508. Thus, a depth of ACS module500includes 4 adders and 4 multiplexers.

However, the ACS scheme of the described embodiment shown inFIG. 2might have a depth almost two times less than the depth of standard two 4-bit solution of ACS module500. These features might be achieved by using carry-save arithmetic combined with a technique of doubling of combinatorial logic of the ACS module. The carry-save arithmetic will be described below. For comparison, a ripple carry adder might be described first.

FIG. 5Ais a block diagram illustrating as 2-bit ripple carry adder. Ripple carry adder600includes a sequence of adders and two full adders602,604(also shown labeled as FAiand FAi+1) as shown inFIG. 5A. Ripple carry adder600might be a logic circuit using multiple full adders to add N-bit numbers. As shown, ai, biare bits of numbers A and B, where A=Σi=0n−1αi2i, B=Σi=0n−1bi2i. Each full adder, for example, first and second fuller602,604, might input a carry which is an carry output of the previous adder, and each carry bit “ripples” to the next full adder. More specifically, first and second full adders602,604might receive carry inputs ciand ci+1from the respective preceding full adder and input bits ai, biand ai+1, bi+1and provide two output bits and carry bits si, ci+1and si+1, ci+2. First full adder602might receive the carry input cifrom a preceding full adder. If no previous full adder exists, then the input carry cimight be zero. First full adder602might output the carry output ci+1to second full adder604. The carry output ci+1from first full adder602might be the carry input ci+1to second full adder604. Likewise, second full adder604might provide its second carry output ci+2as the carry input ci+2to the third full adder (not shown). It should be noted that the input cimight not be used to generate the ci+2output of the same fill adder. Thus, carry propagation occurs from one full adder to the next. The respective input, bits ai, bior ai+1, bi+1to each of full adders602,604might represent adjacent bits from four partial products. For example, first full adder602receives the nth bit of first, second, third and fourth partial products with second full adder604receiving the n+1 bits respectively of those same partial products.

First full adder602(FAi) might compute output bit siof the result of addition and carry bit ci+1. The carry bit ci+1output from first full adder602might be used by following second full adder604. Output bit siof the result of addition and carry bit ci+1bits might satisfy following relations si=ai⊕bi, c0=0, ci+1=a1v bi, i=0, . . . , n−1. Thus, the total depth of ripple carry adder600might equal number of bits n. As the number of bits increases, the depth of ripple carry adder600might increase, which might slow the speed of calculations.

For given implementations, the layout of ripple carry adder600might be relatively simple, which might allow for fast design time for the implementation; however, ripple carry adder600might be relatively slow, since each full adder, for example, first and second full adder602,604, waits for the carry bit to be calculated from the previous full adder. The gate delay might easily be calculated from observation of the full adder circuit. Each full adder, for example, first and second adder602,604, might require three levels of logic. A 32-bit ripple carry adder includes 32 full adders, so the critical path (worst ease) delay might be calculated as 3 delay-units of time (from input to carry in first adder)+31*2 (for carry propagation in later adders), yielding, the equivalent of 65 gate delays.

Carry-save addition techniques might be employed to reduce the depth of addition scheme shown inFIG. 5Ato 1 delay-unit of time.FIG. 5Bshows a block diagram illustrating a standard carry-save adder. Carry-save addition techniques might make an addition scheme perform at higher frequencies than a standard ripple carry adder. With carry-save techniques, carry bits no longer propagate through all full adders; carry bits become part of the result of the addition operation. One of the operands might be entered in carry inputs and carry outputs, instead of feeding the carry inputs of following full adders, forming a second output word which might then be added to an ordinary output in a two-operand adder to form a final sum. A carry-save adder computes the sum of three or more n-bit numbers in binary and outputs two numbers of the same dimensions as the inputs, one which is a sequence of partial sum bits and another which is a sequence of carry bits.

Carry-save adder700, as shown inFIG. 5B, allows for the rapid addition of three operands and includes a sequence of adders (only two adders702,704of the sequence are shown). As shown, an addition of numbers A and B might satisfy relation (2):

and, as such, the result of the carry-save addition of the numbers A and B might be an array of carry-save bus vi. Accordingly, a depth of the carry save adder might equal the depth of a single full adder, i.e., the depth might be equal to 1.

Since carry-save adders reduce the depth of the addition scheme to 1, the described embodiments applying carry-save arithmetic might increase the speed of the calculations. Referring toFIG. 6, a block diagram of a bit-level view of a carry-save ACS module of two 4-bit operands according to the present invention is illustrated first and second ACS layers302,304shown inFIG. 3might be formed as single ACS module800as shown inFIG. 6, ACS module800includes first and second branch metrics801,802represented as bit arrays, an array of adders803,804,805,806for first branch metrics801, an array of compare-select multiplexers (CSMs)807,808,809,810, and a plurality of registers811,812,813,814,815,816,817,818for storing data. Second branch metric802might contain a second branch bit array and also an array of full adders which might be an exact copy of adders803,804,805,806. Registers811,812,813,814,815,816,817,818might be standard registers, with respective width equal to the width of branch metrics, which might vary. For example, in some cases, 6 bits for representing a branch metric might be enough, but some decoder designs employ 8 bit representation. Bits and adders for first branch metric801are shown inFIG. 6, but bits and adders for second branch metric802are omitted inFIG. 6for simplicity. The bits and adders for second branch metric802might be organized in the same structure as for branch metric801.

CSMs807,808,809,810might select the largest sum computed using the relation SM=max (BM1+SM1, BM2+SM2), as described inFIG. 4B, and transfer the largest sum onto the respective registers811,812,813,814.

As shown inFIG. 6, a critical path, depicted in thick lines, of ACS module800might include 2 single-bit adders804,805and 2 single-bit CSMs807,808, where carry-save arithmetic might be applied. As described above, the depth of standard ACS module500includes 4 adders and 4 multiplexers, whereas, ACS module800might include 2 single-bit adders and 2 single-bit CSMs. Thus, the ACS scheme of ACS module800might have a depth almost two times less than the standard solution, thereby, the ACS schemes of the described embodiments might increase the speed of the calculations. These features might be achieved by applying the carry-save arithmetic and technique of doubling of combinatorial logic of the module.

Referring toFIG. 7A, a block diagram illustrates an embodiment of a double speed ACS decoder10employing the double speed ACS techniques described herein in accordance with exemplary embodiments of the present invention. The decoder might be a Viterbi decoder, a turbo decoder, or a log-MAP decoder. The decoder might typically be a functional processing block in a receiver portion of a transceiver configured for use in a communications system, such as a mobile digital cellular telephone. The decoder might perform error correction functions. As shown inFIG. 7A, decoder10includes processor12and associated memory14. It is to be understood that the functional elements of an ACS module of the described embodiments, as described above in detail, which make up a part of a decoder, might be implemented in accordance with the decoder embodiment shown inFIG. 7A.

Processor12and memory14might preferably be part of a digital signal processor (DSP) used to implement the double speed decoder. However, it is to be understood that the term “processor” as used herein might be generally intended to include one or more processing devices and for other processing circuitry (e.g., application-specific integrated circuits or ASICs, Gas, FPGAs, etc). The term “memory” as used herein might be generally intended to include memory associated with the one or more processing devices and/or circuitry, such as, for example, RAM, ROM, a fixed and removable memory devices, etc. Also, in an alternative embodiment, the ACS module might be implemented in accordance with a coprocessor associated with the DSP used to implement the overall turbo decoder. In such case, the coprocessor might share in use of the memory associated with the DSP.

Accordingly, software components including instructions or code for performing the Methodologies of the invention, as described herein, might be stored in the associated memory of the turbo decoder and, when ready to be utilized, loaded in part or in whole and executed by one or more of the processing devices and/or circuitry of the turbo decoder.

Referring toFIG. 7B, a block diagram illustrates an exemplary embodiment of a trellis-based embodiment for double speed decoder10applying ACS double-speed techniques in accordance with the present invention. As shown, decoder20includes branch metric computation module22, first and second ACS modules24,26, and registers28. Branch metric computation module22calculates the branch metrics. First and second ACS modules24,26might recursively accumulate the branch metrics as the path metrics using carry-save addition technique within iteration loop29. First and second ACS modules24,26might then compare the incoming path metrics, and make a decision to select the most likely state transitions for each state of the trellis and generate output state metrics that might contain the corresponding decision bits. Registers28might store the decision bits and help to generate decoded outputs. The primary arithmetic operation performed during state metrics calculation might be ACS double-speed operation on a clock cycle, which might increase the calculation speed at least two times comparing to the conventional ACS operation.

FIG. 8is a flow chart illustrating an exemplary method for module30with double speed ACS techniques as shown inFIG. 3andFIG. 6. As shown, at step31, two or more state metrics in carry-save arithmetic might be provided to first ACS layer module302that has first respective sum components. At step32, two or more computing state metrics in carry-save arithmetic in first ACS layer module302might be produced on a clock cycle in response to two or more respective branch metrics. At step33, the two or more computing state metrics might be fed to second ACS layer module304that has second respective sum and carry components. At step34, another two or more computing state metrics in carry-save arithmetic in second ACS layer module304might be produced in response to another two or more respective branch metrics and the two or more computing state metrics on the same clock cycle. At step35, the another two or more computing state metrics might be stored in carry components306of second ACS layer module304. At step36, the another two or more computing state metrics might be provided to first ACS layer module302for next iterative computation.

The present invention may be implemented as circuit-based processes, including possible implementation as a single integrated circuit (such as an ASIC or an FPGA), a multi-chip module, a single card, or a multi-card circuit pack. As would be apparent to one skilled in the art, various functions of circuit elements may also be implemented as processing blocks in a software program. Such software may be employed in, for example, a digital signal processor, micro-controller, or general-purpose computer.

No claim element herein is to be construed under the provisions of 35 U.S.C §112, sixth paragraph, unless the element is expressly recited using the phrase “means for” or “step for.”