CN102386934A

CN102386934A - Second-order rearrangement polynomial interleaver address generating device and method

Info

Publication number: CN102386934A
Application number: CN2010102690520A
Authority: CN
Inventors: 李顺吉; 王忠炫; 沈文和
Original assignee: Industrial Technology Research Institute ITRI
Current assignee: Industrial Technology Research Institute ITRI
Priority date: 2010-09-01
Filing date: 2010-09-01
Publication date: 2012-03-21

Abstract

A second-order rearrangement polynomial interleaver address generation device and method. The second-order permutation polynomial (QPP) interleaver address generating device is based on a QPP function pi (i) ═ f₁i+f₂i²) mod k, receiving configurable parameters and computing and outputting interleaver addresses using QPP units, each QPP unit being a parallel computing unit and outputting a corresponding set of interleaver addresses in parallel, wherein f₁And f₂Is the QPP coefficient, 0 ≦ i ≦ k-1, k is the information block length of an input sequence, mod is a modulo operation, and ii is also an i-th interleaver address generated by the address generation means.

Description

Second order is reset polynomial interleaver address producing device and method

Technical field

The present invention relates to a kind of second order and reset multinomial (quadratic permutation polynomial; QPP) interleaver (interleaver) address produces (address generation) apparatus and method, can produce forward (increasing) or reverse (decreasing) interleaving address.

Background technology

Common turbine code (Turbo code) interleaver designs is to reach with the mode that in advance the interleaver address that calculates is stored in a memory or an address lookup form (address look-up table) mostly.When needs produced the interleaver address, just memory or this address enquiry form were read thus.This will quite expend circuit area and electric power.With the LTE turbine code is example, and its scope of separating code length can be by 40 to 6144.For 188 kinds of specifications of separating code length, it is the interleaver addresses between 40 to 6144 that this memory need be stored 188 group length.The interleaver address of storage maximum length 6144 need spend the memory span of 6144x13=79872 position approximately.

Disclose a kind of QPP interleaver among the U.S. Patent Publication US2008/0115034, can be applicable to the encoding and decoding of turbine code.Explained in this document that serial (serially) produces the algorithm principle of interleaver address.N the value ∏ (n) of the output sequence of its address generator can be described as following form:

∏(n)＝(f ₁n+f ₂n ²)mod?k，n＝0，1，...，k-1，

Wherein, ∏ (n) is n the outgoing position (interleaved output position) that interweaves, f ₁With f ₂Be the QPP coefficient, k is the information area block length (information block length) of list entries, and mod is modular arithmetic (module operation).

Shown in the example of Fig. 1; Control unit 106 utilizes a modulo counter (modulo-counter) 108 to provide an input pointer (input index) n to give an address generator 104; And produce a control signal 108a; Be input into respectively in an address generator 104 and the interleaver memory 102, to point out being to read computing (read operation) or to write (write) computing.The ∏ that address generator 104 calculates (n) value is stored in the interleaver memory 102.When needs interleaver address ∏ (n), again from interleaver memory 102 series read-outs.The outgoing position that interweaves that calculates has the characteristic of exempting from competition (contention free).

U.S. Patent Publication US2002/0159423 discloses a kind of storage address of utilizing a plurality of question blanks to produce the turbine code interleaver.U.S. Patent number US6845482 discloses a kind of technology that produces the interleaver address voluntarily.Its turbine code interleaver is to utilize one to produce the element of prime number index information (index information) and the storage address that five kinds table look-up (look-up table) produces the turbine code interleaver.

Explained in the aforementioned techniques that serial produces algorithm principle, framework and the generation flow process of interleaver address.The technology of most of concurrent operations (parallel operation) focuses on the lifting of the concurrent operation usefulness on logarithm-correspondence (log-MAP) processor (processor) more, and the less output that is directed against after the concurrent operation is done the action that interweaves and be stored in memory that walks abreast and made efficient design.Yet; On actual hardware or circuit design; If the framework based on the address generator of concurrent operation is arranged; When then being applied in decoder architecture, for example use a plurality of log-MAP to do the turbo decoder of concurrent operation, this parallel address generator that produces the address can promote the output speed of decoder.

In the document of Taiwan number of patent application 098130766 (the applicant filed an application on October 13rd, 2009), a kind of QPP interleaver address producing device is provided.This device is according to QPP function ∏ (i)=(f ₁I+f ₂i ²) mod k; Import several configurable parameters; And through the direct a plurality of interleavers of the output address in regular turn, unit of pulling over, a basis, and through the parallel corresponding interleaver of the many groups addresses that directly produce, a plurality of unit of pulling over, according to the result of calculation of this interleaver address; Through a multiplexing data device, each of list entries information can be received in the corresponding storage address.This design need not used complicated circuitry, need not to spend the memory span of storage interleaver address yet.

Summary of the invention

Enforcement example of the present disclosure can provide a kind of QPP interleaver address producing device and method.

Implement in the example one, disclosed person is a kind of QPP interleaver address producing device.This device comprises L QPP unit, is expressed as QPP unit 1 to QPP unit L, L >=2.This device is according to QPP function ∏ (i)=(f ₁I+f ₂i ²) mod k, f ₁With f ₂Be the QPP coefficient, 0≤i≤k-1, k are the information area block lengths of a list entries; And utilize this L QPP unit to calculate and export a plurality of interleavers address; Wherein, ∏ (i) is the i interleaver address that this device produces, and each QPP unit j; 1≤j≤L is all parallel computing unit and and its corresponding one group of interleaver address of line output.

Implement in the example at another, disclosed person is about a kind of QPP interleaver address generating method, is applied to the codec on the communication system.The method comprises: according to QPP function ∏ (i)=(f ₁I+f ₂i ²) mod k, import a plurality of configurable parameters; And calculate and export a plurality of interleavers address through L QPP unit; Each QPP unit j of this L QPP unit, 1≤j≤L, be all a parallel computing unit and and its corresponding one group of interleaver address of line output; Wherein ∏ (i) is i the interleaving address that the method produces, f ₁With f ₂Be the QPP coefficient, k is the information area block length of a list entries, so, lets the information of this list entries insert the address of a plurality of corresponding memories.

