Title of Invention	"A MODULE FOR GENERATING SISO CIRCUITS FOR DECODING CONVOLUTIONAL CODES"
Abstract	The present invention relates to a module (50) for generating integrated decoding circuits for use, in particular, in turbo devices, to the method for defining the characteristics of and generating convolutional decoding circuits, and to the circuit that can be obtained with said module (50). The module (50) is parametric and, thanks to this feature, makes it possible to generate decoding circuits having different performance characteristics which are such that they can be used in turbo devices employing different decoding modes and different architectures. In addition, the module (50) makes it possible to generate decoding circuits whose distinguishing feature is that they can manage a plurality of generator polynomials selectively and can...

Title of Invention

"A MODULE FOR GENERATING SISO CIRCUITS FOR DECODING CONVOLUTIONAL CODES"

Abstract

The present invention relates to a module (50) for generating integrated decoding circuits for use, in particular, in turbo devices, to the method for defining the characteristics of and generating convolutional decoding circuits, and to the circuit that can be obtained with said module (50). The module (50) is parametric and, thanks to this feature, makes it possible to generate decoding circuits having different performance characteristics which are such that they can be used in turbo devices employing different decoding modes and different architectures. In addition, the module (50) makes it possible to generate decoding circuits whose distinguishing feature is that they can manage a plurality of generator polynomials selectively and can...

