# High-speed module for adding/comparing/selecting for use with witterby decoder

FIELD: Witterby algorithm applications.

SUBSTANCE: system has first memory element for storing metrics of basic states, multiplexer, capable of selection between first and second operating routes on basis of even and odd time step, adding/comparing/selecting mechanism, which calculates metrics of end states for each state metric. Second memory element, connected to adding/comparing/selecting mechanism and multiplexer is used for temporary storage of end states metrics. Multiplexer selects first operating route during even time steps and provides basic states metrics, extracted from first memory element, to said mechanism to form end state metrics. During odd cycles multiplexer picks second operating route for access to second memory element and use of previously calculated end state metrics as metrics of intermediate source states.

EFFECT: higher efficiency.

2 cl, 9 dwg

The present invention relates generally to the application of the Viterbi algorithm. In particular, the present invention relates to an improved system and method of performing high-speed operations of addition/comparison/selection (CERs) under the scheme “butterfly” in the implementation of the Viterbi algorithm.

The Viterbi algorithm was first introduced in 1967 as a way of decoding signals subjected to convolutional coding. After that, the algorithm is widespread in the field of data transmission, data recording and processing digital signals. The application of the algorithm contributed to the solution of various issues related to digital assessment, including reduction of write errors on the media, remove intersymbol interference and improve character recognition and text.

For this reason, the Viterbi algorithm has become the primary method of decoding with error correction data, subjected to convolutional coding. For such applications, the Viterbi algorithm determines, on the basis of the number of measurements, the path with the minimum metric errors crossing the lattice that represents all possible States of the encoder. This shortest path illustrates the most plausible sequence generated by the convolutional encoder.

On figa depicts a typical convolutional encoder. Convolutional encoder 100 of the content is it 8-bit partitioned shift register 110 and a pair of adders 120 type “exclusive OR”,
to convert a sequence of input data bits U(D) 105 in the sequence of output code symbols 125 C_{0}(D), C_{1}(D). In particular, figa shows an example of coding with rate 1/2, which generates two output code symbol 125 C_{0}(D), C_{1}(D) for each input information bit U(D) 105. Note that the specific code rate and the configuration of the convolutional encoder 100 shown only for illustrative purposes and in no way limiting the effect or scope of the various embodiments of the invention. Therefore, in relation to variants of the invention, it is possible to use different code rate, such as 1/3 or 3/4.

The encoder 100 generates each output code symbol 125 C_{0}(D), C_{1}(D)subjecting the input bit stream U(D) 105 operations shift and exclusive OR, according to the specific configuration of the shift register, the set of generating polynomials encoding G_{0}(D), G_{1}(D). In this case, figa shows the wiring diagram shift register, which provides a generating polynomial encoding speed. The coefficients of the polynomial G_{0}(D) is subjected to convolution with the input sequence U(D) 105 to generate an output symbol 125 convolutional code C_{0}(D). Anal is Gino,
on figa shows a generating polynomial encoding speedwhose coefficients are subjected to convolution with the input information sequence U(D) 105 to generate an output symbol 125 convolutional code C_{1}(D). Restrictive length To encoder 100 per unit exceeds the number of delay elements in the shift register 110, the encoder 100 of the restrictive length equal To 9. For each information bit 105, introduced in the encoder 100, the output code symbols 125 C_{0}(D), C_{1}(D) depend on the entered bit as well as from the previous K-1 input bits. Therefore, the encoder 100 generates the output code symbols 125 C_{0}(D), C_{1}(D)that can run 2^{K-l}possible States of the encoder.

In a typical communication system output code symbols 125 C_{0}(D), C_{1}(D) then modulate and transmit on zashumlennaya channel (not shown). As a result, the decoder receives the noisy data stream subjected to convolutional coding, and applies the Viterbi algorithm, which uses the properties of convolution codes finally determine the input information sequence U(D) 105.

The advantage of convolutional codes is the repetitive patterns with a high degree, which provides a symmetric code tree. Theoretically convolutional code can pose the ü an infinite sequence of code symbols.
However, due to its symmetry, the number of States subject to assessment when building the most likely path leading to the entered data sequence U(D) 105, reduced to 2^{K-1}(in this case, 256) conditions. In addition, when decoding such a symmetric code of interest is only the most likely (i.e. selected) local path, all other paths can be discarded and no longer be considered. The fact that the most probable global path through the state must follow the selected local path through it.