Cooperate now following diagram, implement the detailed description and the claim of example, will on address other purposes of the present invention and advantage and be specified in after.

Description of drawings

Fig. 1 is an a kind of example schematic of QPP interleaver.

Fig. 2 is an a kind of example schematic of QPP interleaver, and is consistent with disclosed some enforcement example.

Fig. 3 is an example schematic of QPP interleaver address producing device, and is consistent with disclosed some enforcement example.

Fig. 4 be to root be 2 ^rThe MAP processor, corresponding one group of example schematic of interleaver address or one group of reverse interleaver address forward of explaining that each QPP unit of QPP interleaver address producing device produced, with disclosed some to implement example consistent.

Fig. 5 A and Fig. 5 B are respectively among Fig. 4, and the example schematic of the hardware configuration of QPP unit 1 and the SECO of control signal is consistent with disclosed some enforcement example.

Fig. 6 is among Fig. 4, an example schematic of the hardware configuration of QPP unit j, and j >=2, consistent with disclosed some enforcement example.

Fig. 7 A is a work example of the hardware configuration of QPP unit 1, and wherein employed of MAP processor equals 2 ³, consistent with disclosed some enforcement example.

Fig. 7 B is in QPP unit 1 example of Fig. 7 A, and an example schematic of the SECO of control signal is consistent with disclosed some enforcement example.

Fig. 8 is another work example of the hardware configuration of QPP unit 1, and wherein employed of MAP processor equals 2 ², consistent with disclosed some enforcement example.

Fig. 9 is an example configuration diagram, explains how QPP interleaver address producing device makes a plurality of MAP processors and many data of line output to memory, and is consistent with disclosed some enforcement example.

Figure 10 is a work example schematic, explains how QPP interleaver address producing device makes 40 data of five MAP processors and line output be received in memory, and is consistent with disclosed some enforcement example.

Figure 11 explains in the QPP interleaver address producing device, and the purposes of the position of the interleaver address that calculate each QPP unit is consistent with disclosed some enforcement example.

Figure 12 is with k=40, M=2 ³, f ₁=3, f ₂=10 is example, and the interleaver address of calculating through QPP interleaver address producing device is described, how to determine the address of memory, consistent with disclosed some enforcement example.

Figure 13 is an example schematic, explains how QPP interleaver address producing device produces forward corresponding or reverse interleaver address, come corresponding MAP processor forward or the calculating of inverse path value, with disclosed some to implement example consistent.

Figure 14 is an exemplary flowchart of QPP interleaver address generating method, and is consistent with disclosed some enforcement example.

[main element symbol description]

Embodiment

In the enforcement example of the present disclosure a kind of QPP interleaver address producing device and method can be provided.This QPP address generating technique adopts the design of several parallel computation circuit, calculates forward or reverse interleaver address, and the result of calculation of the OPADD that can walk abreast.This QPP interleaver address producing device also can use as interleaver or anti-interleaver (de-interleaver) address generator, when using with anti-interleaver address generator, only needs the interleaver address of output is got final product as the address of reading a memory.

Shown in the example of Fig. 2, a QPP interleaver 200 is with several parallel computation circuit, parallel computation circuit 1～parallel computation circuit L for example, the result of calculation of the OPADD that walks abreast, with disclosed some to implement example consistent.When the code parallel decoder framework of the MAP processor that is used for different root-R (radix-R) framework; The result of calculation of the address that parallel computation circuit 1～parallel computation circuit L is exported can correspond to L MAP processor; MAP processor 1～MAP processor L for example, employed-R of each MAP processor (=2 ^r) framework.This is for the designer of turbine code; Very big attraction is arranged; Because different root to the MAP processor; QPP interleaver 200 is parallel directly to be calculated and produces corresponding QPP interleaver address and can comprise forward interleaver address or reverse interleaver address, with corresponding MAP processor forward or the calculating of inverse path value (metrics).

Fig. 3 is an example schematic of QPP interleaver address producing device, and is consistent with disclosed some enforcement example.In the example of Fig. 3, QPP interleaver address producing device 300 comprises L QPP unit, is expressed as QPP unit 1 to QPP unit L, L >=2.QPP interleaver address producing device 300 is according to QPP function ∏ (i)=(f ₁I+f ₂i ²) mod k, f ₁With f ₂Be the QPP coefficient, 0≤i≤k-1, k are the information area block lengths of a list entries; Receive several configurable parameters (configurable parameter) 310 and utilize this L QPP unit to calculate and export a plurality of interleavers address; Wherein, ∏ (i) is the i interleaver address that QPP interleaver address producing device 300 produces, and each QPP unit j; 1≤j≤L is all a parallel computing unit and and the corresponding one group of interleaver address of line output.

One group of interleaver address of each QPP unit j and line output can be one group of forward interleaver address 31j or one group of reverse interleaver address 32j.This organize interleaver address 31j forward or this organize code parallel decoder framework that reverse interleaver address 32j can be used for the MAP processor of different root frameworks come corresponding MAP processor forward or the calculating of inverse path value.

For 2≤j≤L, QPP unit j receives the result of calculation of its previous QPP unit j-1 respectively, and parallel computation simultaneously corresponding one group of forward interleaver address 31j or one group of reverse interleaver address 32j.This organizes forward interleaver address 31j and organizes reverse interleaver address 32j therewith and can represent respectively as follows:

∏ (i+ (j-1) M), ∏ (i+ (j-1) M+1) ..., ∏ (i+ (j-1) M+ (r-1)), and

∏(jM-i-1)，∏(jM-i-2)，...；∏(jM-i-r)，