Full Text	The present invention relates to a module for generating SISO circuits for decoding convolutional codes. Technical Field The present invention relates to a generator module for telecommunication circuits capable of decoding convolutional codes, to the method for generating this type of circuit, and to the associated circuit. More particularly, the present invention relates to the module for generating integrated decoding circuits for use in devices for decoding concatenated convolutional codes (turbo codes) to the method for defining the characteristics of this type of circuit, and to the decoding circuit that can be obtained with this module. Background Art Integrated circuits can be designed using high-level description languages such as VHDL (Very High Speed Integrated Circuit Hardware Description Language). By means of this design technique and the use of appropriate silicon compilers, it is possible to obtain an integrated component having the characteristics specified using the high- level language, for example, the VDHL description. It is known that the VHDL descriptions of predetermined functions such as those relating to a decoding circuit can constitute libraries of modules referred to as IP or intellectual Property libraries whereby highly complex electronic devices such as SOC (System On Chip) systems can be constructed. A distinguishing feature of the modules belonging to an IP library (IP modules or modules) is that they can be used in the design of multiple electronic devices, thanks to the fact that their interface parameters with other modules or electronic circuits can be 'specialized" before silicon compilation, assigning specific values to variables or parameters determined at the design stage. In accordance with the object of the present invention, reference is made to the IP module for telecommunications and the corresponding decoding circuits that can be used in devices for decoding concatenated convolutional codes (turbo decoding). With reference to the transmission of digital information (data) , it is known that the errors introduced when transmitting data on 'a channel make it necessary to code said data by adding redundancy bits prior to transmission, and to decode them"after they are received by removing the redundancy bit's-. Essentially, thanks to the presence of the redundancy " bits, encoding and decoding make it possible to reconstruct the initia-1 data with a level of certainty or probability which allows for the errors introduced by the transmission channel involved. A variety of well-known techniques can be used to encode and decode data. For the purposes of the present invention, the convolutional encoding and decoding technique is taken into consideration, and the concatenated type, turbo encoding and decoding, in particular. As is known, a convolutional encoding device is capable of using predetermined algorithms to take the information which precedes encoding, i.e., a priori information, into account when encoding data. As is also known, the extent to which encoding is reliable, or in other words the extent to which it guarantees that data will be correctly reconstructed, is directly proportional to the amount of a priori information that the encoding algorithm takes into account. Naturally, the complexity of the algorithm used in encoding and decoding will increase along with the amount of a priori information it considers. To improve the results that can be attained with decoding and to reduce the complexity of the encoding and 'decoding circuits and devices required for any given level of performance the so-callad turbo encoding and decoding devices have been introduced— Whether used for encoding or decoding, turbo devices comprise a plurality of convolutional circuits interconnected in concatenated fashion by means of one or more circuits (known as interleaver circuits) capable of delaying or changing the' order of the bits. In general, the architecture of turbo encoding devices (turbo encoders) thus involves using a plurality of convolutional encoding circuits interconnected using serial or parallel layouts in such a way that encoding is performed in parallel or serially. For example, a convolutional encoding circuit (encoding circuit) 10 (Figure 1) for turbo encoders includes a data input (u) _ and two outputs, one for input data (u) , in which case the circuit is referred to as systematic, and one for encoding information (code) (c) . In addition, the circuit includes a shift register 12 having a length in number of bits (v-1) which in the example is three bits, i.e., bit 21, bit 2 2 and bit 23 respectively. This shift register is capable of receiving data (u) at input and of output ting the code (c) in accordance with the type of internal connections used in encoding circuit 10. The main parameters that characterize encoding circuit 10 are as follows: k denotes the number of bits introduced in sequence per unit of time. In the example and in general, encoding with k = 1 is used. k(V-l) denotes the size of the shift register 12 to be used for encoding, n denotes the number of bits output by the encoder. In general, an encoder receives k bits at a time, which are introduced in the shift register 12 featuring k(v-l) positions; at the encoder output, there will be n output bits for every k input bits (n ≥ k) . Each output bit is calculated via a binary or modulo-2 sum of a certain number of bits in shift register 12; naturally, this sum depends on the encoder's internal connection logic and establishes the so-called generator polynomials, which will be discussed in detail later. In the example, the value u of the input bit is added to the value of' a bit obtained via a feedback connection (path) . The value thus obtained is then added to the value of the first bit 21 of shift register 12 and the result is added to the value of the third bit 23 of shift register 12; in the feedback path, moreover, the third bit 23 and the second bit 22 of shift register 12 are added to the input bit. As known, encoding circuits 10 are referred to as "recursive in 'cases where feedback connections are present. In this way, each'coded bit (c) depends not only on the k bits received at any given instant, but also on the k* bits (v-1) received previously. In accordance with the prior art, the term "codeword" is used to designate the set of n. bits supplied at the encoder output. In the example there are two codewords, viz., the data provided at input (u) and the associated code (c) , The value k/n is called the "code rate". In general, encoding circuits' performance characteristics are defined on the basis of the parameters indicated above. In particular, these characteristics include: - v Constraint length of the decoding circuit or code, which naturally depends on the length of the shift register, - Nst Number of states corresponding to the value 2 >c'v -1) and which corresponds to the number of possible binary combinations in the shift register, g- Generator polynomial for c, which defines the interconnections for generating code c, and gf Generator polynomial for fm which defines the interconnections for generating feedback information f. As is known, the generator polynomial is uniquely identified hy a binary word consisting of V bits. Each bxt of the binary word corresponds to a position of the input data or of the shift register and, by convention, if the bit is at value 1 in the generator polynomial, the input data or that stored in the shift register in the corresponding position participates in computing the feedback or output code. If the bit is at value 0, it does not participate. In the example shown in Figure 1, V is equal to 4 bits, the polynomial gc is, as will be readily apparent to specialists in the field, 1101 (13 DEC), while polynomial g£ is 1011 (11 DEC) . Encoding is generally described with a so-called trellis diagram. For the encoding circuit in Figure 1, for example, Figure 2 shows the corresponding crellis diagram 20 'where all possible •changes in the encoding circuit over time for the various input values u and circuit state are expressed graphically using connecting lines called edges. Trellis diagram 20 also shows output data, i.e., u and c respectively, on the edges. The foregoing considerations regarding the performance characteristics of encoding circuits for turbo devices also apply to the characteristics of decoding circuits for turbo devices (turbo decoders) given that, as will be readily apparent to a specialist in the field, decoding circuits must have characteristics which are equivalent to those of encoding circuits if they are to be able to decode coded information correctly. Naturally, input information for decoding circuits consists of bits for systematic information estimation (u) and of bits for redundancy information estimation (c) obtained in accordance with the prior art at the output of the transmission channel following a demodulation operation. The type of encoding used by the turbo device, e.g., parallel or serial, is another of the parameters to be considered in implementing both turbo decoders and the decoding circuits they contain. A technical disadvantage of prior art systems for designing turbo decoders is that there are no available IP modules of decoding circuits which can be used regardless of variations in characteristics. in particular, known IP modules for generating convolutional code decoding circuits are constrained to performance characteristics, and there is thus a one-to-one correspondence between IP modules and .the decoding circuits having a given set of-performance characteristics. A further disadvantage of prior art systems is that there are no available IP modules of decoding circuits that can be used regardless of variations in encoding mode. Naturally, thus means that the IP modules of decoding circuits that can be used, in turbo decoders differ according to the turbo encoding mode involved. In addition, known IP modules of decoding circuits are constrained to the use of specific methods and technologies. Essentially, known IP modules of decoding circuits are not parametric as regards the performance characteristics of the architecture and the decoder and, because of this limitation, make it necessary to make design choices very early in the process. If, conversely, these modules were parametric and_ flexible, these choices could be made at later stages. This would provide clear advantages, particularly in cases where it becomes necessary to change the characteristics of the algorithms to be used or the architecture. Yet another technical disadvantage which' specifically affects decoder circuits implemented on silicon or using programmable logic is that once implemented, these circuits can use only one generator polynomial, or in other words only one type of decoding function for reconstructing initial data. This is an extremely significant limitation of prior art systems, particularly in the case of turbo devices which use serial decoding. In serial mode decoding, as is known, a second decoding circuit or stage is 'occupied in decoding at different times than the first circuit or stage, given that information from the first stage must be used for decoding. It is thus possible in principle co use a single decoding circuit in turbo decoders which employ serial decoding approaches . With prior art systems, however, using a single decoding circuit is possible only if the turbo decoder's decoding stages use a single pair of generator polynomials. In cases where two or more decoding stages use different generator polynomials, this constraint means that serial turbo decoders must include a corresponding number of decoding circuits, which clearly increases the device's complexity and the associated development costs, given that each individual decoding circuit generally contains a large number of equivalent gates, e.g., around 150,000. Naturally, this constraint would be overcome if decoder circuits for turbo devices existed which could manage a plurality of generator polynomials. Disclosure of the Invention •The object of the present invention is an IP module for generating decoding circuits featuring different performance characteristics which are such that they can be used in decoding devices employing different decoding modes and different technologies. Another object of the present invention is a method for generating decoding modules with the characteristics indicated above. Yet another object of the present invention is a decoding circuit for turbo devices capable of managing a plurality of generator polynomials selectively. In accordance with these objects, the present invention proposes a generator module for decoding circuits as claimed in claim 1, a. method for generating such circuits as claimed in claim 7, and a convolutional decoding circuit as claimed in claim 9 . Brief Description of Drawings The above and other features of the present invention will be better understood from the following description of a preferred embodiment of the invention, which is intended purely by way of example and is not to be construed as limiting, where: Figure 1 represents a logic diagram of a systematic and recursive convolutional encoding circuit; Figure 2 represents the trellis diagram for the circuit illustrated in Figure 1; Figure 3 represents a flow chart for generating the module and the circuit in accordance with the invention; Figure 4 represents a general input and output diagram for the module in accordance with the invention; Figure 5 represents the general architecture of the module and of the circuit that can be obtained by means of the flow chart shown in Figure 3; Figure 6 represents the architecture of the memory element for the module and circuit shown in Figure 5; and Figure 7 represents the architecture of the characteristic computing element for the module and circuit shown in Figure 5. Best mode for Carrying Out the Invention A preferred embodiment of the invention will be described with reference to Figure 3, which shows the flow chart for designing a generator module for convolutional code decoding circuits in accordance with the present invention. In a first stage designated as 100, the general specifications for the dencoding circuit are defined. In particular, various encoding methods are examined together with the possible architectures for the corresponding decoding circuits. Taking convoluti'onal encoding for turbo encoders as a reference, one of the first constraints for turbo decoders and the circuits they contain is that the decoding operations for convolutional codes must be iterated a number of times which is a multiple of the number of convolutional encoding circuits contained in the turbo encoder. This means that the output of one decoder circuit will be the input of another such" circuit. This in turn means that it is necessary to use Soft Input Soft Output (SISO) decoder circuits which, as is known, make it possible to continue iterating the decoding cycles until such time as the degree of reliability required by specifications has been reached Consequently, on the basis of encoding characteristics, the first specification requirement for decoder circuit generator modules in accordance with the present invention is that these modules must generate SISO circuits in which input and output information consists of probabilistic estimates of transmitted information. Naturally, the fact that modules for generating SISO circuits must be implemented leads to a second constraint, viz., that decoding must make use of a SISO type algorithm such as that proposed by Benedetto, Divslar, Montorsi and Pollara in the document "Soft-Input Soft-Output modules for the construction and distributed iterative decoding of code networks", Department of Electronics, Politecnico di Torino, November 1996. (Formula Removed) Algorithm 1] and 2], of known type, refers to the trellis diagram edges rather than to state pairs and is thus completely general. Consequently, it can work with codes that are not necessarily .binary and with trellises with multiple transitions. However, algorithm lj and 2] has a major drawback in that it is subject to a strict implemencation constraint which requires it to wait for the end of data transmission before decoding can begin. In accordance with the objects of the present invention, it was preferred to make use of the so-called additive SISO algorithm (additive sliding window algorithm) , which is likewise of known type. This algorithm, which derives from the original SISO algorithm 1] and 2], makes it possible to work with a constant quantity of stored data (which is thus independent of transmission duration) and to return probability distributions refined with a fixed delay D, called latency, at output. The additive version of the algorithm was chosen because it performs addition rather than multiplication operations during computation and is thus unaffected by the well-known difficulties involved in implementing multiplication operations at hardware level. The final version of the algorithm is as follows: Given: (Formula Removed) where a and J3, known as branch metrics, represent the weights of the previous and subsequent bits in defining the probability of a given bit at instant t. The output probability calculation algorithm becomes: (Formula Removed) where: - Letters in upper case italics (e.g., U,C,S,E) designate random variables; - Letters in lower case italics (e.g., u,c,s,e) designate individual occurrences of the random variables indicated above; - The upper case letter P(A) designates the probability of an event A; - Subscript k designates a discrete instant of time, defined in the set of time K; A letter in lower case italics with subscript and superscript (e.g., uklk2) designates a time sequence of the variable from instant kl to instant k.2; - The boldface lower case letters (u,c,s,e) designate the complete sequences of the associated random variables,- - Round brackets '()' designate a time sequence; and - Wavy brackets '{} ' ' designate a finite set of elements. As regards the trellis diagram, on the other hand, the following notation is used: - A generic edge is represented by the variable e; - The starting state is SS(e); - The final state is SE(e); - The input symbol is u(e); - The output symbol is c(e). Nothing changes as regards alpha probability or metric initialization; beta metrics, on the other hand, are initialized as equal and constant for all states, as iteration must start from an unknown state. (Formula Removed) The problem of processing complexity was thus shifted from that of having to perform multiplication operations to that of computing the logarithm of an exponential sum which can be approximated by the relation: (Formula Removed) As is known, this simplification leads to a performance degradation if there is a high signal-to-noise ratio. Consequently, if high performance is to be achieved, the following recursive algorithm can be adopted which provides the exact solution in expression 5] below: (Formula Removed) where two operations are performed in order to evaluate (a) with algorithm 5j: finding the maximum of two numbers, which is relatively easy to implement, and computing log{l+exp{~ \|D\| . Naturally, implementing this .second operation in 5] can be accomplished by means of a look-up table. The version of the algoritlim without this feature and where the maximum value is approximated is called MAX„_log_MA?, ivhereas the version which adopts the correction factor is called log_MAP. In all cases, both the algorithms and the implementation approximations are well known. Thus, a second specification requirement for decoder circuit generator modules in accordance with the present invention is that a decoding algorithm for imp lamentation in the associated circuit nust be identified. A further specification requirement: to be defined at the outset in generating the module in accordance with the present invention consists of identifying one of the possible architectures for the module. An analysis carried out at specification stage 100 indicates that the possible architectures which implement the SISO algorithm can be divided into two families: architectures with memories, and parallel register type pipeline architectures. The former, as is known, are clearly the best choice if there are no speed constraints, as they call for far fewer resources. If the most stringent constraints are those on speed, the only way to reach high decoding frequencies is to use parallel register type architectures employing the pipeline technique. Obviously, the choice of the architecture to be implemented will depend to a significant extent on the application for which the module is intended. In order to take the most stringent limits into account, it was found advisable to adopt the solution with a parallel register type pipeline architecture as a third specification requirement. In any case, ' as will be readily apparent from the description of the present embodiment of the invention, parts of the module for generating convolutions! code decoding • circuits in accordance* with the present invention can also he used to implement a model capable of generating decoding circuits having an architecture with memories. Upon completion of stage 100 in accordance with the present invention, the specifications are identified which are needed, to define the types of circuit to be generated (SISO, for example), the algorithm to be implemented (e.g., the additive sliding window algorithm), and the general architecture (e.g., the parallel pipeline architecture). In the second stage, which is designated as 200 the degree of programraability and th§ internal architecture of the decoding module or IP module 50 and the corresponding circuits are defined. Figure 4 shows the IP module 50 interface signals and their meaning, highlighting the circuit characteristics springing from their use. These characteristics are closely linked to the module's parameters, which are an effective tool for implementing circuits intended to cover a wide range of applications In accordance with this example of a preferred embodiment, the SISO input data (INPUTO-3) are the four vord probabilities corresponding to the possible combinations of two bits, i.e., branch metrics, which constitute the signal received from the channel. Consequently, It is assumed that there will be a module and a corresponding circuit external to the IP module 50 which is capable of determining word probabilities starting from the likelihood ratios received from the demodulator output. Output, en the other hand, will consist of calculated probabilities together with estimates of the information bit (u) and of the redundancy bit (c). Input/output data ar'e implemented in the IP module 50 in parametric form, in the sense that they can be specialized prior to silicon compilation and are designed as B_HETRIC and OUT_METRXC for input and cubput respectively. Thanks to these parameters, it is possible no establish the number of bits used to represent input and output data magnitudes, INPUT 0-3 sutd Gutput_u, Output„d respectively. For input data validations, the protocol features an active high signal DVALID_I. The IP module 30 is also provided wibh START_.FRAME_I and 2{ID_FRAM£_I signals which are capable of synchronizing the module by identifying the first: and last bit of the data packet. This technique guarantees module operation without having to include the length of the transmitted data packet among the parameters. Information regarding the start and end of each packet is in any case important, as the sliding window algorithm involves different initialization for metrics at the starting, operating and ending stages. At output, there is a data validation signal (DVALID„0) and * identification signals for the first and last bats in the packet (S7AR?_FRAME„0 and END_FRAME_.0) , which the SISO nodule SO needs in the subsequent iteration. The signal designated EXP makes it possible to represent metrics with an exponential notation, where the exponent, however, is fixed for all metrics in che packet. This technique, in fact, is often used in designing turbo decoders. In effect, a critical aspect of these items is how they handle metrics which tend to increase and lead calculated magnitudes to overflow. To prevent this, a frequently used expedient is to divide all the metrics, reducing their mantissa and retaining information for the operation that was performed through the use of a general exponent. This information is needed when the algorithm with logarithmic correction is implemented, as the correction factor is influenced by the value of the exponent, This makes it possible to avoid the problem of metric overflow without overloading the computations which would have to be carried out if each single metric were represented with an exponent> l-Toduie 53 is also provided with a control signal GEM_CTRL which makes it possible to select arrong four different configurations {which can be set up among the .parameters) for the code generator polynomials, and thus generate circuits capable of managing up to four different pairs of polynomials. In particular, thanks to the G£N_CTRL control signal, it is possible to create circuits that can nanage up to four pairs of different polynomials. As the decoding circuit is highly complex, being able to use it as a shared resource is an important value-added feature. By contrast with the prior art, where the possibility of implementing decoders for concatenated convolutional cedes using a single SISO circuit is limited to the case of symmetrical transmissions, in which concatenated cods units' generator polynomials do not change, the module 50 in accordance with the present invention makes it possible to generate SISO circuits that optimise resource usage and implement the two decoding stages using a single circuit vhich will be described in detail below. The ability to communicate with different generator polynomials, in fact, makes it possible to overcorre the limitations of prior art systems and to guarantee that even asymmetrical transmissions can be managed with a single SISO circuit. The parametricity of module 50 springs from the efforts made to obtain circuits that are able to operate in a variety of applications. Achieving this object involved not only defining parameters for input/output data, but also using confxguxation parameters Internal to module SO which, like the input'output parameters, can also be specialized at the time of silicon compilation and synthesis. As will ce described in detail below, these internal module configuration parameters are evaluated prjor to synthesis and guarantee that different circuits can be generated starting from a single description. The following description will make reference to table 1, which shows all the parameters of module 50 that can be specialized, and which include: 1- Encoding parameters 2~ Decoding parameters 3- Interface parameters 4- Architecture parameters The encoding parameters characterize the transmitted code. The number of encoding states is set by che parameter N_STAT£S which corresponds to the value 2 v;v -1). This parameter has enormous repercussions on the internal structure, as it plays the leading part in determining the actual resources which are used in the module. Once the number of states has been established and assuming k=l, the only parameters whereby trellis diagram 20 (Figure 2), which is represencative of encoding as performed, can be uniquely defined are the generator polynomials gc and gt. These parameters differ from all other parameters inasmuch as they involve a stage preceding code compilation. They are, in fact, processed hy a procedure which takes place before compilation and results in a package in which the trellis characterization vectors are stored. As it is possible to manage up to four pairs of different polynomials, eight different parameters will be used. The decoding parameters characterize decoding, and as such involve only the decoder regardless of the type of encoding carried out. The parameters designated as DEPTH and MAX_log_MAP characterize the selected algorithm, whereas OUTPUTS is influenced by Che type of architecture selected for the decoder as a whole, and «"ill now be described in detail. - Decision DEPTH establishes the width of the windows in which iterations take place. The influence that this parameter has in the structure of the SISO circuit is" chiefly apparent in the metric storage unit; as is to be expected, in fact, the number of data items to be stored increases along with the width of this window, - MAX_Iog_KAP selects the implemented unit, making it possible to determine whether or not the corrective factor is neglected, and OUTPUTS is a parameter which optimizes circuit area occupation in accordance with specifications for the SISO module, given that certain turbo decoder configurations do not need both of the outputs generated by the SISO circuit. In such cases, it is possible to select the appropriate output and thus avoid using the logic resources that generate the magnitude which is not of interest. The interface parameters, which have already been described xn connection with the input/output signals, are involved in representing the SISO module input and output parameters. Their presence is necessary for two reasons the first is associated with decoding quality, as these quantities define ohe internal arithmetic and hence the quality of results. The second r-eason is connected with the need to guarantee that both the module and its interface are necessary and thus ensure that the module can be inserted in complex systems without difficulty. In particular, the parameter B_ME7RIC {Figure 4) represents the quantity of bits used in representing input probabilities, while OUT_METRIC is the cutoff effected at output. Architecture parameters have a direct influence on internal structure for any 'gitfen type of decoding, as they change -its characteristics in terms of speed and area occupation. Trie importance this has is linked to the specific application involved. Seme systems may not pose particular requirement's for data flow processing speed. In such systems, it is. important to be able to reduce complexity by adopting resource sharing techniques. The parameter designated as SPEED is thus the parameter which has the greatest impact in defining the synthesized architecture (Table Removed) As will be readily apparent to a specialist in the field, module 50 with the parameters thus defined :nakes it possible to generate convolutional decoding circuits for turbo devices with extreme flexibility. In particular, said xaodule 50 surpasses, thanks to the parameters described above, the modules hitherto used to generate decoder circuits. The identification of these parameters, and their implementation, is non-trivial, and is one of the qualifying features of the present invention. The interface parameters, moreover, are an innovatory feature for the decoding circuit that can be generated by the IP module 50. The architecture of the SISO module 50 comprises a sub-module representing a storage unit (memory module) 51 (Figure 5} capable of storing the metrics involved in computing probabilities, a sub-module for iterations {STEP module) 52 capable of performing forward and backward iterations, and a sub-module for computing outputs {OCU module) 55 capable of computing output metrics starting front the values of the path and branch metrics. A detailed description of each sub-module is provided below. The architecture as described is shown schematically in Figure 5, which indicates that the part which performs iterations consists of a plurality of elementary STEP modules 520, each of which performs one step of the recursion as will be described in detail later. In accordance with the present example of a preferred embodiment involving a parallel pipeline structure, the memory module 51 is implemented using a shift register Pegister site is highly dependent on the pipe depth of the ir-odules that compute the individual iteration steps, and is parametric on " the basis of the DEPTH parameter. Considering the registers involved in the i-nth recursion step, the depth nee'ded for the forward iteration" {alpha metrics) is equal to pipe depth minus one, as the next step needs the branch metrics for the future step. For backward iteration, on the other hand, the required depth will be that of the pipe plus one, as in this case the metrics for the previous step must be passed to the STEP modules. To optimize resource occupation, the registers for the metrics needed for forward iteration and those for backward iteration are joined in a single shift register whose amplitude is four times the value of B_MSTRXC. This aspect can be better understood by referring to Figure 6, which considers a simplified example in which pipe depth is equal to two and the iteration widow is equal to four. In this case, the depth of shift register 510 xs equal to twelve, given that 2 + 1 shift registers are involved in each step, and four steps are needed. At output, signals are generated that are passed to the module which computes path metrics, and are designated as ALPHA BRANCH for forward iteration and BETA BRANCH for backward iteration. Added co shift register 510 containing branch metrics is a 1-bit shift register 511 which contains information • regarding the first and last bit in the frame (stored starting from the "start* and 'end' signals in tho protocol) co permit the path metrics to be correctly initialized at the beginning and end of the frame. Each elementary STEP module {elementary module) 520 deals with computation for one forward and backward recursion step. The part of the algorithm performed is summarized xn formulas 6] and ?] given below, which are readily reached from formulas 3} and 4] by applying the development shown m formula 5] . Essentially/ the path metric for each state is computed starting from the previous state for forward recursion and from the subsequent state for backward recursion. As the metrics for the path in question are selected by the storage module (the shift register) 51, the inputs to elementary modules 520 refer to the suhscq'ier.t step for beta path metrics, and to the previous step for alpha path metrics. It should be noted the STEP module 52 and its elements 520, in accordance with the present invention, could also be fully reused in an architecture with memories, given that the task of these modules is siraply to perform a step of the algorithm's forward and backward recursions, freeing it from carrying out recursion cycles. Formulas 6] and 7] (Formula Removed) However, given that the pipeline technique is entirely useless in solutions with memories, it would be necessary to include the number of pipe registers to be instantiated among the parameters for the solution with memories. This, naturally, would be accomplished by making use of an optimization command typical of the synthesis program which distributes a parametric number of registers instantiated in the step tail so that the combinatory path is appropriately divided. Consequently, the STEP rr«odule 52 and its elementary components 520 as described are independent of the architecture, whether ic be a parallel pipeline architecture or an architecture with memories, The structure of elementary 3TSP modules 520 will be described in detail with reference to a generic section of trellis diagram 20 (Figure 2, Figure-5 and Figure 7) -for encoding in a UMTS application; note that the diagram can be divided into equal butterfly type * sub-parts 201) so that information regarding only two metrics is needed in order to compute two states. On the basis of this analysis, elementary nodule 520 has been further divided into butterfly elementary nodules 521 and split metrics elementary modules 522. The metrics relating to butterfly 201 to be computed and the path metrics relating to the inpuc states must be passed to butterfly modules 521. For the i-nth butterfly 521, if the block is computing the alpha metrics {forward recursion}, it is necessary to pass the rr.atrics for states 2i and 2ii-l, whereas if the beta metrics are being computed the metrics for states i and i+N_STATES/2 must be passed. The task of selecting the right branch metrics at the various butterfly modules 521 has been delegated to the split metrics modules 522 which starting from the package generated automatically by the trellis and containing the trellis vectors identify the butterfly units to which they are linked and distribute the metrics for the correct words. A battery of registers xs instantiated at the output of each elementary module 520. These registers store the outputs of butterfly modules 521 in che right positions, where they can be taken by the next elementary STEP module. The structure obtained in accordance with this example of a preferred embodiment is illustrated in Ficure 7, which refers to the trellis diagram 20 (Figure 2) for encoding in a UMTS application. It should be noted that a such a breakdown of STEP module 52 {Figure 2, Figure 5 and Figure 7) rftade it possible to achieve the parametricity shown by all features of trellis 20. In applications where speed is not a limiting factor, it can reasonably be assumed that the butterfly modules can be shared in order to perform the functions of elementary STEP modules 520 in several clock cycles. In particular, four configurations are envisaged for this characteristic element of the present invention; these configurations implement 8, 4, 2 and 1 butterfly modules 521 respectively. Obviously, further split metrics modules 522 for metric switching are added for these configurations, along with control modules for the various stages. In addition, memory module 51 must guarantee that information is retained for a time exceeding one clock period. This makes it necessary to use a further control module at the next-highest hierarchical level to synchronize the STEP modules 520 and the memory module 51, It should be noted that an approach of this kind was made possible by the special measures used in the VHDL description. By using "generate" cycles, in fact, it is possible to manage differenc architectural configurations with a high degree of parametricity, and at the same time to produce a description that can be synthesized and optimized. For the sake of completeness, it should be emphasised that the function of butterfly modules 521 is to compute the path metrics given the metrics at the previous step and the branch metrics. In the schematic representation of butterfly modules 521, clock, reset and protocol signals are neglected. The operations to be carried out are characterized by expressions 8) and 3] as given below OUT_ UP = :nax[rN _ UP + PRB _ A, IN _ DN + PRB_ B] + coir OUT_DN = max[lN_UP + PRB-B,lN_UPH-PRB_A] + corr where OUTJJP and OUT__CN represent the output path metrics calculated starting from INJL7P-INJDN {input path metrics) and PRB_A-?RB_B (input braach metrics), and which represent a correction factor. This correction factor is computed by a separate module which simply implements a look-up table. This solution was adopted in order to delegate algorithm selection co the user by means of tne Max_Icg_MAP parameter This module instantiates to further sub-modules which carry out "he elen.encary function of performing two addition operations, conparing them, and selecting the largest sum. These ACS (Add Compare Select) modules, which are not shown in the figure, are the basic computation blocks for decoder module 50, and are the computation units distributed in the entire SISO. The Split_metries nodules 522 were developed specifically to permit parametric description of STEP module 52. In fact, the greatest difficulty in managing different parametric state generator polynomials lies in selecting the right branch metrics The Split_metrics module 522 starts ,from a parameter passed in the description and, during synthesis, generates programmable multiplexers on the basis of the vector values generated by the trellis parameters. These vectors are packaged at the time of generation. Developing this module rtade it possible to provide an important value-added feature, as multiple pairs of parameters can be passed as parameters. The gen_ctrl signal which manages the generator polynomials to be used acts directly on the split_matric modules, which generates a circuit logic made up chiefly of multiplexors whereby the interconnections are switched as needed. It was found that if all of the vector pairs are the same, the synthesis program does not instantiate supplementary logic of any kind, as it proceeds to set up the interconnections. The OCU" module 55 in this example of a preferred embodiment is the ijodule which computes outputs on tne basis of the iteration results supplied by the elementary STEP modules 520 and the input data. This module performs the functions as per forirulas 10} and 11 j given below Formulas 10] and 11] (Formula Removed) As can readily be seen, these formulas differ only slightly from formulas 5] and 1}. Consequently, the OCU module 55 is characterized by the fact that its architecture is similar in all respects zo that of the elementary STEP nodules 520. Once stage 200 has been completed and the degree of prograrrcnability and the internal architecture of the I? module 5C have been defined, a third stage 3 00 is carried out. In this third stage, which is another characteristic feature of the present invention, the individual sub-modules constituting the IP module 50 are developed and described, e.g., using the VHDL language. For the sake of completeness, the sources of the significant modules used in implementing the present invention are given below. In particular, the so-called 'entities" and "structural descriptions" (terms whose rreaning will be known to those familiar with the formalisms used in describing modules in VHDL language) for the significant modules are provided. VHDL CODE FOR SISO MODULE 50 VHDL Code (entities and structural descriptions) (Structures Removed) Once the VHDL language source generation stage 3 00 has been completed, a fourth stage 400 is carried out in which the modules making up the IP encoding module 50 are specialized with particular groups of parameters (parameter scenarios), e.g., in order to implement a decoding circuit for a UMTS application. In the fifth stage 500, zero delay logic simulation is carried out for each scenario defined earlier. Logic simulation, for example, can be performed using commercially available programs such as SYNOPSYS VSS. During stage 500, recycles can be performed to correct modules and/or parameters or constants should errors be found. Once this stage has been successfully completed, the IP module 50 will generally have been simulated with zero delay for all possible parameter scenarios. In the sixth stage 600, the first compilation is performed, e.g., with the SYNOPSYS Design Analyzer program, using a particular parameter scenario such as one designed to result in a particular convolutional encoding circuit. Recycles can also be performed in stage 600. As will be readily apparent to a specialist in the field, such recycles may involve correcting modules and/or certain parameters or constants. In the seventh stage 700, logical optimization is performed, e.g., by making further use of the SYNOPSYS Design Analyzer program, and a library of physical components is "latched" to the compiled modules in such a way as to obtain the actual synthesis compilation needed to produce the physical layout of an encoding circuit for use in a turbo decoder. As will be readily apparent to a specialist in the field, the output of this stage 700 may be either the information needed for the physical implementation of a full-custom integrated circuit, which naturally can be obtained from the supplier of the physical libraries "latched" to the compiled module (stage 80 0) or, alternatively, the information needed for the physical programming of programmable components (stage 900) such as FPGAs (Field Programmable Gate Arrays). Thus, with the flow chart as described, and using an encoding module 50 in accordance with the architecture described herein and specializing the modules with a particular parameter scenario, it is possible in accordance with the present invention to obtain a plurality of encoding circuits, each capable for example of decoding convolutional codes by means of a plurality of generator polynomials that can be activated selectively. The dimensions, forms, materials, components, circuit elements and contacts as contemplated in the foregoing description are capable of modifications in various obvious respects, as are the details of the circuitry and construction as illustrated and of the operating method, all without departing from the scope of the invention as specified in the appended claims. We claim: 1. A module for generating SISO circuits for decoding convolutional codes referred to as turbo codes for telecommunications, comprising - storage means of memory elements (51) for storing probabilistic information associated with digital information; - computing means representative of computing elements (52) for decoding said probabilistic.information on. the basis of at least one - pair' of generator' polynomials for reconstructing said digital - information; - a plurality of pairs of different generator polynomials selectable through a control signal (GEN_CTRL) ; and - scenario, means for configuring said storage means, said computing means and said plurality of pairs of different generator polynomials with parameter scenarios and for generating a single SISO circuit able to manage asymmetrical transmissions by selectively activating, during decoding, different generator polynomials by means of said control signal (GEN CTRL) 2. A module as claimed in claim 1, wherein said scenario means comprise - at least one length constraint parameter associated with said probabilistic information for establishing the size of said memory elements. 3 A module as claimed in claim 1 or 2, wherein said scenario means comprise - at least one number of states parameter associated with said probabilistic information and configurable in order to establish the size of said memory and of said computing elements. 4. A module as claimed in claim 1, 2 or 3, wherein said scenario means comprise - at least one resource sharing parameter for establishing a ,maximum number of computing elements to be used in shared-fashion to decode convolutional Codes. 5. A module as claimed in any of the foregoing claims, wherein said scenario means comprise - at least one architecture parameter for determining that said decoding circuit is associated with a specific type of architecture. 6. A module as claimed in any of the foregoing claims, wherein - at least one parameter representative of a control signal (GEN CTRL) for said decoding circuit for selectively activating one of a plurality of pairs of generator polynomials for decoding said probabilistic information. 7. A single SISO circuit for decoding convolutional codes, generated by a module according to any of the preceding claims, comprising: - memory elements (51) for storing probabilistic information, associated with digital information; - computing' elements (52) for decoding said probabilistic information; .- said computing elements comprising a plurality of generator polynomials representing a plurality of decoding functions; - a control signal (GEN_CTRL) for selectively activating in said computing circuit elements, during decoding, different pairs of generator polynomials in order to manage asymmetrical transmissions.

Full Text

The present invention relates to a module for generating SISO circuits for decoding convolutional codes.
Technical Field
The present invention relates to a generator module for telecommunication circuits capable of decoding convolutional codes, to the method for generating this type of circuit, and to the associated circuit.
More particularly, the present invention relates to the module for generating integrated decoding circuits for use in devices for decoding concatenated convolutional codes (turbo codes) to the method for defining the characteristics of this type of circuit, and to the decoding circuit that can be obtained with this module.
Background Art
Integrated circuits can be designed using high-level description languages such as VHDL (Very High Speed Integrated Circuit Hardware Description Language).
By means of this design technique and the use of appropriate silicon compilers, it is possible to obtain an integrated component having the characteristics specified using the high- level language, for example, the VDHL description.
It is known that the VHDL descriptions of predetermined functions such as those relating to a decoding circuit can constitute libraries of modules referred to as IP or intellectual Property libraries whereby highly complex electronic devices such as SOC (System On Chip) systems can be constructed.
A distinguishing feature of the modules belonging to an IP library (IP modules or modules) is that they can be used in the design of multiple electronic devices, thanks to the fact that their interface parameters with other modules or electronic circuits can be 'specialized" before silicon compilation, assigning specific values to variables or parameters determined at the design stage.
In accordance with the object of the present invention,
reference is made to the IP module for telecommunications and
the corresponding decoding circuits that can be used in
devices for decoding concatenated convolutional codes (turbo
decoding).
With reference to the transmission of digital information (data) , it is known that the errors introduced when transmitting data on 'a channel make it necessary to code said data by adding redundancy bits prior to transmission, and to decode them"after they are received by removing the redundancy bit's-. Essentially, thanks to the presence of the redundancy " bits, encoding and decoding make it possible to reconstruct the initia-1 data with a level of certainty or probability which allows for the errors introduced by the transmission channel involved.
A variety of well-known techniques can be used to encode and decode data.
For the purposes of the present invention, the convolutional encoding and decoding technique is taken into consideration, and the concatenated type, turbo encoding and decoding, in particular.
As is known, a convolutional encoding device is capable of using predetermined algorithms to take the information which precedes encoding, i.e., a priori information, into account when encoding data. As is also known, the extent to which encoding is reliable, or in other words the extent to which it guarantees that data will be correctly reconstructed, is directly proportional to the amount of a priori information that the encoding algorithm takes into account. Naturally, the complexity of the algorithm used in encoding and decoding will increase along with the amount of a priori information it considers.
To improve the results that can be attained with decoding and to reduce the complexity of the encoding and 'decoding
circuits and devices required for any given level of performance the so-callad turbo encoding and decoding devices have been introduced—
Whether used for encoding or decoding, turbo devices comprise a plurality of convolutional circuits interconnected in concatenated fashion by means of one or more circuits (known as interleaver circuits) capable of delaying or changing the' order of the bits.
In general, the architecture of turbo encoding devices (turbo encoders) thus involves using a plurality of convolutional encoding circuits interconnected using serial or parallel layouts in such a way that encoding is performed in parallel or serially.
For example, a convolutional encoding circuit (encoding circuit) 10 (Figure 1) for turbo encoders includes a data input (u) _ and two outputs, one for input data (u) , in which case the circuit is referred to as systematic, and one for encoding information (code) (c) .
In addition, the circuit includes a shift register 12 having a length in number of bits (v-1) which in the example is three bits, i.e., bit 21, bit 2 2 and bit 23 respectively. This shift register is capable of receiving data (u) at input and of output ting the code (c) in accordance with the type of internal connections used in encoding circuit 10.
The main parameters that characterize encoding circuit 10 are as follows:
k denotes the number of bits introduced in sequence per unit of time. In the example and in general, encoding with k = 1 is used.
k*(V-l) denotes the size of the shift register 12 to be used
for encoding, n denotes the number of bits output by the encoder. In general, an encoder receives k bits at a time, which are introduced in the shift register 12 featuring k*(v-l)
positions; at the encoder output, there will be n output bits for every k input bits (n ≥ k) . Each output bit is calculated via a binary or modulo-2 sum of a certain number of bits in shift register 12; naturally, this sum depends on the encoder's internal connection logic and establishes the so-called generator polynomials, which will be discussed in detail later. In the example, the value u of the input bit is added to the value of' a bit obtained via a feedback connection (path) . The value thus obtained is then added to the value of the first bit 21 of shift register 12 and the result is added to the value of the third bit 23 of shift register 12; in the feedback path, moreover, the third bit 23 and the second bit 22 of shift register 12 are added to the input bit. As known, encoding circuits 10 are referred to as "recursive in 'cases where feedback connections are present.
In this way, each'coded bit (c) depends not only on the k bits received at any given instant, but also on the k* bits (v-1) received previously.
In accordance with the prior art, the term "codeword" is used to designate the set of n. bits supplied at the encoder output. In the example there are two codewords, viz., the data provided at input (u) and the associated code (c) , The value k/n is called the "code rate".
In general, encoding circuits' performance characteristics are defined on the basis of the parameters indicated above. In particular, these characteristics include:
- v Constraint length of the decoding circuit or code, which
naturally depends on the length of the shift register,
- Nst Number of states corresponding to the value 2 >c'v -1) and
which corresponds to the number of possible binary
combinations in the shift register,
g- Generator polynomial for c, which defines the interconnections for generating code c, and
gf Generator polynomial for fm which defines the interconnections for generating feedback information f.
As is known, the generator polynomial is uniquely identified hy a binary word consisting of V bits. Each bxt of the binary word corresponds to a position of the input data or of the shift register and, by convention, if the bit is at value 1 in the generator polynomial, the input data or that stored in the shift register in the corresponding position participates in computing the feedback or output code. If the bit is at value 0, it does not participate.
In the example shown in Figure 1, V is equal to 4 bits, the polynomial gc is, as will be readily apparent to specialists in the field, 1101 (13 DEC), while polynomial g£ is 1011 (11 DEC) .
Encoding is generally described with a so-called trellis diagram.
For the encoding circuit in Figure 1, for example, Figure 2
shows the corresponding crellis diagram 20 'where all possible
•changes in the encoding circuit over time for the various
input values u and circuit state are expressed graphically
using connecting lines called edges. Trellis diagram 20 also
shows output data, i.e., u and c respectively, on the edges.
The foregoing considerations regarding the performance
characteristics of encoding circuits for turbo devices also
apply to the characteristics of decoding circuits for turbo
devices (turbo decoders) given that, as will be readily
apparent to a specialist in the field, decoding circuits must
have characteristics which are equivalent to those of encoding
circuits if they are to be able to decode coded information
correctly.
Naturally, input information for decoding circuits consists of bits for systematic information estimation (u) and of bits for redundancy information estimation (c) obtained in accordance
with the prior art at the output of the transmission channel following a demodulation operation.
The type of encoding used by the turbo device, e.g., parallel or serial, is another of the parameters to be considered in implementing both turbo decoders and the decoding circuits they contain.
A technical disadvantage of prior art systems for designing turbo decoders is that there are no available IP modules of decoding circuits which can be used regardless of variations in characteristics.
in particular, known IP modules for generating convolutional code decoding circuits are constrained to performance characteristics, and there is thus a one-to-one correspondence between IP modules and .the decoding circuits having a given set of-performance characteristics.
A further disadvantage of prior art systems is that there are no available IP modules of decoding circuits that can be used regardless of variations in encoding mode.
Naturally, thus means that the IP modules of decoding circuits that can be used, in turbo decoders differ according to the turbo encoding mode involved.
In addition, known IP modules of decoding circuits are constrained to the use of specific methods and technologies.
Essentially, known IP modules of decoding circuits are not parametric as regards the performance characteristics of the architecture and the decoder and, because of this limitation, make it necessary to make design choices very early in the process. If, conversely, these modules were parametric and_ flexible, these choices could be made at later stages. This would provide clear advantages, particularly in cases where it becomes necessary to change the characteristics of the algorithms to be used or the architecture.
Yet another technical disadvantage which' specifically affects decoder circuits implemented on silicon or using
programmable logic is that once implemented, these circuits can use only one generator polynomial, or in other words only one type of decoding function for reconstructing initial data.
This is an extremely significant limitation of prior art systems, particularly in the case of turbo devices which use serial decoding.
In serial mode decoding, as is known, a second decoding circuit or stage is 'occupied in decoding at different times than the first circuit or stage, given that information from the first stage must be used for decoding. It is thus possible in principle co use a single decoding circuit in turbo decoders which employ serial decoding approaches . With prior art systems, however, using a single decoding circuit is possible only if the turbo decoder's decoding stages use a single pair of generator polynomials. In cases where two or more decoding stages use different generator polynomials, this constraint means that serial turbo decoders must include a corresponding number of decoding circuits, which clearly increases the device's complexity and the associated development costs, given that each individual decoding circuit generally contains a large number of equivalent gates, e.g., around 150,000.
Naturally, this constraint would be overcome if decoder circuits for turbo devices existed which could manage a plurality of generator polynomials. Disclosure of the Invention
•The object of the present invention is an IP module for generating decoding circuits featuring different performance characteristics which are such that they can be used in decoding devices employing different decoding modes and different technologies.
Another object of the present invention is a method for generating decoding modules with the characteristics indicated above.
Yet another object of the present invention is a decoding circuit for turbo devices capable of managing a plurality of generator polynomials selectively.
In accordance with these objects, the present invention proposes a generator module for decoding circuits as claimed in claim 1, a. method for generating such circuits as claimed in claim 7, and a convolutional decoding circuit as claimed in claim 9 . Brief Description of Drawings
The above and other features of the present invention will be better understood from the following description of a preferred embodiment of the invention, which is intended purely by way of example and is not to be construed as limiting, where: Figure 1 represents a logic diagram of a systematic and
recursive convolutional encoding circuit; Figure 2 represents the trellis diagram for the circuit
illustrated in Figure 1; Figure 3 represents a flow chart for generating the module and
the circuit in accordance with the invention; Figure 4 represents a general input and output diagram for the
module in accordance with the invention; Figure 5 represents the general architecture of the module and of the circuit that can be obtained by means of the flow chart shown in Figure 3; Figure 6 represents the architecture of the memory element for
the module and circuit shown in Figure 5; and Figure 7 represents the architecture of the characteristic computing element for the module and circuit shown in Figure 5. Best mode for Carrying Out the Invention
A preferred embodiment of the invention will be described with reference to Figure 3, which shows the flow chart for
designing a generator module for convolutional code decoding circuits in accordance with the present invention.
In a first stage designated as 100, the general specifications for the dencoding circuit are defined. In particular, various encoding methods are examined together with the possible architectures for the corresponding decoding circuits.
Taking convoluti'onal encoding for turbo encoders as a reference, one of the first constraints for turbo decoders and the circuits they contain is that the decoding operations for convolutional codes must be iterated a number of times which is a multiple of the number of convolutional encoding circuits contained in the turbo encoder.
This means that the output of one decoder circuit will be the input of another such" circuit. This in turn means that it is necessary to use Soft Input Soft Output (SISO) decoder circuits which, as is known, make it possible to continue iterating the decoding cycles until such time as the degree of reliability required by specifications has been reached Consequently, on the basis of encoding characteristics, the first specification requirement for decoder circuit generator modules in accordance with the present invention is that these modules must generate SISO circuits in which input and output information consists of probabilistic estimates of transmitted information.
Naturally, the fact that modules for generating SISO circuits must be implemented leads to a second constraint, viz., that decoding must make use of a SISO type algorithm such as that proposed by Benedetto, Divslar, Montorsi and Pollara in the document "Soft-Input Soft-Output modules for the construction and distributed iterative decoding of code networks", Department of Electronics, Politecnico di Torino, November 1996.

(Formula Removed)

Algorithm 1] and 2], of known type, refers to the trellis diagram edges rather than to state pairs and is thus completely general. Consequently, it can work with codes that are not necessarily .binary and with trellises with multiple transitions. However, algorithm lj and 2] has a major drawback in that it is subject to a strict implemencation constraint which requires it to wait for the end of data transmission before decoding can begin.
In accordance with the objects of the present invention, it was preferred to make use of the so-called additive SISO algorithm (additive sliding window algorithm) , which is likewise of known type.
This algorithm, which derives from the original SISO algorithm 1] and 2], makes it possible to work with a constant quantity of stored data (which is thus independent of transmission duration) and to return probability distributions refined with a fixed delay D, called latency, at output.
The additive version of the algorithm was chosen because it performs addition rather than multiplication operations during computation and is thus unaffected by the well-known difficulties involved in implementing multiplication operations at hardware level. The final version of the algorithm is as follows: Given:
(Formula Removed)

