The device calculate the metrics of the paths of the viterbi decoder


H03M13/12 -

 

(57) Abstract:

The invention relates to telecommunications and is intended for use in digital transmission systems convolutional code. The purpose of the invention is the simplification of the device. The proposed device allows to solve the task of implementing a decoder with sufficient practice for noise immunity on a single chip ultra integrated circuit. The device contains a memory metrics on non-binary shift registers with the minimum number of interconnects and the minimum memory capacity for the sequential procedure of the addition - comparison - selection. This allows you to perform a Viterbi decoder for code with code constraint on domestic basic matrix crystal. 13 Il.

The invention relates to telecommunication and can be used in digital transmission systems convolutional code for decoding by the Viterbi algorithm when implementing technology base matrix crystals (BMC).

Known convolutional code decoder for decoding by the Viterbi algorithm [1] that contains the device calculate the metrics of the paths based on the signal properties of the metrics of the branches, which reduces the delay is enabled in the device calculate metrics ways performs parallel processing of the received code sequence and contains the 2channel processing, which cannot be implemented on a promising technology for BMC = 4 and more. Exponential (on ) the increasing complexity of devices severely limits the realisable value and thereby reduces the robustness of the decoder.

Closest to the proposed is a device for computing metrics of paths [2] , containing two channels of processing, each of which consists of two adders, the outputs of which are connected through the block comparison and switch metrics to the transmitter, the second input is connected with the output unit of the normalized threshold, the input of which is connected to the input of the memory block metrics that are connected to the circuit output OR inputs which are connected to the outputs of the calculators both channels of processing, and outputs of the memory block metrics connected to the outputs of the respective adders. Two channel processing instead of the 2channels provide sequential processing metrics.

The disadvantage of the prototype is that it is focused on software implementation with address memory organization metrics, performed the BMC, actually the memory and control circuit it takes an unacceptably large portion of the crystal, and for the remaining blocks of the decoder of space left. In the prototype it is also proposed to perform memory metrics on parallel registers, however, 3 the problem arises exponential increase in the number of interconnects on a chip BMC. It also makes impossible the task of placing the electric circuit of the Viterbi decoder with high immunity on a single chip.

The purpose of the invention is the simplification of the device for the hard of hardware implementation on BMC and, as a consequence, the increased robustness of the decoder.

The goal is achieved that the device calculate the metrics of the Viterbi decoder, the containing element OR the output of which is connected to the input unit of the normalized threshold, and two channels of processing, each of which contains a block of comparison, the output of which is connected to the first input of the switch metrics, and first and second adders, the output of the first adder connected to the first input of the block compare your channel processing, introduced the first five non-binary shift registers and the first through third switches, when this output block of the normalized threshold is connected to the inputs of the senior resolution is to each processing channel connected to the second inputs of the block comparison and switch metrics another channel processing, the outputs of blocks compare all the channels of the processing are output devices, the third inputs of the switches of the metrics of each processing channel connected to the output of the first adder of the same channel processing, the output switch metrics of the first processing channel connected to the first inputs of the first switch element OR the input of the second non-binary shift register, whose input is connected to the second input of the first switch, the output of which is connected to the control inputs of the adders of the first channel processing, the output switch of the metrics of the second processing channel connected to the second input element OR to the first inputs of the second and third switches and the fourth input non-binary shift register, the output of which through fifth non-binary shift register is connected to the second input of the third switch, the output of which is connected to the input of the third non-binary shift register, the output of which is connected to the control inputs of the adders of the second channel processing.

The essence of the invention and the significance of the differences is as follows. Thanks to the introduction of new nodes and links changed memory organization metrics in the metrics are calculated, which allows to localize blocky nodes adding - compare - select (CERs).

Traditional principles of memory organization metrics based on the use of either multi-bit RAM, or a multi-bit parallel registers. In the first case, the exponential growth in the complexity of RAM and the corresponding control circuit, and the second case, the exponential increase in the number of interconnections is not possible to implement in BMC decoder Viterbi, complex enough to provide the required noise immunity.