Wherein, M is the width (width) of sliding window (sliding window) of the information output of this list entries.

To root is 2 ^rMAP (Radix-2 ^rMAP) processor j, 1≤j≤L, the corresponding QPP interleaver address explanation that corresponding QPP unit j is produced is as follows.Because QPP function ∏ (i)=(f ₁I+f ₂i ²) mod k, i=0,1 ..., k-1, so, for j=1,

With QPP unit 1 corresponding one group forward interleaver address 311 arrangement be ∏ (i+1)=(f ₁(i+1)+f ₂(i+1) ²) mod k

＝(∏(i)+f ₂+f ₁+2f ₂i)mod?k，i＝0，1，...，k-1 (1)，

And with corresponding one group of reverse interleaver address 321 arrangements of QPP unit 1 do

∏(i-1)＝(f ₁(i-1)+f ₂(i-1) ²)mod?k

＝(∏(i)+f ₂-f ₁-2f ₂i)mod?k，i＝0，1，...，k-1 (2)，

According to this, QPP unit 1 can walk abreast and calculate forward interleaver address ∏ (i) according to formula (1), ∏ (i+1) ..., ∏ (i+ (r-1));

And according to formula (2), walk abreast and calculate reverse interleaver address ∏ (M-i-1), ∏ (M-i-2) ..., ∏ (M-r-1).

Because ∏ (i+M)=(∏ (i)+f ₁M+f ₂M ²+ 2f ₂Mi) mod k, i=0,1 ..., k-1, so, for 2≤j≤L, do with the first group address 31j of QPP unit j arrangement

∏(i+(j-1)M)

＝(∏(i+(j-2)M)+f ₁M+(2j-3)f ₂M ²+2f ₂Mi)mod?k (3)，

∏(i+(j-1)M+1)

＝(∏(i+(j-2)M+1)+f ₁M+(2j-3)f ₂M ²+2f ₂M(i+1))mod?k (4)，

∏(i+(j-1)M+(r-1))