where a and J3, known as branch metrics, represent the weights of the previous and subsequent bits in defining the probability of a given bit at instant t. The output probability calculation algorithm becomes:
(Formula Removed)

where:
- Letters in upper case italics (e.g., U,C,S,E) designate random variables;
- Letters in lower case italics (e.g., u,c,s,e) designate individual occurrences of the random variables indicated above;

- The upper case letter P(A) designates the probability of an event A;
- Subscript k designates a discrete instant of time, defined in the set of time K;
A letter in lower case italics with subscript and superscript (e.g., uklk2) designates a time sequence of the variable from instant kl to instant k.2;
- The boldface lower case letters (u,c,s,e) designate the
complete sequences of the associated random variables,-
- Round brackets '()' designate a time sequence; and
- Wavy brackets '{} ' ' designate a finite set of elements.
As regards the trellis diagram, on the other hand, the following notation is used:
- A generic edge is represented by the variable e;
- The starting state is SS(e);
- The final state is SE(e);
- The input symbol is u(e);
- The output symbol is c(e).
Nothing changes as regards alpha probability or metric initialization; beta metrics, on the other hand, are initialized as equal and constant for all states, as iteration must start from an unknown state.
(Formula Removed)

The problem of processing complexity was thus shifted from that of having to perform multiplication operations to that of computing the logarithm of an exponential sum which can be approximated by the relation:
(Formula Removed)
As is known, this simplification leads to a performance degradation if there is a high signal-to-noise ratio. Consequently, if high performance is to be achieved, the following recursive algorithm can be adopted which provides the exact solution in expression 5] below:
(Formula Removed)
where two operations are performed in order to evaluate (a) with algorithm 5j: finding the maximum of two numbers, which is relatively easy to implement, and computing log{l+exp{~
|D| .
Naturally, implementing this .second operation in 5] can be accomplished by means of a look-up table.
The version of the algoritlim without this feature and where the maximum value is approximated is called MAX„_log_MA?, ivhereas the version which adopts the correction factor is called log_MAP. In all cases, both the algorithms and the implementation approximations are well known.
Thus, a second specification requirement for decoder circuit generator modules in accordance with the present invention is that a decoding algorithm for imp lamentation in the associated circuit nust be identified.
A further specification requirement: to be defined at the outset in generating the module in accordance with the present invention consists of identifying one of the possible architectures for the module.
An analysis carried out at specification stage 100 indicates that the possible architectures which implement the SISO algorithm can be divided into two families: architectures with memories, and parallel register type pipeline architectures. The former, as is known, are clearly the best choice if there are no speed constraints, as they call for far fewer resources.
If the most stringent constraints are those on speed, the only way to reach high decoding frequencies is to use parallel register type architectures employing the pipeline technique.
Obviously, the choice of the architecture to be implemented will depend to a significant extent on the application for which the module is intended.
In order to take the most stringent limits into account, it was found advisable to adopt the solution with a parallel register type pipeline architecture as a third specification requirement.
In any case, ' as will be readily apparent from the
description of the present embodiment of the invention, parts
of the module for generating convolutions! code decoding
• circuits in accordance* with the present invention can also he
used to implement a model capable of generating decoding
circuits having an architecture with memories.
Upon completion of stage 100 in accordance with the present invention, the specifications are identified which are needed, to define the types of circuit to be generated (SISO, for example), the algorithm to be implemented (e.g., the additive sliding window algorithm), and the general architecture (e.g., the parallel pipeline architecture).
In the second stage, which is designated as 200 the degree of programraability and th§ internal architecture of the decoding module or IP module 50 and the corresponding circuits are defined.
Figure 4 shows the IP module 50 interface signals and their meaning, highlighting the circuit characteristics springing from their use. These characteristics are closely linked to the module's parameters, which are an effective tool for implementing circuits intended to cover a wide range of applications
In accordance with this example of a preferred embodiment,
the SISO input data (INPUTO-3) are the four vord probabilities
corresponding to the possible combinations of two bits, i.e.,
branch metrics, which constitute the signal received from the
channel.
Consequently, It is assumed that there will be a module and a corresponding circuit external to the IP module 50 which is capable of determining word probabilities starting from the likelihood ratios received from the demodulator output.
Output, en the other hand, will consist of calculated probabilities together with estimates of the information bit (u) and of the redundancy bit (c).
Input/output data ar'e implemented in the IP module 50 in parametric form, in the sense that they can be specialized prior to silicon compilation and are designed as B_HETRIC and OUT_METRXC for input and cubput respectively.
Thanks to these parameters, it is possible no establish the number of bits used to represent input and output data magnitudes, INPUT 0-3 sutd Gutput_u, Output„d respectively.
For input data validations, the protocol features an active high signal DVALID_I.
The IP module 30 is also provided wibh START_.FRAME_I and 2{ID_FRAM£_I signals which are capable of synchronizing the module by identifying the first: and last bit of the data packet. This technique guarantees module operation without having to include the length of the transmitted data packet among the parameters. Information regarding the start and end of each packet is in any case important, as the sliding window algorithm involves different initialization for metrics at the starting, operating and ending stages.
At output, there is a data validation signal (DVALID„0) and * identification signals for the first and last bats in the packet (S7AR?_FRAME„0 and END_FRAME_.0) , which the SISO nodule SO needs in the subsequent iteration.
The signal designated EXP makes it possible to represent metrics with an exponential notation, where the exponent, however, is fixed for all metrics in che packet. This technique, in fact, is often used in designing turbo decoders. In effect, a critical aspect of these items is how they handle
metrics which tend to increase and lead calculated magnitudes to overflow. To prevent this, a frequently used expedient is to divide all the metrics, reducing their mantissa and retaining information for the operation that was performed through the use of a general exponent. This information is needed when the algorithm with logarithmic correction is implemented, as the correction factor is influenced by the value of the exponent, This makes it possible to avoid the problem of metric overflow without overloading the computations which would have to be carried out if each single metric were represented with an exponent>
l-Toduie 53 is also provided with a control signal GEM_CTRL which makes it possible to select arrong four different configurations {which can be set up among the .parameters) for the code generator polynomials, and thus generate circuits capable of managing up to four different pairs of polynomials.
In particular, thanks to the G£N_CTRL control signal, it is possible to create circuits that can nanage up to four pairs of different polynomials.
As the decoding circuit is highly complex, being able to use it as a shared resource is an important value-added feature.
By contrast with the prior art, where the possibility of implementing decoders for concatenated convolutional cedes using a single SISO circuit is limited to the case of symmetrical transmissions, in which concatenated cods units' generator polynomials do not change, the module 50 in accordance with the present invention makes it possible to generate SISO circuits that optimise resource usage and implement the two decoding stages using a single circuit vhich will be described in detail below.
The ability to communicate with different generator polynomials, in fact, makes it possible to overcorre the limitations of prior art systems and to guarantee that even
asymmetrical transmissions can be managed with a single SISO circuit.
The parametricity of module 50 springs from the efforts made to obtain circuits that are able to operate in a variety of applications.
Achieving this object involved not only defining parameters for input/output data, but also using confxguxation parameters Internal to module SO which, like the input'output parameters, can also be specialized at the time of silicon compilation and synthesis.
As will ce described in detail below, these internal module configuration parameters are evaluated prjor to synthesis and guarantee that different circuits can be generated starting from a single description.
The following description will make reference to table 1, which shows all the parameters of module 50 that can be specialized, and which include: 1- Encoding parameters 2~ Decoding parameters
3- Interface parameters
4- Architecture parameters
The encoding parameters characterize the transmitted code.
The number of encoding states is set by che parameter N_STAT£S
which corresponds to the value 2 v*;v -1).
This parameter has enormous repercussions on the internal
structure, as it plays the leading part in determining the
actual resources which are used in the module.
Once the number of states has been established and assuming k=l, the only parameters whereby trellis diagram 20 (Figure 2), which is represencative of encoding as performed, can be uniquely defined are the generator polynomials gc and gt. These parameters differ from all other parameters inasmuch as they involve a stage preceding code compilation. They are, in fact, processed hy a procedure which takes place before compilation
and results in a package in which the trellis characterization vectors are stored. As it is possible to manage up to four pairs of different polynomials, eight different parameters will be used.
The decoding parameters characterize decoding, and as such involve only the decoder regardless of the type of encoding carried out.
The parameters designated as DEPTH and MAX_log_MAP characterize the selected algorithm, whereas OUTPUTS is influenced by Che type of architecture selected for the decoder as a whole, and «"ill now be described in detail. - Decision DEPTH establishes the width of the windows in which iterations take place. The influence that this parameter has in the structure of the SISO circuit is" chiefly apparent in the metric storage unit; as is to be expected, in fact, the number of data items to be stored increases along with the width of this window,
- MAX_Iog_KAP selects the implemented unit, making it possible to determine whether or not the corrective factor is neglected, and
OUTPUTS is a parameter which optimizes circuit area occupation in accordance with specifications for the SISO module, given that certain turbo decoder configurations do not need both of the outputs generated by the SISO circuit. In such cases, it is possible to select the appropriate output and thus avoid using the logic resources that generate the magnitude which is not of interest.
The interface parameters, which have already been described xn connection with the input/output signals, are involved in representing the SISO module input and output parameters. Their presence is necessary for two reasons* the first is associated with decoding quality, as these quantities define ohe internal arithmetic and hence the quality of results. The second r-eason is connected with the need to guarantee that
both the module and its interface are necessary and thus ensure that the module can be inserted in complex systems without difficulty.
In particular, the parameter B_ME7RIC {Figure 4) represents the quantity of bits used in representing input probabilities, while OUT_METRIC is the cutoff effected at output.
Architecture parameters have a direct influence on internal structure for any 'gitfen type of decoding, as they change -its characteristics in terms of speed and area occupation. Trie importance this has is linked to the specific application involved.
Seme systems may not pose particular requirement's for data flow processing speed. In such systems, it is. important to be able to reduce complexity by adopting resource sharing techniques.
The parameter designated as SPEED is thus the parameter which has the greatest impact in defining the synthesized architecture

(Table Removed)

As will be readily apparent to a specialist in the field, module 50 with the parameters thus defined :nakes it possible to generate convolutional decoding circuits for turbo devices with extreme flexibility. In particular, said xaodule 50 surpasses, thanks to the parameters described above, the modules hitherto used to generate decoder circuits.
The identification of these parameters, and their implementation, is non-trivial, and is one of the qualifying features of the present invention.
The interface parameters, moreover, are an innovatory feature for the decoding circuit that can be generated by the IP module 50.
The architecture of the SISO module 50 comprises a sub-module representing a storage unit (memory module) 51 (Figure 5} capable of storing the metrics involved in computing probabilities, a sub-module for iterations {STEP module) 52 capable of performing forward and backward iterations, and a sub-module for computing outputs {OCU module) 55 capable of
computing output metrics starting front the values of the path and branch metrics.
A detailed description of each sub-module is provided below. The architecture as described is shown schematically in Figure 5, which indicates that the part which performs iterations consists of a plurality of elementary STEP modules 520, each of which performs one step of the recursion as will be described in detail later.
In accordance with the present example of a preferred embodiment involving a parallel pipeline structure, the memory module 51 is implemented using a shift register Pegister site is highly dependent on the pipe depth of the ir-odules that compute the individual iteration steps, and is parametric on " the basis of the DEPTH parameter. Considering the registers involved in the i-nth recursion step, the depth nee'ded for the forward iteration" {alpha metrics) is equal to pipe depth minus one, as the next step needs the branch metrics for the future step. For backward iteration, on the other hand, the required depth will be that of the pipe plus one, as in this case the metrics for the previous step must be passed to the STEP modules. To optimize resource occupation, the registers for the metrics needed for forward iteration and those for backward iteration are joined in a single shift register whose amplitude is four times the value of B_MSTRXC.
This aspect can be better understood by referring to Figure 6, which considers a simplified example in which pipe depth is equal to two and the iteration widow is equal to four.
In this case, the depth of shift register 510 xs equal to twelve, given that 2 + 1 shift registers are involved in each step, and four steps are needed.
At output, signals are generated that are passed to the module which computes path metrics, and are designated as ALPHA
BRANCH for forward iteration and BETA BRANCH for backward iteration.
Added co shift register 510 containing branch metrics is a 1-bit shift register 511 which contains information • regarding the first and last bit in the frame (stored starting from the "start* and 'end' signals in tho protocol) co permit the path metrics to be correctly initialized at the beginning and end of the frame.
Each elementary STEP module {elementary module) 520 deals with computation for one forward and backward recursion step. The part of the algorithm performed is summarized xn formulas 6] and ?] given below, which are readily reached from formulas 3} and 4] by applying the development shown m formula 5] .
Essentially/ the path metric for each state is computed starting from the previous state for forward recursion and from the subsequent state for backward recursion.
As the metrics for the path in question are selected by the storage module (the shift register) 51, the inputs to elementary modules 520 refer to the suhscq'ier.t step for beta path metrics, and to the previous step for alpha path metrics. It should be noted the STEP module 52 and its elements 520, in accordance with the present invention, could also be fully reused in an architecture with memories, given that the task of these modules is siraply to perform a step of the algorithm's forward and backward recursions, freeing it from carrying out recursion cycles. Formulas 6] and 7]
(Formula Removed)