Comparative analysis with the prototype shows that the device is characterized by the presence of non-binary shift registers, allowing to minimize hardware memory organization metrics and their relationship to processing node CERs, which provide the minimum number of word-level interconnects. Therefore, the claimed device meets the criterion of "Novelty."

A comparison of the proposed facility with other technical solutions shows that the use of non-binary shift registers for memory organization metrics in the Viterbi decoder is not known, together with links gives a summary of new features in the device calculate metrics and gives him the above new features. Therefore, Salama proposed device, where 1-1 and 1-2, the first and second arithmetic adders, 2 blocks comparison, 3 - switches metrics, 4 - scheme OR 5 - unit normalized threshold 6 - the first non-binary shift register, 7 - second non-binary shift register, 8 - first switch, 9 - third non-binary shift register, 10 - fourth non-binary shift register, 11 - second switch, 12 - fifth non-binary shift register, 13 the third switch; Fig. 2 shows a convolutional encoder in the form of a Moore machine; Fig. 3 is a trellis diagram (States) of the encoder of Fig. 4 shows the correspondence between the "butterfly" (a) trellis diagram of the encoder and processing site (b) CER; Fig. 5-12 shows the processes in the device at full cycle of decoding one code branch; Fig. 13 is a timing diagram of signals that control the decoding process is shown in Fig. 5-12, where a is a clock signal whose period is equal to a full cycle of decoding one bit, b - clock signal of the first and third non-binary shift registers; a control signal to the first switch, the clock signal of the second non-binary shift register, d - control signal to the second switch, the e - clock signal of the fourth nonbinary sdvigovoi is egistra.

The device calculate the metrics of the Viterbi decoder (Fig. 1) contains two channels of processing, each of which is composed of the first 1-1 and 1-2 second adders, low-order bits are connected to the corresponding outputs of the unit for computing the metrics of the branches and are the inputs of the device, unit 2 compare and switch 3 metrics. The outputs of the switches 3 through the scheme, OR 4 and block 5 normalized threshold associated with the older bits of all adders 1. The outputs of the first adder 1-1 each processing channel connected to the first input unit 2 compare and to a third input of the switch 3 metrics of the same processing channel, and the outputs of the second adder 1-2 each processing channel connected to the second inputs of unit 2 compare and switch 3 metrics another channel processing. The first inputs of the switches 3 are connected to the inputs of blocks 2 comparison of the corresponding channel processing and simultaneously to the output devices, which are connected to the inputs of the memory block paths decoders. The control inputs of adders 1-1 and 1-2 of the first channel processing combined and connected to the output of the first non-binary shift register 6, the inlet of which is connected to the output of the first switch 8, the first input of which is directly and through the second second the water adders 1-1 and 1-2 of the second channel processing combined and connected to the output of the third non-binary shift register 9, the inlet of which is connected to the output of the third switch 13. The first input of the latter is connected with the output of the fifth non-binary shift register 12, the inlet of which is connected to the output of the second switch 11. The first input of the switch 11 is connected to the output of the fourth register 10, the inlet of which is connected to the output of the switch 3 metrics of the second processing channel and to the second inputs of the second 11 and third 13 switches.

To describe the operation of the device in the structure of the Viterbi decoder will first consider the process of encoding the convolutional code. The convolutional encoder shown in Fig. 4, and in the form of a four-digit (K = 4) shift register (Moore machine, i.e., final digital machine whose outputs are a function of its state). State of the encoder is called content = K-1 bits of his shift register, in this case three information bits

it, it-1, it-2stored in the bits of the encoder at time t. By definition, the code constraint convolutional code called number = K - 1. In our example, = 3. The rate of the code R = ko/nobecause when you enter ko= 1 one information bit itthe encoder generates no= 2 code symbol: Y1t,Y2t. / Min net the sequence. Code symbols appear at the outputs of adders modulo two, the inputs of which are connected to predetermined bits of the shift register. The configuration of these compounds is described by ( + 1)-bit binary sequences: G1= 1111, G2= 1011, which are called subgeneration. Units in the positions of subgeneration correspond to the number of digits, the output of which is connected to the modulo two, with the first unit in subminiature means that one of the inputs of the modulo two is connected to the input of the register. The code symbols are generated according to the rule

