VLSI Architectures for Forward Error-Control Decoders:Viterbi Decoder Architectures

By -
Viterbi Decoder Architectures

Convolutional codes find use in a wide range of applications such as magnetic disk-drive channels, satellite, and in wireless communications. These codes are typically low-rate codes, i.e., R = 1/2 or R = 1/3 for most commonly employed codes. The Viterbi algorithm [34] is an efficient algorithm for decoding convolutional codes. The complexity of a Viterbi decoder is inversely proportional to the code rate unless the code rate is increased via puncturing.

Convolutional codes can be viewed as linear block codes with memory, i.e., the output of the linear encoder depends not only on the present information symbols but also on previous information symbols. Thus, a convolutional encoder is a finite-state machine (FSM) and the Viterbi algorithm is a particularly efficient method of estimating the state sequence of an FSM from a sequence of noisy observations of its output.

Convolutional Encoder

Consider an (no , ko , K) convolutional code where the encoder is an FSM with K - 1 memory elements that encodes a ko-bit data symbol into an no-bit code symbol as shown in Figure 82.7(a). The parameter K is called the constraint length of the code. At time index k, the N = 2K-1 possible encoder states are denoted as si(k) where i = 0, … , N - 1 and the branch connecting states si (k) with sj (k + 1) is denoted as bi , j (k). Note that si (k) and bi,j (k) are labels and not variables.

Given the current state si (k) and an input symbol u(k), the encoder transitions to a unique next state sj(k + 1) and generates a unique output symbol c(k). Hence, for an input sequence of L data symbols

VLSI Architectures for Forward Error-Control Decoders-0108

0 s0(k + 1)while generating L, no-bit code symbols c �- (c(0), c(1), ¼, c(L - 1)). An efficient method of describing all possible state transitions in an encoder is by using a trellis diagram. A section of the trellis of the encoder of Figure 82.7(a) is depicted in Figure 82.7(b), where the solid edges correspond to u(k) = 1 and dashed edges correspond to u(k) = 0. Note that the number of branches emerging from or ending in any state is 2ko .

The received sequence y = (y(0), y(1), ¼, y(L - 1)) at the receiver is simply a noisy version of the transmitted code sequence c. Thus, the convolutional decoding problem can be defined as estimating the input sequence u given the noisy sequence y. Two major approaches for estimating the transmitted bits u(k) from y are: (1) maximum likelihood (ML) decoding, and (2) maximum a posteriori probability (MAP) decoding. MAP is known to be much more complex than ML decoding. Furthermore, the results of MAP and ML decoding are identical when the probability distribution of the input u(k) is uniform. In 1966, Andrew Viterbi [34] proposed a computationally efficient procedure to implement ML decoding of convolutional codes. As a result, the Viterbi algorithm is almost universally applied whenever there is a convolutional code in a communication link. Hence, we will focus on the Viterbi algorithm and the ML decoding approach in this section.

Next, we provide a brief description of the ML decoding principle and then describe the Viterbi algorithm.

Comments

Post a Comment

Popular posts from this blog

SRAM:Decoder and Word-Line Decoding Circuit [10–13].

By -
Image
Decoder and Word-Line Decoding Circuit [10–13] Two kinds of decoders are used in SRAM: the row decoder and the column decoder. Row decoders are needed to select one row of word-lines out of a set of rows in the array. A fast decoder can be implemented by using AND/NAND and OR/NOR gates. Figure 52.7 shows the schematic diagrams of static and dynamic AND gate decoders. The static NAND-type structure is chosen due to its low power consumption, that is, only the decoded row transitions. The dynamic structure is chosen due to its speed and power improvement over conventional static NAND gates. From a low-voltage operation standpoint, a dynamic NOR-base decoding would provide lower delay times through the decoder due to the limited amount of stacking of devices. Figure 52.8 shows circuit diagrams of dynamic NOR gates. The dynamic CMOS gate as shown in Figure 52.8(a) consists of input- NMOSs whose drain nodes are precharged to a high level by a PMOS when a clock signal Φ is at a low lev...
Read more

ASIC and Custom IC Cell Information Representation:GDS2

By -
Image
GDS2 The Graphical Design System (GDS) format is a binary format developed by Calma Company in 1971 to convey IC layout information between IC designers and fabricators. Calma presented GDS2 format, the improved version of GDS, in 1978. Finally in 1991, when Cadence acquired Calma, GDS2 rights were transferred to it. In the design process, after the completion of routing and placement, design rule check (DRC) and layout versus schematic (LVS) are performed to verify the final layout. Then the verified layout, dumped in a GDS2 file, is transferred to IC foundries for fabrication. GDS2 File Format GDS2 is a standard mask layout intermediate format containing a single cell or a library of cells each of which includes a number of geometrical objects such as boundaries, paths, boxes, etc. These objects correspond to different layers of a cell where each layer is specified by a layer number and data type [3]. The file format of GDS2 is in binary. A GDS2 file contains a number of variable...
Read more

Timing Description Languages:SDF

By -
Image
SDF Standard Delay Format (SDF) is an ASCII format used to convey timing information between EDA tools. SDF was first developed by Cadence in 1990. Open Verilog International (OVI) approved SDF version 2 in 1993 and SDF version 2.1 and 3 in the following years. Improving SDF version 3 features, resulted in IEEE Standard 1497 [1]. Role of SDF in Design Process SDF can be used in different levels of a design process to annotate timing specifications, including timing data and constraints. Timing constraints are used during the forward-annotation process while timing data are applied during the back-annotation process. Forward-annotation process deals with porting timing constraints to synthesis, floorplanner, layout, and routing tools to meet the required constraints. During the design process, timing data can be back-annotated to analysis tools (including simulators, static timing analysis tools, etc.) to provide more accurate timing representations. SDF Structure An SDF f...
Read more