However, given that the pipeline technique is entirely useless in solutions with memories, it would be necessary to include
the number of pipe registers to be instantiated among the
parameters for the solution with memories.
This, naturally, would be accomplished by making use of an
optimization command typical of the synthesis program which
distributes a parametric number of registers instantiated in
the step tail so that the combinatory path is appropriately
divided.
Consequently, the STEP rr«odule 52 and its elementary components 520 as described are independent of the architecture, whether ic be a parallel pipeline architecture or an architecture with memories,
The structure of elementary 3TSP modules 520 will be described in detail with reference to a generic section of trellis diagram 20 (Figure 2, Figure-5 and Figure 7) -for encoding in a UMTS application; note that the diagram can be divided into equal butterfly type * sub-parts 201) so that information regarding only two metrics is needed in order to compute two states.
On the basis of this analysis, elementary nodule 520 has been further divided into butterfly elementary nodules 521 and split metrics elementary modules 522.
The metrics relating to butterfly 201 to be computed and the path metrics relating to the inpuc states must be passed to butterfly modules 521.
For the i-nth butterfly 521, if the block is computing the alpha metrics {forward recursion}, it is necessary to pass the rr.atrics for states 2*i and 2*ii-l, whereas if the beta metrics are being computed the metrics for states i and i+N_STATES/2 must be passed.
The task of selecting the right branch metrics at the various butterfly modules 521 has been delegated to the split metrics modules 522 which starting from the package generated automatically by the trellis and containing the trellis
vectors identify the butterfly units to which they are linked and distribute the metrics for the correct words.
A battery of registers xs instantiated at the output of each elementary module 520. These registers store the outputs of butterfly modules 521 in che right positions, where they can be taken by the next elementary STEP module. The structure obtained in accordance with this example of a preferred embodiment is illustrated in Ficure 7, which refers to the trellis diagram 20 (Figure 2) for encoding in a UMTS application.
It should be noted that a such a breakdown of STEP module 52 {Figure 2, Figure 5 and Figure 7) rftade it possible to achieve the parametricity shown by all features of trellis 20.
In applications where speed is not a limiting factor, it can reasonably be assumed that the butterfly modules can be shared in order to perform the functions of elementary STEP modules 520 in several clock cycles.
In particular, four configurations are envisaged for this characteristic element of the present invention; these configurations implement 8, 4, 2 and 1 butterfly modules 521 respectively. Obviously, further split metrics modules 522 for metric switching are added for these configurations, along with control modules for the various stages.
In addition, memory module 51 must guarantee that information is retained for a time exceeding one clock period. This makes it necessary to use a further control module at the next-highest hierarchical level to synchronize the STEP modules 520 and the memory module 51,
It should be noted that an approach of this kind was made possible by the special measures used in the VHDL description. By using "generate" cycles, in fact, it is possible to manage differenc architectural configurations with a high degree of parametricity, and at the same time to produce a description that can be synthesized and optimized.
For the sake of completeness, it should be emphasised that the function of butterfly modules 521 is to compute the path metrics given the metrics at the previous step and the branch metrics. In the schematic representation of butterfly modules 521, clock, reset and protocol signals are neglected. The operations to be carried out are characterized by expressions 8) and 3] as given below
OUT_ UP = :nax[rN _ UP + PRB _ A, IN _ DN + PRB_ B] + coir OUT_DN = max[lN_UP + PRB-B,lN_UPH-PRB_A] + corr
where OUTJJP and OUT__CN represent the output path metrics calculated starting from INJL7P-INJDN {input path metrics) and PRB_A-?RB_B (input braach metrics), and which represent a correction factor.
This correction factor is computed by a separate module which simply implements a look-up table. This solution was adopted in order to delegate algorithm selection co the user by means of tne Max_Icg_MAP parameter This module instantiates to further sub-modules which carry out "he elen.encary function of performing two addition operations, conparing them, and selecting the largest sum.
These ACS (Add Compare Select) modules, which are not shown in the figure, are the basic computation blocks for decoder module 50, and are the computation units distributed in the entire SISO.
The Split_metries nodules 522 were developed specifically to permit parametric description of STEP module 52. In fact, the greatest difficulty in managing different parametric state generator polynomials lies in selecting the right branch metrics
The Split_metrics module 522 starts ,from a parameter passed in the description and, during synthesis, generates programmable multiplexers on the basis of the vector values generated by
the trellis parameters. These vectors are packaged at the time of generation.
Developing this module rtade it possible to provide an important value-added feature, as multiple pairs of parameters can be passed as parameters. The gen_ctrl signal which manages the generator polynomials to be used acts directly on the split_matric modules, which generates a circuit logic made up chiefly of multiplexors whereby the interconnections are switched as needed. It was found that if all of the vector pairs are the same, the synthesis program does not instantiate supplementary logic of any kind, as it proceeds to set up the interconnections.
The OCU" module 55 in this example of a preferred embodiment is the ijodule which computes outputs on *tne basis of the iteration results supplied by the elementary STEP modules 520 and the input data.
This module performs the functions as per forirulas 10} and 11 j given below Formulas 10] and 11]
(Formula Removed)