y1t= it+ it-1+ it-2+ it-3(mod 2);

y2t= it+ it-2+ it-3(mod 2), where addition is performed modulo two. The encoding process described by a trellis diagram shown in Fig. 3, which illustrates the transition of the encoder from one state to another upon receipt of the next information bit at the input of the encoder. Since the number of bits the encoder is in our example K = 4, the number of States that can be received by the encoder in a given time, as well

2= 2K-1= 8.

Since the information bit can take one of two values of the ionic bit is equal to two: go through the upper branches, outgoing from each state of the graph corresponds to the entry "0", and the transition to the lower branch corresponds to the receipt of "1". Each transition (line graph) corresponds to a pair of symbols: y1t, y2twhich is also called a code branch.

When considering Fig. 3 you can see that the lattice chart breaks down into four independent bipartite graph (Fig. 4A), which is called "butterflies" in the literature on computational aspects of algorithms (see,for example, in the book. D. Ullman. Computational aspects. VLSI. M, MS, 1990, S. 215). Therefore, decoding of one-bits in the Viterbi decoder is reduced to 2-fold repetition of the computational procedures of CERs, which describes "the butterfly". In Fig. 4B shows a block diagram of the processing node performing the operation of CERs. Node CER contains two channels of processing their inputs Metric status" in Fig. 4B acoustilay left vertices of the bipartite graph "butterflies". In Fig. 4 inputs "branch Metric" if necessary acoustilay with the relevant branches of the "butterfly", and outputs block CER Metric status" in Fig. 4B - right vertices of the bipartite graph "butterflies".

Each processing channel includes two adder, atora metrics of the same processing channel, and the output of the second adder is connected with the joint second inputs of the block comparison and switch metrics another channel processing. The output of the Comparer connected to the first input of the switch whose output is the output channel processing. Site CERs works as follows. Metrics branches arrive at the low-order bits of the adders, the control inputs of which receive the metrics of the States (or metric paths, or simply the metric). The results of the summation arrive at the inputs of the block comparison, the output of which appears a logical "0" provided that the number on its upper input is greater than the number on the bottom of the entrance, if this condition is not met, then the output of the Comparer appears logical "1". The output signal of the block comparison so affects the switch on its output appears smaller of the two numbers, arriving at its inputs. After you perform this procedure (called procedure CERs) over the metrics of the branches and metrics of States at the outputs of the channels of the processing unit CERs new metric States. Similarly performed CERs and for the other three "butterflies".

Device metrics are calculated as follows:

On the interval T decety transmission information sequence, the device sequentially performs four times the procedure CER (Fig. 5-12) for each of the four "butterflies", is shown in Fig. 4A. For this purpose, the interval T is divided into four equal putinterval