The Viterbi decoder based on these properties of the code, functioning as a state machine with a limited set of transitions between States. The decoder constructs a hypothesis for each of the 2^{K-1}possible States of the encoder and determines the probability of transition of the encoder of each of these States in the next lot of 2^{K-l}possible States of the encoder on the basis of measurement results obtained from a received noisy data stream subjected to convolutional encoding.

The transition probability is expressed by a value called the metric and which is proportional to the logarithm of the probability values, taken with a negative sign. Obviously the lower the metric, the higher the probability of occurrence. There are two t the PA metric: metric and branch metric. Metric status, also referred to as a metric of the path, expresses the relative probability that given a set of code symbols passed through a particular state. The branch metric expresses the conditional probability that was transferred to the transition from a particular initial state to a specific final state (assuming that the initial state was correct).

The Viterbi algorithm can be summarized as follows: when the time is divided into d samples and for each time sample k, there are n possible States S

k |

i |

k-1 |

j |

Initialization: for the initial time sampling (k=1) initialize the metric stored for each state S

1 |

i |

1 |

i |

Iteration: for each time sample (k=2• (d) attend all these condition S

k |

i |

k |

i |

k-1 |

j |

k |

j |

k-1 |

j |

k |

i |

k |

i |

k |

i |

Reverse chain: after visiting all States corresponding to the last time the sample, identify the condition S

d |

i |

d |

i |

T is thus, for every time sample k, the Viterbi algorithm computes the metrics of the paths leading to States S

k |

n |

k |

n |

Operation 155 “butterfly” contains only those possible transitions between States, which could occur for two specific initial state of the encoder 100. This is partly due to the fact that at any given time the state of the encoder 100 is obtained from the previous state of the encoder when the vig to the right by 1 bit. Next (after shift right) data bits determines which transition occurred from the initial state, and becomes the senior discharge (CF) end state. Therefore, there are only two possible end States in which the transition from the initial state. Thus, as evidenced by figure 2, the encoder 100 can move from the initial state x0” end state “h” or “1x” and from the initial state “x1” end state “h” or “1x”, depending on the values of the information bits U(D). Note that the designation “x0” and “x1” indicates that the least significant digit (Mr) initial state equal to “0” and “1” respectively, and higher digits are represented as “x”; and the designation “h” or “1x” indicates that the SRS end state is equal to 0 or 1, respectively, and the lower bits are represented as “x”. The value of “x” has the same value (for example, 7-bit value), regardless of whether it is part of the representation of the initial state or final state.

Figure 2 also highlights the fact that each transition from the initial state to the final state, generates a hypothetical set of code symbols H_{0}(D), H_{1}(D) orIn fact, when the encoder 100 pieces is no parallel branches of the circuit “butterfly” 155 CERs (for example,
performs transitions from “x0” in “h” or from “x1” to “1x”), for both parallel branches generated code symbols N_{0}(D), H_{1}(D). This feature is partly due to the generally repetitive nature of convolutional codes, as well as by using a generating polynomial encoding, in which SB and MB is set equal to one (i.e. in both the polynomials G_{0}(D) and (G_{1}(D) the coefficients g_{0}and g_{8}equal to 1). Similarly, the code symbolsgenerated when the encoder 100 is valid for any of the diagonal branches schema “butterfly” 155 (for example, carries out the transitions from “x0” to “1x” or from “x1” to “0x”).

According to the above, the module 150 CER calculates metrics tm_{0x}tm_{1x}final States. Logic circuit 150 CER preserves the metric sm_{x0}sm_{x1}initial conditions that are associated with the likelihood that adopted a set of code symbols leads to the initial state “x0” and “x1”. According figv, taking the set of code symbols, the module 140 metric branch calculates a metric value bm_{ij},branch. The module 150 CER “summarizes” the metric bm_{ij},branches corresponding to each of the two transitions leading to a specific final state, with a corresponding metric of s_{
x0}sm_{x1}state. Metric bm_{ij},branch Express the conditional probability of transition from a particular initial state to a specific final state. Metric bm_{ij}branch indicates how closely received code symbols coincide with the hypothetical code symbols H_{0}(D), H_{1}(D) 125 generated by the module 150 CERs and metricbranch indicates how accurately received code symbols coincide withThe value of metrics bm_{ij},branch depends only on the distance between the accepted pair of symbols and a hypothetical pair of symbols H_{0}(D), H_{1}(D).

For each of the two end States of the module CER 150 compares the sum of pairs metric baseline/metric branch, for initial States from which it is possible to come to a final state. Then, the module 150 CER “selects” the most plausible of transitions in each final state, presents the least amount of metrics, and assigns the final state obtained value as a metric tm_{0x}tm_{1x}end state.

According to the above, logic module 150 CER summarizes the metric bm_{ij},the branch metric sm_{x0/sub>
smx1the initial state for each of the two transitions leading to the final state, and decides that the most plausible way in this final state came from the passage that gives a lesser amount of metrics. Then, choose a smaller amount of metrics and assign it a new metric tm0xtm1xend state. The module 150 CERs also preserves the metric conditions (i.e. the cost associated with the most likely path leading to each end state) in RAM 145 States. According figv, choosing the lowest amount of metrics leads to the preservation of single-bit values, called bit solutions, in-memory paths in the module 160 memory circuit reverse. Bit decisions, which is an MRI metrics winning original state, indicates which of the two transitions was selected.}

The module 160 memory circuit reverse retains a bit of the solution, corresponding to the most probable transition in each final state. For the encoder 100 with restrictive length K=9, is generated 2^{K-l}or 256 bits decisions, each of which corresponds to one of 256 possible States of the encoder 100. After generation and preservation matrix of all this information for a given number of States module 160 return circuit begins to state that with the highest likelihood is headed the right way (i.e. comprising the Oia,
which of all relevant most recent time interval, has the lowest cost). After this module 160 return circuit performs a backward pass through the circuit, reading the latest R×256 (i.e. P×2^{K-l}) bits decisions to choose R bits, where R is the effective depth of the return circuit memory paths. Because bits decisions Express the most plausible hypothesis about the many bits that have passed through the encoder 100, they are the best data that can give the decoder. As a result, the deeper into the history of decisions immersed chain, the more credibility the received path merges with, the right way. Thus, the greater the depth R of the reverse chain, the higher the quality of the decoder, but the more delay on the conveyor and memory. Therefore, the depth p of the return circuit, in General, should exceed the limit length To encoder 100 3-10 times. For encoder with K=9 depth R circuit reverse usually set equal to 64.

The loop CER specifies the period during which the module 150 CER calculates new metrics tm_{0x}tm_{1x}end state for a specified number of received code symbols. For a convolutional code with rate 1/2 each pair of received code symbols requires 1 loop for computing the metrics. The length of the loop is equal to the number of clock cycles necessary for the NCD is estline operations CERs under the scheme “butterfly” over all States of the encoder for the two sets of received symbols.
For example, the Viterbi decoder having a single “butterfly” CERs, as shown in figure 2, in General, require 128 clock cycles for each adopted a code symbol for transactions over all 256 States of the encoder 100. To speed processing, you can use an array of schemes “butterfly” CERs of a particular architecture that allows one loop in fewer cycles through the use of multiple schemes “butterfly” CERs.

An example of this architecture is the array 300 schemes “butterfly” CER dimension 8×1, is shown in figure 3. The array 300 provides an 8-fold increase in processing speed due to parallel use of 8 modules 155 schemes “butterfly” CERs. For a set of received code symbols array 300 schemes “butterfly” dimension 8×1 uses all 8 modules 155 schemes “butterfly” to read 16 initial conditions and calculate the 16 relevant metrics tm_{0x}and tm_{1x}final States in a single cycle. According to the above, the module 155 CER takes a metric for each of the original States and the metric bm_{ij},branches for each of the four possible transitions. Metric bm_{ij},branch depends only on the values adopted by the pairs of code symbols and hypothetical character pairs H_{0}1(D) orand is a measure of the distance between them. The value of “X”as part of the binary representation of the initial and final States, is shown in figure 3, represents the four-digit group symbol (i.e. X=[X0,X1,x2,X3]), which registers all 16 bars, running from 0 to 15. Thus, for the two sets of received code symbols, the array 300 schemes “butterfly” dimension 8×1 calculates metrics tm_{0x}tm_{1x}end States for all 256 possible States of the encoder 100 for 32 bars (i.e. by 16 clock cycles for each adopted a code symbol).

The disadvantage of the architecture of the array 300 of dimension 8×1 is that for each set of received code symbols to read 16 metrics of the initial condition and at the same time to generate the necessary metrics of branches in each of the 16 clock cycles. Thus, to perform operations on the array 300 butterflies dimension 8×1 requires a very large amount of memory.

Another option architecture of the array is an array 400 of schemes “butterfly” CER dimension 4×2, depicted in figure 4. The array 400 schemes “butterfly” CER dimension 4×2 provides the same increase in speed as the array 300 of dimension 8×1, but due to the 2 sets of 4 parallel operating modules 155 schemes the butterfly” CERs.
The array 400 solves the problem of memory due to temporary preservation metrics tm_{0x}tm_{1x}interim final States. For example, for one step of the first stage of the array 400 reads the 8 initial conditions and calculates the 8 relevant metrics tm_{0x}tm_{1x}final States. However, the array 400 is not immediately saves metrics tm_{0x}tm_{1x}interim final States. On the contrary, in the same quantum array 400 performs a permutation of the interim final States to supply them as initial conditions for the second stage, and then calculates the 8 relevant metrics tm_{0x}tm_{1x}final States for the next set of received code symbols. Thus, like the array 300 8×1, the array 400 is able to calculate metrics tm_{0x}tm_{1x}final States for the two sets of received code symbols within 32 clock cycles.

The array 400 schemes “butterfly” CER 4×2 has the advantage of reducing the amount of memory status module 150 CERs because metrics interim final States (i.e. metrics tm_{0x}tm_{1x}final States of the first stage) is not required to read from the memory status module 150 CERs or write to it. On the contrary, the value of the intermediate target States combinatorial move on to the next stage, which avoids C the costs and minimize the amount of memory needed.

However, the array 400 schemes “butterfly” CER 4×2 also has its limitations. For example, the advantage of reducing the memory capacity of the States directly caused by the fact that the array 400 provides 2 cascade calculations CER 150 for one clock cycle. This critical path can be a significant limitation to the higher clock frequency.

In addition, as for the array 300 schemes “butterfly” CER dimension 8×1 and array 400 schemes “butterfly” CER dimension 4×2 a performance problem exists in relation to the operation of the reverse chain. According to the above, the module 160 return circuit is designed to preserve bits of the solutions generated by the array of CERs, and to restore the feedback bits stored solutions to generate decoded bits decisions. For encoder with restrictive length K=9 (for example, the encoder 100) array CERs in the decoder generates the 2^{K-1}or 256 bits solutions for each set of received code symbols (i.e., 1 bit decisions for each of the 256 possible States of the encoder), and the memory module 160 return circuit typically has a depth of feedback in memory paths, component P=64 block.

After 32 cycles of treatment, each of which is calculated metrics of the final States for the two sets of received symbols, the module 160 reverse chain starts with the last C is KLA processing (for example,
the rightmost block of memory In_{0}of the 64 memory blocks), according figa. The module 160 return circuit detects among the 256 bits of the solutions contained in the block In_{0}memory circuit reverse, bit decisions R_{0}corresponding to the state with the lowest metric value. This state is defined as the best condition and has an 8-bit address BS_{0}that shown in figv. The module 160 return circuit reads the bit value of the best solution, then enters this value in the address, shifting to the left in BS_{0}the low-order (i.e. bs_{0}according figv. On FIGU also shows that the values of other bits in the address BS_{0}(i.e. bs_{6}bs_{5}bs_{4}bs_{3}bs_{2}bs_{1}also shift to the left that leads to a loss in BS_{0}senior level (i.e. bs_{7}) and the formation of a new address BS_{1}. According figa, BS_{1}is the address values of R_{1}the best state in the block B_{1}memory circuit reverse. Then, the module 160 return circuit reads the value of a bit decision, the corresponding address BS_{1}and inserts left-shift the value in the address BS_{1}generating a new address BS_{2}corresponding to the best state in block In_{2}memory circuit reverse.

This read operation and inserts with left shift is repeated until, until butobarbitone all memory blocks reverse chain (i.e. P=64 blocks). In General, the reverse circuit provides for read operations in a quantity equal to the length R of the reverse circuit, therefore, in this case, for reverse passing the correct path and generating decoded bits decisions requires a 64 read operations. However, such a large number of read operations can reduce the efficiency and performance of the decoding process.

The above problems lead to the need for a system and method that would ensure the effective implementation of high-speed operations of CERs under the scheme of “butterfly” in the implementation of the Viterbi algorithm.

Systems and methods consistent with the principles of the present invention can solve the above-mentioned task of ensuring that the system and method of performing high-speed operations of CERs under the scheme of “butterfly” in the implementation of the Viterbi algorithm.

The system and method consistent with the principles of the present invention is described here in General terms and in relation to options for implementation include the use of the first memory element for storing aggregate metric of the original States. The first memory element connected to the multiplexer that can select between the first and second current paths on the basis of even and odd cycles. The multiplexer is connected to the mechanism of the addition/comparison/the selection tool, which calculates metrics end States for each of the metrics of the original States. A second memory element connected to the mechanism of the addition/comparison/selection and the multiplexer, is used for temporary storage of metrics final States, and the third memory element stores the specified logical bits corresponding to the initial state, providing the lowest metric value end state. Thus, the multiplexer selects the first valid path during even-numbered cycles and delivers the metrics of initial conditions extracted from the first memory element, the mechanism of the addition/comparison/selection to generate metrics final States. During odd cycles, the multiplexer selects the second current path for access to the second memory element and use previously computed metrics final States as intermediate metrics of initial conditions, which allows the mechanism of the addition/comparison/selection to generate metrics of the end States on the basis of metrics intermediate initial States.

The accompanying drawings, which are an integral part of the specification, illustrate a variant embodiment of the invention and, together with the description, explain the objectives, advantages and principles of the invention. In the drawings:

figa - action diagram of the convolutional encoder with K=9 and rate 1/2

figw - block diagram of the system showing the modules of CERs and feedback;

figure 2 is a transition diagram illustrating the operation of CERs under the scheme “butterfly”;

figure 3 is a transition diagram depicting an array of 8×1 schemes “butterfly” CERs;

4 is a transition diagram depicting an array of 4×2 schemes “butterfly” CERs;

figa, 5V - functional diagram of the operation circuit reverse;

figa, 6B is a diagram depicting a variant implementation of the present invention.

The following detailed description of the present invention is given with reference to the accompanying drawings, illustrating preferred embodiments of the present invention. Without going beyond the nature and scope of the invention, it is possible to offer other options for implementation and their varieties. Therefore, the following detailed description should not be construed as limiting the invention. Scope of the invention defined by the attached claims.

The average person skilled in the art it is obvious that described below, the present invention can be implemented in many different embodiments of software implementation, hardware-software and hardware in the objects illustrated in the figures. Real program or specialized control logic used to implement this is part II of the invention, does not limit the present invention. Thus, the present invention will be described without specific reference to a real program or specialized hardware components, and specialists in this field will be able, based on the description given here, to design software and control hardware to implement the preferred alternative implementation of the present invention.

Variant implementation of the present invention depicted in figa, 6V. An implementation option involves the use of array 600 schemes “butterfly” CER dimension 8×1 containing 8 parallel modules 155 schemes “butterfly” CERs to provide 8-fold increase in processing speed. Unlike other attempts to achieve this increase, the array 600 operates during different clock cycles, which reduces the required memory and, simultaneously, to limit the number of calculations performed in a single cycle.

According figa, the array 600 uses 8 modules 155 schemes “butterfly” for even the tact to read the next conjunction of the 16 initial States identified by the 4-bit counter X. Then, the array 600 calculates the 16 relevant metrics tm_{0x}tm_{1x}for the current level of the lattice. After the even-numbered cycle (i.e. during the odd cycle) array 600 uses the target state even stroke as the initial States of odd time signature to the next level of the lattice.
Therefore, the array 600 uses the values tm_{0x}tm_{1x}metrics final States even quantum values sm_{x0}sm_{x1}metrics of the original States of the odd-numbered clock cycles. Then, the array 600 calculates metrics final States of the odd quantum tm_{0x}tm_{1x}in accordance with the values sm_{x0}sm_{x1}metrics for the corresponding level of the lattice.

Thus, for a full treatment of the two sets of received symbols generated by the encoder with K=9 using a modified array 600 schemes “butterfly” CER dimension 8×1 depicted in FIGU requires 32 clock cycles. During even-numbered cycles, the array 600 reads the next set of 16 States identified by the 4-bit counter X increments, and calculates the 16 relevant metrics tm_{0x}tm_{1x}final States for the first set of received symbols. During odd clock cycles, the array 600 uses a finite state even tact as new initial conditions and calculates metrics tm_{0x}tm_{1x}final States of odd tact for the second set of received symbols. Therefore, the array 600 within a single clock cycle performs only one level of CERs, thereby overcoming the problem of computing multi-level CERs for one clock cycle inherent in the array 400 of dimension 4×2.

On FIGU shows a diagram 650 decode the RA Viterbi,
supports a modified array 600 schemes “butterfly” CER dimension 8×1 depicted in figa. Metric sm_{x0}sm_{x1}initial conditions for all the States are stored in RAM 145 States. For illustrative purposes, let's start the description of the circuit operation 650 Viterbi decoder with a read operation of the RAM 145 States during even-numbered cycles. Specialists in this field it is obvious that the description of this option exercise, you can also start by reading from the RAM 145 States during odd clock cycles. Similarly, all read operations can be implemented during odd cycles, and all write operations can occur during even-numbered cycles, or Vice versa.

Therefore, during even-numbered cycles multiplexer the MUKSU 670 is configured to select the information metric initial state for 16 consecutive States of the RAM 145, corresponding to the first set of received code symbols. Information source state is delivered directly to the module 150 CERs, which contains an array 600 of dimension 8×1. Then, the array 600 calculates the corresponding 16 metrics tm_{0x}tm_{1x}final States, which again comes in RAM 145 States and MUKSU 670. The calculated information final state is then fed to the register 680 for temporary storage of information to the end state. Temporary storage of information the final state in the register 680 allows the array 600 to do without re-saving state information in memory,
thereby removing the problem of the memory characteristic of the array 300 of dimension 8×1.

During odd cycles multiplexer the MUKSU 670 selects the information of the end state metrics calculated during the previous clock cycle, contained in the register 680. Then, this information metrics final state is used in the array 600 dimension 8×1 as new metrics sm_{x0}sm_{x1}the source States. Then, the array 600 processes the information metric initial state to generate information metrics final state corresponding to the second set of received code symbols. Information metrics final state is then stored in RAM 145 States, to be used as metrics of initial conditions for the next iteration. For the first and second sets of received code symbols this process is repeated for 32 cycles to generate a 256 bit decisions for each of the two sets of received symbols. Upon completion of 32 ticks scheme 650 Viterbi decoder starts the process from the beginning, for the following two sets of received code symbols.

Diagram 650 of the Viterbi decoder also improves the performance of the reverse chain by reducing the number of read operations needed to generate decoded bits decisions. According to the above, m is Dul 160 return circuit is designed to preserve bits decisions generated by the array of CERs. In addition, two bars (i.e. for odd and even cycles) modified array 600 dimension 8×1 generates 32-bit solutions. Diagram 650 of the Viterbi decoder provides for the preservation of these 32 bits decisions as one 32-bit words of memory, and thus, the bits of the solutions generated during the odd and even cycles are stored in the same word of memory.

So, as mentioned above in connection with the operations return circuit, first, to set the starting point of the reverse passage of the chain in time, use the best condition, identifying the state with the lowest metric from the last processing cycle (i.e., the bit value of the best solution). Since the word memory is 32 bits, there are 16 words in the loop (due to 2 sets of received code symbols), and each of 32-bit words of memory has a unique 8-bit address. One variant of implementation involves the use of 4 bits of the addresses of the best States for selecting the memory word to be read, and 4 other bits of address best condition is to determine the 16 bits of the 32-bit memory word to be read. In particular, if the best state BS_{0}has an 8-bit address (bs_{7}bs_{6}bs_{5}bs_{4}bs_{3}bs_{2}b_{
1}bs_{0}), then, according to this variant implementation, the bits (bs_{5}bs_{4}bs_{3}bs_{2}) are used to select a particular memory word in the memory block In_{0}and bits (bs_{7}bs_{6}bs_{1}bs_{0}) to select the bit decisions R_{0}the best condition. Address BS_{1}new best state is formed by inputting the bit decisions R_{0}the best state in BS_{0}as the least significant bit left-shift (bs_{6}bs_{5}bs_{4}bs_{3}bs_{2}bs_{1}bs_{0}, R_{0}).

Because the calculation of CERs produced over two sets of received symbols, the initial state from which it is possible to come to a final state in accordance with just a few bit decisions, have their own bits of the solutions, which are stored in the same 32-bit word of memory. Thus, an implementation option allows for the selection bits (bs_{6}bs_{1}bs_{0}, R_{0}to select the bit decisions R_{1}the next best state from the second half of 32-bit words of memory. So, bit solutions best condition selected from half of the bits of 32-bit words of memory, and these selected bits allow you to determine which bits of the solutions from the other half of the 32-bit memory word is the next bit of the solution to a better state. Full satisfaction is this,
the number of read operations required for proper completion of the desired path in the reverse direction circuit and generating decoded bits of the solution is reduced by a factor of 2. Thus, for module 160 return circuit having a memory depth of paths P=64 memory block requires only 32 read operations.

The above description of preferred embodiments of the present invention is meant to be illustrative, but not intended to be exhaustive coverage or limit the invention to the specific form set out. The above ideas of the invention provide for the possibility of modifications and variations, which can also be offered in the practical application of the invention. For example, the architecture disclosed here, the embodiments can be easily extended to dimension array of 16×1 or array of dimension 32×1, where for one step, you can generate 32 or 64 States. Additionally, instead of working on two sets of received symbols can offer options for implementation, which work on multiple sets of received symbols. Thus, it should be emphasized that the scope of the invention defined by the attached claims.

1. The method of performing an addition operation(comparison)selection scheme “butterfly” for the implementation of the Sal is rhythm Viterbi, the method comprises the steps are read during even-numbered cycles aggregate metric of the original States of the first memory element corresponding to the first set of received symbols, compute the metric end state for each of the metrics of the original States, temporarily retain metric final States in the second memory element, determine which metrics final States has the smallest value, retain the specified logical bit corresponding to the smallest metric value end state, the third memory element read during odd cycles metric final States of the second memory element and use a few metrics final States as a set of metrics intermediate initial States, the respective second set of received symbols, compute the metric interim end state for each of the metrics intermediate initial conditions determine which of the metrics interim final States has the smallest value, retain the specified logical bit corresponding to the smallest metric value of the interim end state, the third memory element.

2. The method according to claim 1, in which the first and second sets of received symbols is encoded using a restrictive length K.

3. The method according to claim 2, in which the WMD addition operation (comparison)selection scheme “butterfly” realize until
until they reach each of the 2^{K-1}end States for each of the first and second sets of received symbols.

4. The method according to claim 3, in which the operation of addition(comparison)selection scheme “butterfly” is implemented by structure 8×1 schemes “butterfly” addition(comparison)of the selection.

5. The method according to claim 4, in which the set of metrics of initial States consists of metrics for a set of 16 consecutive initial States and the set of 16 successive initial States consistently opt for increasing the even-numbered clock cycles.

6. The method according to claim 5, in which the step of calculating the metrics final States summarize the metrics of initial States with the branch metric associated with each of the two possible transitions, compare each of the amounts metrics of initial conditions and metrics of the branches and choose and prescribe the smallest amount of metric end state.

7. The method according to claim 6, in which the step of calculating the metrics interim final States summarize the metrics intermediate initial States with the branch metric associated with each of the two possible transitions, compare each of the amounts of intermediate metrics of initial conditions and metrics of the branches and choose the lowest amount and assigns a metric of the interim end state.

8. The method according to claim 7, in which Opera is the s addition(comparison)selection scheme “butterfly” is used for decoding data subjected to convolutional encoding.

9. The method according to claim 8, in which the memory module reverse the circuit provides a third memory element containing a set of memory blocks, each storing the specified logical bits for each even and odd clock cycles.

10. The method according to claim 8, which additionally perform the operation of feedback to create a set of values of the decoded bits.

11. The method according to claim 10, in which when the operation circuit reverse to identify the most recent memory blocks in the memory module reverse the circuit specified logical bit with the lowest value, associated logic bit is the smallest value with a specific address, reads the specified logical bits and transfer the logical value of a bit is the smallest value in the low-order address specific, shifting all the values in a specific address on one digit to the left to find the following specific address corresponding to the next memory block in the memory module reverse the chain.

12. System to perform the operations of addition(comparison)selection scheme “butterfly” for the implementation of the Viterbi algorithm, the system includes a first memory element for storing the set of metrics of initial States, a multiplexer, connected to the first memory element to select the first act is his way during even clock cycles and for selecting the second current path during odd clock cycles, a second memory element connected to the multiplexer for temporary storage of metrics final States, the mechanism of addition(comparison)of choice, is connected to the second memory element and a multiplexer to compute the metric end state for each of the metrics of the original States and the third memory element for storing the specified logical bits corresponding to the calculated metrics of the target state with the lowest value, the multiplexer selects the first mentioned current path during even clock cycles and generates metrics of initial States of the first memory element in the mechanism of addition(comparison)of choice to generate metrics final States corresponding to the first set of received symbols, and the multiplexer selects the second current path during odd clock cycles to read metric final States of the second memory element and use a few metrics final States as intermediate metrics source States that the mechanism of addition(comparison)selection generated on the basis of metrics intermediate source state metrics interim final States corresponding to the second set of accepted characters.

13. System according to clause 12, in which the first and second sets of received symbols is encoded using ogranichitel the Noah length K.

14. The system of item 13, in which the operation of addition(comparison)selection scheme “butterfly” is carried out until now visited each of the 2^{K-1}end States for each of the first and second sets of received symbols.

15. System 14, in which the operation of addition(comparison)selection scheme “butterfly” through patterns 8×1 schemes “butterfly” addition(comparison)of the selection.

16. The system of clause 15, in which a set of metrics of initial States consists of metrics for a set of 16 consecutive initial conditions, the choice of the set of 16 successive initial conditions is carried out sequentially for increasing the even-numbered clock cycles.

17. System according to clause 12, in which the mechanism of addition (comparison)selection performs addition operation (comparison)selecting, summarizing metrics of initial States with the branch metric associated with each of the two possible transitions, comparing each of the amounts metrics of initial conditions and metrics of the branches and choosing the smallest sum and assign the metric end state.

18. System 17, in which the operation of addition (comparison)selection scheme “butterfly” is used to decode the data subjected to convolutional encoding.

19. System p, in which the memory module reverse the circuit provides a third ElementPath, contains a set of memory blocks, each storing the specified logical bits for each even and odd clock cycles.

20. The system according to claim 19, in which the memory module reverse the circuit generates a set of values of the decoded bits.

21. The system according to claim 20, in which the memory module reverse the circuit identifies for the most recent memory blocks specified logical bits having the lowest value that associates the logical bit is the smallest value with a specific address, reads the specified logical bits, and transfers the logical value of a bit is the smallest value in the low-order address specific, shifting all the values in a specific address on one digit to the left to find the following specific address corresponding to the next memory block in the memory module reverse the chain.

**Same patents:**

FIELD: Witterby algorithm applications.

SUBSTANCE: system has first memory element for storing metrics of basic states, multiplexer, capable of selection between first and second operating routes on basis of even and odd time step, adding/comparing/selecting mechanism, which calculates metrics of end states for each state metric. Second memory element, connected to adding/comparing/selecting mechanism and multiplexer is used for temporary storage of end states metrics. Multiplexer selects first operating route during even time steps and provides basic states metrics, extracted from first memory element, to said mechanism to form end state metrics. During odd cycles multiplexer picks second operating route for access to second memory element and use of previously calculated end state metrics as metrics of intermediate source states.

EFFECT: higher efficiency.

2 cl, 9 dwg

FIELD: computers.

SUBSTANCE: device has eleven majority elements, four information inputs, two adjustment inputs.

EFFECT: broader functional capabilities.

1 dwg

FIELD: computers.

SUBSTANCE: module has n D-triggers, n AND elements and n OR elements, while output of i-numbered And element is connected to first input of i-numbered OR element, connected by second input to data input of i-numbered D-trigger, setting input and clock input of which are connected respectively to first and second control inputs of module, connected by i-numbered information input to first input of i-numbered And element, second input of which is connected to non-inverse output of i-numbered D-trigger, output of each previous OR element is connected to second input of following OR element, and second input of first and output of n-numbered OR elements are connected respectively to zero potential bus and module output.

EFFECT: simplified adjustment.

2 dwg

FIELD: computers.

SUBSTANCE: device has 2n AND elements, n OR elements, n D-triggers.

EFFECT: simplified construction.

2 dwg, 1 tbl

FIELD: computers.

SUBSTANCE: logic module has And element, first, second majority elements, OR element, three data inputs and two adjustment inputs.

EFFECT: broader functional capabilities.

1 dwg

FIELD: computer science.

SUBSTANCE: device has majority elements, grouped in V+1 group in such a way, that i-numbered (I = 1, V) and V+1 numbered groups contain respectively n and V-1 majority element groups.

EFFECT: broader functional capabilities.

1 dwg

FIELD: computer science.

SUBSTANCE: identifier has twenty two cells, each of which has two inputs, two outputs, AND, XOR elements, while all cells are grouped as a matrix of four rows and seven columns in such a way, that i-numbered (i=1,4) string and j-numbered (j=1,4) column contain respectively 8-i and j cells.

EFFECT: simplified construction.

2 dwg

FIELD: computer science.

SUBSTANCE: device has n computing cells, each of which has AND element, OR element, D-trigger.

EFFECT: simplified construction.

2 dwg, 1 tbl