As can readily be seen, these formulas differ only slightly from formulas 5] and 1}. Consequently, the OCU module 55 is characterized by the fact that its architecture is similar in all respects zo that of the elementary STEP nodules 520.
Once stage 200 has been completed and the degree of prograrrcnability and the internal architecture of the I? module 5C have been defined, a third stage 3 00 is carried out. In this third stage, which is another characteristic feature of the present invention, the individual sub-modules constituting

the IP module 50 are developed and described, e.g., using the VHDL language.
For the sake of completeness, the sources of the significant modules used in implementing the present invention are given below.
In particular, the so-called 'entities" and "structural descriptions" (terms whose rreaning will be known to those familiar with the* formalisms used in describing modules in VHDL language) for the significant modules are provided.
VHDL CODE FOR SISO MODULE 50 VHDL Code (entities and structural descriptions)

(Structures Removed)

Once the VHDL language source generation stage 3 00 has been completed, a fourth stage 400 is carried out in which the modules making up the IP encoding module 50 are specialized with particular groups of parameters (parameter scenarios), e.g., in order to implement a decoding circuit for a UMTS application.
In the fifth stage 500, zero delay logic simulation is carried out for each scenario defined earlier.
Logic simulation, for example, can be performed using commercially available programs such as SYNOPSYS VSS.
During stage 500, recycles can be performed to correct modules and/or parameters or constants should errors be found.
Once this stage has been successfully completed, the IP module 50 will generally have been simulated with zero delay for all possible parameter scenarios.
In the sixth stage 600, the first compilation is performed, e.g., with the SYNOPSYS Design Analyzer program, using a particular parameter scenario such as one designed to result in a particular convolutional encoding circuit.
Recycles can also be performed in stage 600. As will be readily apparent to a specialist in the field, such recycles may involve correcting modules and/or certain parameters or constants.
In the seventh stage 700, logical optimization is performed, e.g., by making further use of the SYNOPSYS Design Analyzer program, and a library of physical components is "latched" to the compiled modules in such a way as to obtain the actual synthesis compilation needed to produce the physical layout of an encoding circuit for use in a turbo decoder.
As will be readily apparent to a specialist in the field, the output of this stage 700 may be either the information needed for the physical implementation of a full-custom integrated circuit, which naturally can be obtained from the
supplier of the physical libraries "latched" to the compiled module (stage 80 0) or, alternatively, the information needed for the physical programming of programmable components (stage 900) such as FPGAs (Field Programmable Gate Arrays).
Thus, with the flow chart as described, and using an encoding module 50 in accordance with the architecture described herein and specializing the modules with a particular parameter scenario, it is possible in accordance with the present invention to obtain a plurality of encoding circuits, each capable for example of decoding convolutional codes by means of a plurality of generator polynomials that can be activated selectively.
The dimensions, forms, materials, components, circuit elements and contacts as contemplated in the foregoing description are capable of modifications in various obvious respects, as are the details of the circuitry and construction as illustrated and of the operating method, all without departing from the scope of the invention as specified in the appended claims.