＝(∏(i+(j-2)M+(r-1)+f ₁M+(2j-3)f ₂M ²+2f ₂M(i+(r-1))mod?k(5)

According to formula (3), (4), (5), for 2≤j≤L, QPP unit j can walk abreast and calculate forward interleaver address ∏ (i+ (j-1) M), ∏ (i+ (j-1) M+1) ..., ∏ (i+ (j-1) M+ (r-1)); In like manner, for 2≤j≤L, QPP unit j can walk abreast and calculate reverse interleaver address ∏ (jM-i-1), ∏ (jM-i-2) ..., ∏ (jM-i-r).To root is 2 ^rThe MAP processor, M can be the memory length that each MAP processor writes or reads.So, can original weaving length k be configured as the weaving length that k/M length is all M, also needn't change the circuit or the structure of original decoded device or processor.

Accepting above-mentionedly, is 2 to root ^rMAP (Radix-2 ^rMAP) processor, Fig. 4 are corresponding one group of example schematic of interleaver address or one group of reverse interleaver address forward that each QPP unit of QPP interleaver address producing device is produced, with disclosed some to implement example consistent.In the example of Fig. 4, QPP interleaver address producing device 300 can be imported several configurable parameters, for example shown in the label 410, and k, (f ₁+ f ₂) mod k or f ₂-f ₁-2 (M-1) f ₂Mod k, 2f ₂Mod k, f ₁Mmod k, ∏ (0) or ∏ (M-1); And utilize this L QPP unit to come parallel computation and export the interleaver address; And each QPP unit j; 1≤j≤L, the formula that reaches as stated capable of using come and line output corresponding a group (r) forward interleaver address or one group of (r) reverse interleaver address.

Fig. 5 A and Fig. 5 B are respectively among Fig. 4, and the example schematic of the hardware configuration of QPP unit 1 and the SECO of control signal is consistent with disclosed some enforcement example.Suppose that employed of MAP processor equals 2 ^r, then in the example of Fig. 5 A, get the remainder circuit after available r+1 multiplexer 510-51r, a r register 521-52r and 2r 2-input-addition, label is 531～53r and 541～54r, and the control signal init1 that arranges in pairs or groups realizes QPP unit 1.Getting the remainder circuit after the 2-input-addition is the circuit of generally getting remainder, and for example A of two add operations units and B after add operation, get the remainder after the divisor K, i.e. (A+B) mod K, and available two adders and a multiplexer are realized.In the example of Fig. 5 B, the SECO of control signal init1 is described.Below please in the lump with reference to figure 5A and Fig. 5 B, with the running between the inner member of explanation QPP unit 1.

According to the SECO of Fig. 5 B, at first, through triggering control signal init1 (logical value that is init1 is high (high)), multiplexer 510 is with forward parameter ∏ (0) or reverse parameter ∏ (M-1) export register 521 to; This moment, multiplexer 511 also can be with parameter f forward ₂+ f ₁+ 2f ₂* 2 or reverse parameter f ₂-f ₁-2 (M-3) f ₂Get remainder circuit 541 after exporting 2-input-addition to; Multiplexer 512 also can be with forward parameter 0 or reverse parameter-2 (M-1) f ₂Get remainder circuit 542 after exporting 2-input-addition to; Multiplexer 51r also can be with parameter (2r-4) f forward ₂Or reverse parameter-2 (M-r+1) f ₂Get remainder circuit 54r after exporting 2-input-addition to.When forward parameter ∏ (0) or reverse parameter ∏ (M-1) output, get remainder circuit 532 after also can exporting 2-input-addition to.

Get another input of remainder circuit 511 after the 2-input-addition and then import forward parameter 2 (r-1) f ₂Or reverse parameter-2 (M-r) f ₂After getting 511 computings of remainder circuit after the 2-input-addition, the modular arithmetic of generation R1 is as a result got

remainder circuit

531 and 542～54r after can exporting multiplexer 511 and 2-input-addition respectively to.After getting 542 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation gets remainder circuit 532 after can exporting multiplexer 513 and 2-input-addition respectively to.After getting 532 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation gets remainder circuit 533 (not being shown in graphic) after can exporting register 522 and 2-input-addition respectively to.After getting remainder circuit 54r computing after the 2-input-addition, the modular arithmetic result of generation can export register 52r to.

According to this, when the logical value of init1 when being high, the parallel r that calculates of the example of this QPP unit 1 forward interleaver address ∏ (0)～∏ (r-1) or r reverse interleaver address ∏ (M-1)～∏ (M-r) can deposit in respectively to r register 521～52r.Value in register 52r, i.e. ∏ (r-1) or ∏ (M-r) during output, get remainder circuit 531 after also can exporting 2-input-addition in the lump to.

Then, low value is reduced at the triggering edge of control signal init1, and QPP unit 1 example 500 is with r interleaver address in register 521～52r, and promptly ∏ (0)～∏ (r-1) or ∏ (M-1)～∏ (M-r) exports.Because control signal init1 is a low value; So multiplexer 510 is got remainder circuit 531 calculated result after with 2-input-addition, i.e. ∏ (r) or ∏ (M-r-1); Export register 521 to, this calculated result is got remainder circuit 532 after also can exporting 2-input-addition to.

After low value is reduced at the triggering edge of control signal init1, get modular arithmetic result that remainder circuit 511 produces after the 2-input-addition and be by a last modular arithmetic R1 and parameter 2 (r-1) f forward as a result ₂Or reverse parameter-2 (M-r) f ₂The result who after modular arithmetic, obtains, this new R1 result gets remainder circuit 531 and 542～54r after can exporting multiplexer 511 and 2-input-addition respectively to.Multiplexer 512 can be with parameter 2f ₂Get remainder circuit 542 after exporting 2-input-addition to; After getting 542 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation gets remainder circuit 532 after can exporting multiplexer 513 and 2-input-addition respectively to.After getting 532 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation, i.e. ∏ (r+1) or ∏ (M-r-2) get remainder circuit 533 after can exporting register 522 and 2-input-addition respectively to.Multiplexer 51r can be with parameter (2r-2) f ₂Get remainder circuit 54r after exporting 2-input-addition to; After getting remainder circuit 54r computing after the 2-input-addition, the modular arithmetic result of generation gets remainder circuit 53r after can exporting 2-input-addition to.After getting 532 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation, promptly ∏ (2r-1) or ∏ (M-2r) can export register 52r to.QPP unit 1 example 500 is with r interleaver address in register 521～52r, and promptly ∏ (r)～∏ (2r-1) or ∏ (M-r-1)～∏ (M-2r) exports.Value in register 52r, i.e. ∏ (2r-1) or ∏ (M-2r) during output, get remainder circuit 531 after also can exporting 2-input-addition in the lump to.

According to this; Shown in the example of Fig. 5 B; Register 521～52r is through the SECO of control signal init1, after low value is reduced at the triggering edge of control signal init1, during i=0; Interleaver address in QPP unit 1 example, 500 output registers, 521～52r is interleaver address ∏ (0)～∏ (r-1) forward, or reverse interleaver address ∏ (M-1)～∏ (M-r); During i=r, the interleaver address in QPP unit 1 example, 500 output registers, 521～52r is interleaver address ∏ (r)～∏ (2r-1) forward, or reverse interleaver address ∏ (2M-1)～∏ (2M-r); By that analogy.So QPP unit 1 example 500 is along with sequential, for the first time can and line output interleaver address ∏ (0)～∏ (r-1) forward, or reverse interleaver address ∏ (M-1)～∏ (M-r); For the second time can and line output interleaver address ∏ (r)～∏ (2r-1) forward, or reverse interleaver address ∏ (M-r-1)～∏ (M-2r); By that analogy.

In the example of Fig. 5 A, the action through K is got remainder earlier of all negatives convert value originally between 0～K-1 positive integer, that is input signal all must be positive integer.

Fig. 6 is among Fig. 4, an example schematic of the hardware configuration of QPP unit j, and j >=2, consistent with disclosed some enforcement example.In the example of Fig. 6, suppose that employed of MAP processor equals 2r, the hardware configuration of this QPP unit j can be formed by getting remainder circuit 631～63r after r register 621～62r and r the 2-input-addition, and its input parameter is f ₁M, QPP unit j receives the result of calculation of previous QPP unit j-1, and the parallel r that calculates and export forward the interleaver address be ∏ (x+ (j-1) M), ∏ (x+ (j-1) M+1) ..., ∏ (x+ (j-1) M+ (r-1)); Its parallel r that calculates and export reverse interleaver address is ∏ (jM-x-1), ∏ (jM-x-2) ..., ∏ (jM-x-r), x=0 wherein, r, 2r ..., M-r.Likewise, these forward or reverse interleaver address also can export next QPP unit j+1 to.

Formula according to aforementioned calculation interleaver address; The hardware configuration of QPP unit 1 can be along with input different forward parameter or reverse parameter; And collocation Different control signal designs, and and line output its corresponding one group of forward interleaver address 311 or one group of reverse interleaver address 321.Below lifting two work examples explains.

Fig. 7 A is a work example of the hardware configuration of QPP unit 1, and wherein employed of MAP processor equals 2 ³, consistent with disclosed some enforcement example.QPP unit 1 example 700 of Fig. 7 A can be with getting remainder circuit 701～706 after 711～716,3 registers 721～723 of 6 multiplexers and 6 2-input-additions, and the control signal init1 that arranges in pairs or groups realizes.At first, through triggering control signal init1 (logical value that is init1 is high (high)), multiplexer 711 is with forward parameter ∏ (0) or reverse parameter ∏ (M-1) export register 721 to; This moment, multiplexer 712 also can be with parameter f forward ₂+ f ₁+ 2f ₂* 2 or reverse parameter f ₂-f ₁-2 (M-3) f ₂Get remainder circuit 702 after exporting 2-input-addition to; Multiplexer 713 also can be with parameter f forward ₂+ f ₁Or reverse parameter f ₂-f ₁-2 (M-1) f ₂Get remainder circuit 703 after exporting 2-input-addition to; Multiplexer 714 also can be with parameter f forward ₂+ f ₁+ 2f ₂Or reverse parameter f ₂-f ₁-2 (M-2) f ₂Get remainder circuit 704 after exporting 2-input-addition to.When forward parameter ∏ (0) or reverse parameter ∏ (M-1) output, get remainder circuit 705 after also can exporting 2-input-addition to.

Get all input parameter 2f of remainder circuit 702～704 another input separately after the 2-input-addition ₂* 3.After getting 702 computings of remainder circuit after the 2-input-addition, the modular arithmetic of generation R1 is as a result got remainder circuit 701 after can exporting multiplexer 712 and 2-input-addition respectively to.After getting 703 computings of remainder circuit after the 2-input-addition, the modular arithmetic of generation R2 as a result can export multiplexer 713 and multiplexer 715 respectively to.After getting 703 computings of remainder circuit after the 2-input-addition, the modular arithmetic of generation R2 as a result can export multiplexer 713 and multiplexer 715 respectively to.After getting 704 computings of remainder circuit after the 2-input-addition, the modular arithmetic of generation R3 as a result can export multiplexer 714 and multiplexer 716 respectively to.

When the logical value of init1 when being high, multiplexer 715 is with input parameter 2f ₂* 3 get remainder circuit 705 after exporting 2-input-addition to, and multiplexer 716 is with input parameter 2f ₂* 3 get remainder circuit 706 after exporting 2-input-addition to.After getting 705 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation, i.e. ∏ (1) or reverse parameter ∏ (M-2) get remainder circuit 706 after can exporting register 722 and 2-input-addition respectively to.After getting 706 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation, i.e. ∏ (2) or reverse parameter ∏ (M-3) get remainder circuit 701 after can exporting register 723 and 2-input-addition respectively to.

According to this, when the logical value of init1 when being high, example 700 parallel 3 of calculating of QPP unit 1 forward interleaver address ∏ (0)～∏ (2) or 3 reverse interleaver address ∏ (M-1)～∏ (M-3) can deposit in respectively to 3 registers 721～723.

Then; Low value is reduced at the triggering edge of control signal init1; Multiplexer 711 is got the modular arithmetic result that remainder circuit 701 produces after with 2-input-addition and is exported register 721 to; An input wherein getting remainder circuit 701 after the 2-input-addition is forward parameter ∏ (2) or reverse parameter ∏ (M-3), and another input is to get the modular arithmetic result that remainder circuit 702 produces after the 2-input-addition.And get modular arithmetic result that remainder circuit 702 produces after the 2-input-addition is by a last modular arithmetic R1 and input parameter 2f as a result ₂* 3 results that after modular arithmetic, obtain.After getting 701 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation, i.e. ∏ (3) or reverse parameter ∏ (M-4) except meeting exports register 721 to, get remainder circuit 705 after also can exporting 2-input-addition to.

Similarly, getting modular arithmetic result that remainder circuit 703 produces after the 2-input-addition is by a last modular arithmetic R2 and input parameter 2f as a result ₂* 3 results that after modular arithmetic, obtain, and get remainder circuit 705 after exporting 2-input-addition to by multiplexer 715; Get modular arithmetic result that remainder circuit 704 produces after the 2-input-addition and be by a last modular arithmetic R3 and input parameter 2f as a result ₂* 3 results that after modular arithmetic, obtain, and get remainder circuit 706 after exporting 2-input-addition to by multiplexer 716.

After getting 705 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation, i.e. ∏ (4) or reverse parameter ∏ (M-5) get remainder circuit 706 after can exporting register 722 and 2-input-addition respectively to.After getting 706 computings of remainder circuit after the 2-input-addition, the modular arithmetic result of generation, i.e. ∏ (5) or reverse parameter ∏ (M-6) get remainder circuit 701 after can exporting register 723 and 2-input-addition respectively to.

According to this; Shown in the example of Fig. 7 B; Register 721～723 is through the SECO of control signal init1; After low value was reduced at the triggering edge of control signal init1, for the first time temporary interleaver address was respectively forward interleaver address ∏ (0), ∏ (1), ∏ (2), or reverse interleaver address ∏ (M-1), ∏ (M-2), ∏ (M-3); For the second time temporary interleaver address is respectively forward interleaver address ∏ (3), ∏ (4), ∏ (5), or reverse interleaver address ∏ (M-4), ∏ (M-5), ∏ (M-6); By that analogy.So QPP unit 1 example 700 is along with sequential, for the first time can and line output forward interleaver address ∏ (0), ∏ (1), ∏ (2), or reverse interleaver address ∏ (M-1), ∏ (M-2), ∏ (M-3); For the second time can and line output forward interleaver address ∏ (3), ∏ (4), ∏ (5), or reverse interleaver address ∏ (M-4), ∏ (M-5), ∏ (M-6); By that analogy.

Fig. 8 is another work example of the hardware configuration of QPP unit 1, and wherein employed of MAP processor equals 2 ², consistent with disclosed some enforcement example.In the example of Fig. 8; QPP unit 1 example 800 can be got remainder circuit 804 after remainder circuit 801～803 and a 2-import-subtract each other with getting after 6 multiplexers 811～816, two 821～822,3 2-input-additions of register; And two control signals of arranging in pairs or groups; Be init1 and init2, realize hardware configuration.Wherein, Register 821～822 is through the SECO of control signal init1 and init2; After the triggering edge of control signal init1 is reduced to low value and is triggered control signal init2; For the first time temporary interleaver address is respectively forward interleaver address ∏ (0), ∏ (1), or reverse interleaver address ∏ (M-1), ∏ (M-2); For the second time temporary interleaver address is respectively forward interleaver address ∏ (2), ∏ (3), or reverse interleaver address ∏ (M-3), ∏ (M-4); By that analogy.

Compare with the example of Fig. 7 A; The comparatively different design of 1 example 800 of QPP unit is that the input of forward parameter or reverse parameter has a little difference; And two control signals of arranging in pairs or groups, and adopt simultaneously and get the remainder circuit after the 2-input-addition and 2-gets the hardware configuration that the remainder circuit is realized QPP unit 1 after importing-subtracting each other.Wherein, Trigger control signal init1 earlier; Set the output of multiplexer 811～815; After low value is reduced at the triggering edge of control signal init1,, set the modular arithmetic result who gets remainder circuit 804 after multiplexer 816 is imported 2--subtracted each other and export multiplexer 815 to through triggering control signal init2.

In the design of the hardware configuration of the QPP unit 1 of above-mentioned Fig. 5 A, Fig. 7 A and Fig. 8, to using same root (2 ^r) the MAP processor, the design of the hardware configuration of the QPP unit 1 of Fig. 5 A is simplified the most.Wherein, the hardware configuration of Fig. 5 A design control signal of only arranging in pairs or groups, and use less multiplexer.

If the handled data length of each MAP processor is M, i.e. the width of sliding window, and M is 2 inferior power (power), for example M=2 ⁿ, n least significant bit of the interleaver address that calculates then capable of using (Least Significant Bit, LSB) next address as the memory that the handled data of MAP processor are write.Fig. 9 is an example configuration diagram, explains how QPP interleaver address producing device makes a plurality of MAP processors and many data of line output to memory, and is consistent with disclosed some enforcement example.

With reference to figure 9; QPP interleaver address producing device 300 produce interleaver address ∏ (i), ∏ (i+M), ∏ (i+2M) ..., ∏ (i+ (L-1) M); And output storage is selected (memory selection) information 920 to one multiplexing data devices 910; This memory select information 920 be ∏ (i), ∏ (i+M), ∏ (i+2M) ..., the information of the part position of ∏ (i+ (L-1) M), for example be interleaver address ∏ (i), ∏ (i+M), ∏ (i+2M) ..., the information of the highest effective n position (MSB n bits) of ∏ (i+ (L-1) M).Multiplexing data device 910 receives a plurality of MAP processors, for example MAP processor 1～MAP processor L, and the L of line output data, M=2 ⁿAnd after the memory selection information 920 from QPP interleaver address producing device 300; Will each data of L data be exported to a corresponding storage address 950 of selected memory; These corresponding storage addresss can directly obtain from interleaver address ∏ (i) that QPP interleaver address producing device 300 is calculated, for example by the information of minimum effective n position (LSB n bits) of these interleaver addresses ∏ (i).

With k=40, M=8=2 ³Be example; Figure 10 is an example configuration diagram; Explain how QPP interleaver address producing device 300 makes 5 MAP processors, and for example MAP processor 1～MAP processor 5, and 40 data are all inserted the storage address that QPP interleaver address producing device 300 is produced.In the example of Figure 10, the handled data length M=40/5=8=2 of each MAP processor ³, for example MAP processor 1 deal with data 0～data 7, MAP processor 2 deal with data 8～data 15, MAP processor 3 deal with data 16～data 23, MAP processor 4 deal with data 24～data 31, MAP processor 5 deal with data 32～data 39.

When QPP interleaver address producing device 300 is parallel when calculating interleaver address ∏ (i), ∏ (i+8), ∏ (i+16), ∏ (i+24), ∏ (i+32), export information 1020 to the multiplexing data device 1010 of the highest effective 3 positions of ∏ (i), ∏ (i+8), ∏ (i+16), ∏ (i+24), ∏ (i+32) simultaneously.Multiplexing data device 1010 receives simultaneously and uses root-8 (to equal 2 ³) MAP processor 1～MAP processor 5 and 5 data of line output; And after the highest effective 3 information 1020 of ∏ (i), ∏ (i+8), ∏ (i+16), ∏ (i+24), ∏ (i+40); Export five different memories to these 5 data are parallel; For example memory 0～memory 4; Storage address in, this five block storage is that the highest effective 3 information 1020 by ∏ (i), ∏ (i+8), ∏ (i+16), ∏ (i+24) ∏ (i+32) decides, its storage address that is written into is that the information 1050 by minimum effective 3 (the LSB 3bits) of ∏ (i) decides.That is to say that these five data are parallel to export five different memories to, and these five different memories are stored this five data with the same memory address all respectively.According to this, from i=0 to i=7, MAP processor 1～MAP processor 5 is total to and 40 data of line output, and inserts the storage address of these five different memories.

In other words, work as M=2 ^rThe time, shown in the example of the QPP interleaver address producing device of Figure 11, among the interleaver address ∏ (i) that QPP receipt unit 1 calculates, its minimum effective n position provides to the address of all memories and uses; And each QPP unit j, j=1 ..., L, among the interleaver address ∏ (i+jM) that calculates, its highest effective n position provides to a multiplexing data device, and for example the multiplexing data device of a MAP processor is chosen a memory.N can be considered the figure place of the address bus (address buses) of memory, that is to say that each memory has 2 ⁿIndividual storage address.This L the interleaver address that calculate the QPP unit, i.e. ∏ (i), ∏ (i+M), ..., ∏ (i+ (L-1) M), the information of the highest effective n position can correspond to L MAP processor, choose its deal with data the memory that will write.

In the example chart of Figure 12, with k=40, M=2 ³, f ₁=3, f ₂=10 is example, and the interleaver address of calculating through QPP interleaver address producing device is described, how to determine storage address, consistent with disclosed some enforcement example.Suppose ∏ (0)=0, L=K/M=5, in the QPP interleaver address producing device 300, when i=0,1～QPP unit, QPP unit 5 is calculated the interleaver address respectively:

∏(0)＝0＝(000000) ₂，∏(8)＝24＝(011000) ₂，

∏(16)＝8＝(001000) ₂，∏(24)＝32＝(100000) ₂，

∏(32)＝16＝(010000) ₂。

Because the highest effective 3 of ∏ (0), ∏ (8), ∏ (16), ∏ (24), ∏ (32) are respectively 000,011,001,100,010; And minimum effective 3 of ∏ (0) is 000; So 5 MAP processors; MAP processor 1～MAP processor 5; Five data of the first time and line output, promptly data 0, data 8, data 16, data 24, data 32 are written into the address 0 of memory 0, the address 0 of memory 3, the address 0 of memory 1, the address 0 of memory 4, the address 0 of memory 2 respectively.

When i=1,1～QPP unit, QPP unit 5 is calculated the interleaver address respectively:

∏(1)＝13＝(001101) ₂，∏(9)＝37＝(100101) ₂，

∏(17)＝21＝(010101) ₂，∏(25)＝5＝(000101) ₂，

∏(33)＝29＝(011101) ₂。

Because the highest effective 3 of ∏ (1), ∏ (9), ∏ (17), ∏ (25), ∏ (33) are respectively 001,100,010,000,011; And minimum effective 3 of ∏ (1) is 101; So five data of 5 second time of MAP processor 1～MAP processor and line output; Be data 1, data 9, data 17, data 25, data 33, be written into the address 5 of memory 1, the address 5 of memory 4, the address 5 of memory 2, the address 5 of memory 0, the address 5 of memory 3 respectively.

The rest may be inferred.So, when i=7, ∏ (7)=31=(011111) ₂, MAP processor 1～MAP processor 5 five data last and line output are calculated the highest effective 3 information of interleaver address according to 1～QPP unit, QPP unit 5, are written into the address 7 of five memories respectively.In this example, each memory has 8 addresses, and promptly 0～address, address 7, can be written into 8 data by the output of MAP processor.

From Figure 12 example chart, can find out; (this example is 8 to the stroke count M of the specific deal with data of each MAP processor; Be the width of sliding window of the information output of list entries); On calculating, need not use complicated circuitry, like multiplier, and MAP processor 1～MAP processor 5 is written into the same address of memory 0～memory 4 with 5 data of once parallel output.

Also can peep knowledge from above-mentioned example, if employed-R of MAP processor (=2 ^r), then r interleaver address going out of each QPP unit j parallel computation promptly corresponds to employed-R of each MAP processor (=2 ^r) framework.In addition, setting the handled data length of each MAP processor is M=2 ⁿ, the information of minimum effective n position of the interleaver address that then lucky QPP capable of using unit 1 is calculated is come the address as write memory.

Moreover as previously mentioned, to the different root of MAP processor, QPP interleaver address producing device 300 also can produce forward corresponding or reverse interleaver address, come corresponding MAP processor forward or the calculating of inverse path value, like the example explanation of Figure 13.(Soff-input Soft-output, SISO) the 1310 li some MAP in unit read L when soft input and soft output _e(Z _{K, 1}), I _a(x _k) and L _e(x _k) forward input signal or reverse input signal the time, QPP interleaver address producing device 300 can produce forward or reverse interleaver address ∏ (i) gives different memories to read corresponding L _e(Z _K, ₁), I _a(x _k) and L _e(x _k), as the input signal of this MAP.When MAP begins to export I _e(x _k) time, QPP interleaver address producing device 300 also can produce corresponding interleaver address, supplies the result of calculation of this MAP to write in a certain block storage 1320, and wherein, M representes the address size of each block storage.

Accept above-mentionedly, Figure 14 is an exemplary flowchart of QPP interleaver address generating method, with disclosed some to implement example consistent.With reference to Figure 14, according to QPP function ∏ (i)=(f ₁I+f ₂i ²) mod k, import a plurality of configurable parameters, shown in step 1410.In the step 1420; Calculate and export a plurality of interleavers address through L QPP unit, each QPP unit j of this L QPP unit, be all a parallel computing unit and and its corresponding one group of interleaver address of line output; Wherein ∏ (i) is i the interleaving address that the method produces, f ₁With f ₂Be the QPP coefficient, k is the information area block length of a list entries, so, lets the information of this list entries insert the address of a plurality of corresponding memories, 0≤i≤k-1,1≤j≤L.The information of this list entries can be passed through L sliding window and line output, and M is the width of each sliding window of this L sliding window.One group of interleaver address of each QPP unit j and line output can be one group of forward interleaver address or one group of reverse interleaver address.

In the step 1420, each QPP unit j can be according to aforementioned formula (1)～(5), parallelly calculate its corresponding one group of forward interleaver address or one group of reverse interleaver address, no longer explanation.

Work as M=2 ⁿThe time; Shown in the example of aforementioned Figure 11, Figure 12, among the interleaver address ∏ (i) that calculate QPP unit 1, can utilize its minimum effective n position is to use as the address of all memories; And each QPP unit j; 1≤j≤L, the highest effective n position of the interleaver address ∏ that calculates (i+ (j-1) M) then can offer a multiplexing data device, comes from a plurality of memories, to select a memory.The memory of being selected through the highest effective n position, and specified address, minimum effective n position, each of list entries information just can be written in the corresponding storage address.

In sum; Enforcement example of the present disclosure can provide a kind of QPP interleaver address producing device and method; Can directly calculate forward interleaver address or reverse interleaver address through several QPP unit, but the corresponding one group of result of calculation of interleaver address or one group of reverse interleaver address forward of each QPP unit parallel computation and output.For root-R (=2 ^r) the MAP processor, also can each output of parallel interleaving address originally be expanded into parallel r interleaver address again and export.To the different root-R of MAP processor, also can produce corresponding forward interleaver address or reverse interleaver address, come corresponding MAP processor forward or the calculating of inverse path value.This QPP interleaver address producing device needn't be changed ifq circuit, can be with original weaving length K, and configuration becomes the weaving length that K/M length is all M.The circuit of low complex degree is used in the design of enforcement example of the present disclosure; Also need not memory span and store the interleaver address; Can significantly lower hardware area and the computational speed that promotes the interleaver address, can be applicable in mobile communication (like 3GPP LTE, the LTE-A) system.

Yet the above is merely enforcement example of the present disclosure, when not limiting the scope that the present invention implements according to this.Promptly the equalization done of claim of the present invention changes and modifies generally, all should still belong to the scope that patent of the present invention contains.

Claims

1. A second-order rearrangement polynomial QPP interleaver address generating device, the device comprising:

L QPP units, expressed as QPP unit 1 to QPP unit L, L≥2;

The device is based on a QPP function ∏(i)=(f ₁ i+f ₂ i ² ) mod k, f ₁ and f ₂ are QPP coefficients, 0≤i≤k-1, k is an information block of an input sequence Length, receiving several configurable parameters and using the L QPP units to calculate and output a plurality of interleaver addresses, wherein, Π(i) is also an i-th interleaver address generated by the device, and each QPP unit j, 1≤j≤L, all are a parallel computing unit and output a corresponding set of interleaver addresses in parallel.

2. The address generating device as claimed in claim 1, wherein the group interleaver address is a group of forward interleaver addresses or a group of reverse interleaver addresses, when the group interleaver address is a forward interleaver address, the The group of interleaver addresses output by QPP unit j in parallel are ∏(i+(j-1)M), ∏(i+(j-1)M+1),..., ∏(i+(j-1)M+( r-1)), when the group interleaver address is a reverse interleaver address, the group interleaver address output by the QPP unit j in parallel is ∏(jM-i-1), ∏(jM-i-2), ..., Π(jM-i-r), M=k/L, M is a positive integer, 1≤r≤k.

3. The address generating device as claimed in claim 2, wherein M is equal to 2 ⁿ , and n is a positive integer.

4. The address generating device as claimed in claim 2, wherein the hardware structure of the QPP unit 1 is composed of r+1 multiplexers, r registers, and 2r 2-input-additional remainder circuits, and collocation at least one control signal.

5. The address generating device as claimed in claim 2, wherein for 2≤j≤L, the hardware structure of each QPP unit j is made up of r registers and r 2-input-adding and taking remainder circuits .

6. The address generating device as claimed in claim 3 , the device outputs the corresponding interleaver address for logarithm-corresponding to the parallel decoder architecture of the different roots of the MAP processor, to correspond to each of the MAP processors of the different roots Calculation of forward or reverse path values of a MAP processor.

7. The address generating device according to claim 1, which is an address generating device for an interleaver or a deinterleaver.

8. The address generating device according to claim 1, wherein for j≥2, each QPP unit j receives the calculation result of QPP unit j-1 respectively.

9. The address generating device as claimed in claim 1, wherein the several configurable parameters are {k, (f ₁ +f ₂ ) mod k, 2f ₂ mod k, f1M mod k, Π(0)} and { k, f ₂ -f ₁ -2(M-1)f ₂ mod k, 2f ₂ mod k, f ₁ M mod k, ∏(M-1)} one of a set of configurable parameters.

10. A second-order rearrangement polynomial QPP interleaver address generation method, applied to a codec on a communication system, the method comprising:

Input multiple configurable parameters according to a QPP function ∏(i)=(f ₁ i+f ₂ i ² ) mod k; and

Calculate and output multiple interleaver addresses through L QPP units, each QPP unit j of the L QPP units, 1≤j≤L, is a parallel calculation unit and outputs its corresponding group of interleavers in parallel address;

Wherein ∏(i) is an i-th interleaving address produced by the method, f ₁ and f ₂ are QPP coefficients, k is the information block length of an input sequence, 0≤i≤k-1, mod is a modulus operation, In this way, the information of the input sequence is filled into a plurality of corresponding memory addresses.

11. The address generating method as claimed in claim 10, wherein the group interleaver address is a group of forward interleaver addresses or a group of reverse interleaver addresses, when the group interleaver address is a forward interleaver address, the The group of interleaver addresses output by QPP unit j in parallel are ∏(i+(j-1)M), ∏(i+(j-1)M+1),..., ∏(i+(j-1)M+( r-1)), when the group interleaver address is a reverse interleaver address, the group interleaver address output by the QPP unit j in parallel is ∏(jM-i-1), ∏(jM-i-2), ..., Π(jM-i-r), M=k/L, M is a positive integer, 1≤r≤k.

12. The address generating method as claimed in claim 11, wherein M is equal to 2 ⁿ , and n is a positive integer.

13. The address generating method according to claim 11, wherein the least significant n bits of the i-th interleaver address Π(i) are addresses filled into L memories as a plurality of pieces of data of the input sequence.

14. The address generation method as claimed in claim 12, wherein the most significant n bits of the i-th interleaver address Π(i) are provided to a data matrix multiplexer to select L corresponding memories.

15. The address generation method according to claim 11, wherein the plurality of configurable parameters are {k, (f ₁ +f ₂ ) mod k, 2f ₂ mod k, f ₁ M mod k, ∏(0)} One set of configurable parameters with {k, f ₂ -f ₁ -2(M-1)f ₂ mod k, 2f ₂ mod k, f ₁ M mod k, ∏(M-1)}.

16. The address generating method as claimed in claim 11, wherein the information of the input sequence is output in parallel through L sliding windows, and M is the width of each sliding window of the L sliding windows.