Tp= (1/4)T by the number of "butterflies" in one step trellis diagram. Consider the state of the device on the ground pointervalue, i.e. at the beginning of the decoding of the information bits (see Fig. 5 and 6). In this state, the output of the first non-binary shift register 6 at the joint control inputs of the adders 1 of the first processing channel receives a metric of "1" (Fig. 5 and 6 is marked with number 1 in the output discharge of the first binary shift register), the joint control inputs of the adders 1 second channel processing from the output of the third non-binary shift register 9 is supplied metric state "0" (Fig. 13 is marked with the number 0 in the output category of the third non-binary shift register). On the low-order bits of the respective first inputs of adders both channels of the processing serves the metrics of the branches of 00 and 11. The sum of the metric of "1" and metric branch 00 routed to the first input unit 2 a comparison of the first channel processing, and on its second input signal the sum of the metrics of the States "0" and the metrics of the branches 11. And the La treatment, and at its first input receives the sum of the metrics of the States "0" and metric branch 00. If the sum of the metrics on the first input unit 2 a comparison of the amount of the metrics on the second of its input, the signal at its output assumes a logic level "1", otherwise a logic level "0". The feedback of this signal at the first input of the switch 3 metrics at its output appears smaller of these two amounts: at the output of the switch 3 metrics of the first channel processing is the new metric status "4", and the output of the switch 3 metrics of the second channel processing is the new metric state "0". The control signal (Fig. 13B) of the first switch 8 assumes the logic level "1", resulting in its output pin connected to the output of the second non-binary shift register 7. The control signals of the second 11 and third 13 switches also accept a logic level "1" (Fig. D and W, respectively), resulting in the entrance of the third non-binary shift register 9 is connected to the output of the fifth register 12, the entrance of which, in turn, is connected to the output of the fourth register 10. As shown in Fig. 13B,g,W, h, at the end of this putinterval after you finish all transients in Ih registers. This transition is the shift by one digit to the left of the contents of all non-binary shift registers 6, 7, 9, 10, 12. The resulting state diagram is shown in Fig. 7 - the device is prepared for operation CERs, which corresponds to "butterfly", is shown in Fig. 8. For the next seven putinterval device works similarly. Non-binary shift register operates in the storage mode, i.e., its content does not move in the case, if this pointervalue for the corresponding register is missing clock pulse. As shown in Fig. 13, this condition is satisfied for the second case in Fig. 7-12, for the fourth case in Fig. 9-12 and for the fifth register in Fig. 11 and 12.

Since the device is only one arithmetic operation - addition, the metric is cumulative in nature: its value monotonically increases in time. Therefore, if you do not take special measures, there is a memory overflow and, as a result, the malfunction of the device. In order to avoid memory overflow as necessary to carry out the so-called "normalization" of the metric. It boils down to the subtraction of all metrics of some constant number, or, equivalently, to the module, the value of which depends on the bitness of the metric. Normalization metrics perform with the help of block 5 of the normalized threshold. May signal the risk of memory overflow is the appearance of a logical "1" in the highest bit metrics at the output of the switch 3 both channels processing on all four clock putinterval. This causes a logical "1" at the output of the circuit OR 4, is connected to the input unit 5 of the normalized threshold. The danger signal overflow is stored in the unit 5 to the end of interval I. Then on the interval decoding of the next bit level logical "1" occurs at the output of block 5, therefore, to the higher digits of the first inputs of adders 1-1 and 1-2 in this interval connected logical "1". With appropriate selection of the high-order bits (the same for all adders) the value of each metric after the operation of addition is reduced by a constant amount. After normalization for the next interval T at the output of block 5 again level is set to a logical "0".

The DEVICE calculate the METRICS of the PATHS of the Viterbi DECODER, the containing element OR the output of which is connected to the input unit of the normalized threshold, and two channels of processing, each of which contains Blo is, I can pay tithing adder connected to the first input of the block compare your channel processing, characterized in that, to simplify the device, it introduced the first five non-binary shift registers and the first through third switches, the output block of the normalized threshold is connected to the inputs of the senior ranks of all the adders, the inputs of the least significant bits which are input devices, the output of the second adder of each processing channel connected to the second inputs of the block comparison and switch metrics another channel processing, the outputs of blocks compare all the channels of the processing are output devices, the third inputs of the switches of the metrics of each processing channel connected to the output of the first adder of the same processing channel, the output switch metrics of the first processing channel connected to the first input of the first switch element OR the input of the second non-binary shift register, the output of which is connected to the second input of the first switch, the output of which is connected to the input of the first non-binary shift register, the output of which is connected to the control inputs of the adders of the first channel processing, the output switch of the metrics of the second processing channel connected to the second input element OR to the first inputs of the second and third switches and the fourth input nonbinary DM is the first non-binary shift register is connected to the second input of the third switch, the output of which is connected to the input of the third non-binary shift register, the output of which is connected to the control inputs of the adders of the second channel processing.

 

Same patents:

The invention relates to systems for the transmission of information via communication channels and can be used in devices for decoding by the Viterbi algorithm
Up!