We claim:
1. A module for generating SISO circuits for decoding convolutional codes referred to as turbo codes for telecommunications, comprising
- storage means of memory elements (51) for storing probabilistic
information associated with digital information;
- computing means representative of computing elements (52) for
decoding said probabilistic.information on. the basis of at least one
- pair' of generator' polynomials for reconstructing said digital
- information;
- a plurality of pairs of different generator polynomials selectable
through a control signal (GEN_CTRL) ; and
- scenario, means for configuring said storage means, said
computing means and said plurality of pairs of different generator
polynomials with parameter scenarios and for generating a single
SISO circuit able to manage asymmetrical transmissions by
selectively activating, during decoding, different generator
polynomials by means of said control signal (GEN CTRL)
2. A module as claimed in claim 1, wherein said scenario means comprise
- at least one length constraint parameter associated with said probabilistic information for establishing the size of said memory elements.
3 A module as claimed in claim 1 or 2, wherein said scenario means comprise
- at least one number of states parameter associated with said probabilistic information and configurable in order to establish the size of said memory and of said computing elements.
4. A module as claimed in claim 1, 2 or 3, wherein said scenario means comprise
- at least one resource sharing parameter for establishing a ,maximum number of computing elements to be used in shared-fashion to decode convolutional Codes.
5. A module as claimed in any of the foregoing claims, wherein said
scenario means comprise
- at least one architecture parameter for determining that said
decoding circuit is associated with a specific type of architecture.
6. A module as claimed in any of the foregoing claims, wherein
- at least one parameter representative of a control signal (GEN
CTRL) for said decoding circuit for selectively activating one of a
plurality of pairs of generator polynomials for decoding said
probabilistic information.
7. A single SISO circuit for decoding convolutional codes, generated by a module according to any of the preceding claims, comprising:
- memory elements (51) for storing probabilistic information, associated with digital information;
- computing' elements (52) for decoding said probabilistic information;
.- said computing elements comprising a plurality of generator polynomials representing a plurality of decoding functions;
- a control signal (GEN_CTRL) for selectively activating in said computing circuit elements, during decoding, different pairs of generator polynomials in order to manage asymmetrical transmissions.

Documents:

587-delnp-2003-abstract.pdf

587-delnp-2003-claims.pdf

587-delnp-2003-correspondence-others.pdf

587-delnp-2003-correspondence-po.pdf

587-delnp-2003-description (complete).pdf

587-delnp-2003-drawings.pdf

587-delnp-2003-form-1.pdf

587-delnp-2003-form-18.pdf

587-delnp-2003-form-2.pdf

587-delnp-2003-form-3.pdf

587-delnp-2003-form-5.pdf

587-delnp-2003-gpa.pdf

587-delnp-2003-pct-101.pdf

587-delnp-2003-pct-210.pdf

587-delnp-2003-pct-220.pdf

587-delnp-2003-pct-304.pdf

587-delnp-2003-pct-308.pdf

587-delnp-2003-pct-408.pdf

587-delnp-2003-pct-409.pdf

587-delnp-2003-pct-416.pdf

587-delnp-2003-petition-137.pdf

587-delnp-2003-petition-138.pdf

« Previous Patent

Next Patent »

Patent Number

253875

Indian Patent Application Number

587/DELNP/2003

PG Journal Number

36/2012

Publication Date

07-Sep-2012

Grant Date

30-Aug-2012

Date of Filing

17-Apr-2003

Name of Patentee

TELECOM ITALIA S.P.A

Applicant Address

PIAZZA DEGLI AFFARI, 2, I-20123 MILANO, ITALY

Inventors:

#	Inventor's Name	Inventor's Address
1	GIANMARIO BOLLANO	C/O TELECOM ITALIA LAB S.P.A., VIA REISS ROMOLI, 274, I-10148, TORINO, ITALY
2	DONATO ETTORRE	C/O TELECOM ITALIA LAB S.P.A., VIA REISS ROMOLI, 274, I-10148, TORINO, ITALY
3	AMURA TUROLLA	C/O TELECOM ITALIA LAB S.P.A., VIA REISS ROMOLI, 274, I-10148, TORINO, ITALY

PCT International Classification Number

G06F 17/50

PCT International Application Number

PCT/IT2001/00514

PCT International Filing date

2001-10-11

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	TO00A000984	2000-10-19	Italy