CN101488823A - Reed-Muller decoding method and decoder using the method - Google Patents

Abstract

Provided is a Reed-Muller decoding method comprising: receiving an inputted non-quantification transmitting format combined indication TFCI symbol and generating a basic coding sequence; respectively performing one interweave for the inputted TFCI symbol and the generated basic coding sequence; generating a first data matrix composed of data vectors and obtaining a first related matrix; generating a second data matrix composed of data vectors and performing a Hadamard transformation for the data vectors in the second data matrix in turn to obtain a second related matrix; determining decoding parameters by utilizing the first related matrix and the second related matrix and decoding to output binary decoding results. The invention enables the FHT in the decoder to be decreased from 32 input to 8 input according to the characteristic of the M0-M4 in the TFCI basic coding sequence by introducing a secondary interweave in the decoder, thereby reducing the implementing complicated degree of the decoder at the expense of small performance loss.

Description

Reed-Muller interpretation method and use the decoder of this method

Technical field

The present invention relates to the transformat combination indication detection technique in the 3GPP communication system, more specifically, relate to a kind of decoder that is applicable to the 3GPP Reed-Muller interpretation method of non-quantification input and uses this method.

Background technology

The present invention mainly inquires in the 3GPP communication system, based on the interpretation method of transformat combination indication TFCI under the non-compact model.

In 3GPP communication system physical layer protocol, the TFCI under the non-compact model adopts (32,10) subcode of second order Reed-Muller sign indicating number to encode (referring to 3GPP TS 25.212, v7.4.0.).

The Reed-Muller sign indicating number is a kind of linear block codes, and the coded system of its (32,10) subcode as shown in Figure 1.The output code word of this coded system is 32 bits, is the linear combination as 10 listed basic coding sequences of table 1.

The basic coding sequence of table 1 (32,10) TFCI coding

? i	M i，0	M i，1	M i，2	M i，3	M i，4	M i，5	M i，6	M i，7	M i，8	M i，9
											0	1	0	0	0	0	1	0	0	0	0
1	0	1	0	0	0	1	1	0	0	0
											2	1	1	0	0	0	1	0	0	0	1
3	0	0	1	0	0	1	1	0	1	1
											4	1	0	1	0	0	1	0	0	0	1
5	0	1	1	0	0	1	0	0	1	0
											6	1	1	1	0	0	1	0	1	0	0
7	0	0	0	1	0	1	0	1	1	0
											8	1	0	0	1	0	1	1	1	1	0
9	0	1	0	1	0	1	1	0	1	1
											10	1	1	0	1	0	1	0	0	1	1
11	0	0	1	1	0	1	0	1	1	0
											12	1	0	1	1	0	1	0	1	0	1
13	0	1	1	1	0	1	1	0	0	1
											14	1	1	1	1	0	1	1	1	1	1
15	1	0	0	0	1	1	1	1	0	0
											16	0	1	0	0	1	1	1	1	0	1
17	1	1	0	0	1	1	1	0	1	0
											18	0	0	1	0	1	1	0	1	1	1
19	1	0	1	0	1	1	0	1	0	1
											20	0	1	1	0	1	1	0	0	1	1
21	1	1	1	0	1	1	0	1	1	1
											22	0	0	0	1	1	1	0	1	0	0
23	1	0	0	1	1	1	1	1	0	1
											24	0	1	0	1	1	1	1	0	1	0
25	1	1	0	1	1	1	1	0	0	1
											26	0	0	1	1	1	1	0	0	1	0
27	1	0	1	1	1	1	1	1	0	0
											28	0	1	1	1	1	1	1	1	1	0
29	1	1	1	1	1	1	1	1	1	1
											30	0	0	0	0	0	1	0	0	0	0
31	0	0	0	0	1	1	1	0	0	0

With a ₀, a ₁, a ₂, a ₃, a ₄, a ₅, a ₆, a ₇, a ₈, a ₉The input bit of presentation code device, then TFCI output code word b _iObtain by following formula:

$b_i=\underset{n=0}{\overset{9}{\mathrm{\&Sigma;}}}(a_n\&times;M_{i,n})\mathrm{<figure-callout\; id="2"\; label="mod"\; filenames="A200810002662E00142.png,A200810002662E00151.png"\; state="\{\{state\}\}">mod</figure-callout>}2,i\&Element;\left[\mathrm{0,31}\right].$

It should be noted that under the non-compact model of 3GPP the right and wrong rule second order Reed-Muller method that the TFCI coding adopts.Basic sequence M promptly encodes ₀～M ₄Produce coding basic sequence M by the Walsh code generator after interweaving ₆～M ₉Produce by the mask generator after interweaving.

Unipolarity coded-bit by generating with upper type 0, and 1}, {+1 ,-1} sends into channel again through being mapped as ambipolar coded-bit after the simple BPSK modulation (f:y=1-2x).

When the channel output valve being carried out TFCI decoding, two kinds of decoder input modes are arranged generally:

Non-quantification input: the sampled signal that is about to channel output is directly imported decoder;

Quantize input: promptly earlier the sampled signal of channel output is adjudicated, be judged to 1 greater than 0, otherwise be judged to-1, obtain ambipolar reception code word, import decoder again and decipher.

The present invention is for being applicable to Non-quantification inputThe TFCI decoder.

In the research about 3GPP communication system Reed-Muller decoder at present, decorrelation is a basic skills step by step.Principle is simple, method intuitively is the advantage of this method, but computational complexity is big, decoding time length is the subject matter that is faced when this method is put to use.

At list of references " Reed-Muller coding in 3GPP " (Wu Zhan-ji, Wu Wei-ling, Reed-Muller coding in 3GPP, ACTA ELECTORNICA SINICA, Vol.33, Jan.2005.) in, the Reed-Muller that adopts 32 input fast hadamard transform FHT to carry out among the 3GPP deciphers.FHT is used to calculate with the reception code word of Walsh sign indicating number spread spectrum and the correlation of different Walsh sign indicating numbers based on butterfly computation.Fig. 2 and Fig. 3 have represented the basic operation principle of FHT and the core algorithm of list of references 2 respectively.Have benefited from the advantage that the FHT signal parallel is handled, this method can significantly shorten decoding time, but 32 input FHT still mean bigger computational complexity and higher hardware implementation cost.

In sum, in the 3GPP communication system, Reed-Muller decoder efficient, low complex degree still is to need the further problem of solution.In the research about 3GPP communication system Reed-Muller decoder at present, decorrelation is a basic skills step by step.But computational complexity is big, decoding time length is the subject matter that is faced when this method is put to use.Comparatively speaking, can significantly shorten decoding time, but 32 input FHT still mean bigger computational complexity and higher hardware implementation cost based on 32 interpretation methods of importing FHT.

Summary of the invention

For addressing the above problem, according to an aspect of the present invention, provide a kind of Reed-Muller interpretation method, comprise step:

A) receive the non-quantification transmitting format combined indication TFCI symbol of input, and generate the basic coding sequence;

B) the TFCI symbol of input and the basic coding sequence of generation are once interweaved respectively;

C) utilize TFCI symbol that has interweaved and the basic coding sequence that has interweaved, generate first data matrix that constitutes by data vector, and the data vector in first data matrix is carried out Hadamard transform successively, obtain first correlation matrix;

D) the TFCI symbol of input and the basic coding sequence of generation being carried out secondary respectively interweaves, utilize TFCI symbol that has interweaved and the basic coding sequence that has interweaved, second data matrix that generation is made of data vector, and the data vector in second data matrix carried out Hadamard transform successively, obtain second correlation matrix;

E) utilize first correlation matrix and second correlation matrix to determine decoding parameters, and carry out decoding, with output binary decoding result.

According to a further aspect in the invention, proposed a kind of Reed-Muller decoder, having comprised:

The code word input module, the quantification transmitting format combined that receives input is indicated the TFCI symbol;

The coded sequence generation module generates the basic coding sequence;

An interleaving block interweaves respectively to the TFCI symbol of input and the basic coding sequence of generation;

The secondary interleaving block carries out secondary respectively to the TFCI symbol of input and the basic coding sequence of generation and interweaves;

Decoded vector generates and modular converter, utilizes interleaving block and the TFCI symbol that has interweaved of secondary interleaving block output and the basic coding sequence that has interweaved, generates first data matrix and second data matrix that are made of data vector respectively;

The Hadamard transform module is carried out Hadamard transform to first data matrix and second data matrix respectively, obtains first correlation matrix and second correlation matrix; And

Judging module utilizes first correlation matrix and second correlation matrix to determine decoding parameters, and carries out decoding, with output binary decoding result.

The present invention is according to M in the TFCI basic coding sequence ₀～M ₄Characteristics, interweave by in decoder, introducing secondary, make the FHT in the decoder reduce to 8 inputs, thereby be cost with less performance loss by 32 inputs, significantly reduced the implementation complexity of decoder.

Description of drawings

The schematic diagram of the Reed-Muller cataloged procedure of Fig. 1 TFCI information bit

The schematic diagram of Fig. 2 16 input FHT butterfly computation basic principles

Fig. 3 is based on the Reed-Muller decoder rudimentary algorithm schematic diagram of 32 input FHT

Fig. 4 is according to the flow chart of interpretation method of the present invention

Fig. 5 is according to the block diagram of decoder of the present invention

Fig. 6 compares schematic diagram according to frame error rate (FER) performance of the embodiment of the invention

Embodiment

The present invention is according to M in the TFCI basic coding sequence ₀～M ₄Characteristics, interweave by in decoder, introducing secondary, make the FHT in the decoder reduce to 8 inputs, thereby be cost with less performance loss by 32 inputs, significantly reduced the implementation complexity of decoder.

Interpretation method according to the embodiment of the invention is as follows:

1. the TFCI symbol of establishing input is b _i, i ∈ [0,31], wherein b _iBe the non-quantification input of TFCI.

2. generate basic coding sequence M ₆～M ₉, wherein

M ₆：0101_0000_1100_0111_1100_0001_1101_1101，

M ₇：0000_0011_1001_1011_1011_0111_0001_1100，

M ₈：0001_0101_1111_0010_0110_1100_1010_1100，

M ₉：0011_1000_0110_1110_1011_1101_0100_0100。

To the input TFCI symbol and basic coding sequence M ₆～M ₉Interweave.In interleaving process, the data of establishing input are m ₀, m ₁..., m ₁₄, m ₁₅..., m ₂₉, m ₃₀, m ₃₁, then dateout is m ₃₀, m ₀, m ₁..., m ₁₄, m ₃₁, m ₁₅..., m ₂₉

4. generating solution code vector.If $M*=\left[\begin{array}{c}{M}_6^{*}\\ {\mathrm{<figure-callout\; id="7"\; label="M"\; filenames="A200810002662E00181.png"\; state="\{\{state\}\}">M</figure-callout>}}_7^{*}\\ {\mathrm{<figure-callout\; id="8"\; label="M"\; filenames="A200810002662E00161.png,A200810002662E00181.png"\; state="\{\{state\}\}">M</figure-callout>}}_8^{*}\\ M_9^{*}\end{array}\right],$ Wherein

Be the basic coding sequence after interweaving, i ∈ [6,9].Decoded vector V then _i, i ∈ [0,15] generates according to following formula:

V _i＝[c ₀?c ₁?c ₂?c ₃]×M ^*，

Wherein i is expressed as the binary number c of 4 bits ₀c ₁c ₂c ₃

Utilize decoded vector, can remove coded sequence M ₆～M ₉Influence, obtain a in the decode results ₆, a ₇, a ₈, a ₉

5. all bits in the decoded vector are converted to signed number according to following rule:

0→+1，1→-1。

6. descend column operations:

$T_{i,j}=b_j^{*}\&times;V_{i,j}^{*},i\&Element;\left[\mathrm{0,15}\right],j\&Element;\left[\mathrm{0,31}\right].$

Wherein

Be j symbol of the back TFCI code word that interweaves,

Be decoded vector V _iIn j symbol.

7. recomputate T according to following rule _{I, j}:

$T_{i,0}^{*}=T_{i,0}\&times;T_{i,8}\text{\&times;}{T}_{i,16}\&times;T_{i,24},$

$T_{i,1}^{*}=T_{i,1}\&times;T_{i,9}\text{\&times;}{T}_{i,17}\&times;T_{i,25},$

……

$T_{i,7}^{*}=T_{i,7}\&times;T_{i,15}\text{\&times;}{T}_{i,23}\&times;T_{i,31}.$

Utilize above-mentioned steps 4-7, can obtain preceding 4 in the decode results.

8. carry out 16 times 8 input FHT computing.In each FHT computing, be input as 1 * 8 vector

Be output as h _{I, j}, j ∈ [0,7].All 16 FHT computings generate one 16 * 8 correlation matrix after finishing, and are labeled as H ⁽¹⁾

9. return step 3.As the TFCI of all inputs symbol and basic coding sequence M ₆～M ₉Interweave finish after, carry out following secondary interlace operation: in secondary interweaves, establish the input data be d ₀, d ₁..., d ₁₄, d ₁₅.., d ₂₉, d ₃₀, d ₃₁, then the interleaver dateout is: d ₀, d ₁₆, d ₈, d ₂₄, d ₄, d ₂₀, d ₁₂, d ₂₈, d ₂, d ₁₈, d ₁₀, d ₂₆, d ₆, d ₂₂, d ₁₄, d ₃₀,

d ₁，d ₁₇，d ₉，d ₂₅，d ₅，d ₂₁，d ₁₃，d ₂₉，d ₃，d ₁₉，d ₁₁，d ₂₇，d ₇，d ₂₃，d ₁₅，d ₃₁.

10. the correlation matrix that repeating step 4-8, and flag F HT generates is H ⁽²⁾, can access a thus ₄And a ₅

11. carry out data decision:

$C_{x,y}=\arg \max \left|h_{i,j}^{\left(1\right)}\right|,$ ? $C_{m,n}=\arg \max \left|h_{i,j}^{\left(2\right)}\right|,$ ? $h_{i,j}^{\left(1\right)}\&Element;H^{\left(1\right)},$ ? $h_{i,j}^{\left(2\right)}\&Element;H^{\left(2\right)},$ ?i∈[0，15]，j∈[0，7]，

X is expressed as the binary number of 4 bits, is a after the decoding ₆, a ₇, a ₈, a ₉

The binary number that y is expressed as 3 bits is a after the decoding ₂, a ₁, a ₀

The binary number that (n-4) is expressed as 2 bits is a after the decoding ₃, a ₄

If C _{X, y}0, a then ₅=0, otherwise a ₅=1.

12. a that judgement obtains ₀, a ₁, a ₂, a ₃, a ₄, a ₅, a ₆, a ₇, a ₈, a ₉Be decoder output.

According to the structure of the decoder of the embodiment of the invention as shown in Figure 4.

According to of the present invention, a kind of 3GPP Reed-Muller low complex degree decoder that is applicable to non-quantification input can comprise:

Code word input module 501: this module is finished the input that TFCI receives code word.If the TFCI symbol of input is b _i, i ∈ [0,31], wherein b _iBe the non-quantification input of TFCI.

Coded sequence generation module 502: this module generates basic coding sequence M ₆～M ₉, wherein

M ₆：0101_0000_1100_0111_1100_0001_1101_1101，

M ₇：0000_0011_1001_1011_1011_0111_0001_1100，

M ₈：0001_0101_1111_0010_0110_1100_1010_1100，

M ₉：0011_1000_0110_1110_1011_1101_0100_0100.

An interleaving block 503: this module is to the TFCI symbol and the basic coding sequence M of input ₆～M ₉Once interweave.

In this module, the data of establishing input are a ₀, a ₁..., a ₁₄, a ₁₅..., a ₂₉, a ₃₀, a ₃₁, then dateout is a ₃₀, a ₀, a ₁..., a ₁₄, a ₃₁, a ₁₅.., a ₂₉.

Secondary interleaving block 504: this module is to the TFCI symbol and the basic coding sequence M of input ₆～M ₉Carrying out secondary interweaves.

In this module, establishing the input data is d ₀, d ₁..., d ₁₄, d ₁₅..., d ₂₉, d ₃₀, d ₃₁, then dateout is:

d ₀，d ₁₆，d ₈，d ₂₄，d ₄，d ₂₀，d ₁₂，d ₂₈，d ₂，d ₁₈，d ₁₀，d ₂₆，d ₆，d ₂₂，d ₁₄，d ₃₀，

d ₁，d ₁₇，d ₉，d ₂₅，d ₅，d ₂₁，d ₁₃，d ₂₉，d ₃，d ₁₉，d ₁₁，d ₂₇，d ₇，d ₂₃，d ₁₅，d ₃₁.

Decoded vector generates and bipolarity modular converter 505: this module generating solution code vector.If

$M*=\left[\begin{array}{c}{\mathrm{<figure-callout\; id="6"\; label="M"\; filenames="A200810002662E00181.png"\; state="\{\{state\}\}">M</figure-callout>}}_6^{*}\\ {\mathrm{<figure-callout\; id="7"\; label="M"\; filenames="A200810002662E00181.png"\; state="\{\{state\}\}">M</figure-callout>}}_7^{*}\\ {\mathrm{<figure-callout\; id="8"\; label="M"\; filenames="A200810002662E00161.png,A200810002662E00181.png"\; state="\{\{state\}\}">M</figure-callout>}}_8^{*}\\ M_9^{*}\end{array}\right],$ Wherein

Be the basic coding sequence after interweaving, i ∈ [6,9].Then decoding

Vector V _i, i ∈ [0,15] generates according to following formula:

V _i＝[c ₀?c ₁?c ₂?c ₃]×M ^*，

V wherein _iSubscript i is expressed as the binary number c of 4 bits ₀c ₁c ₂c ₃

This module is converted to signed number with all bits in the decoded vector according to following rule simultaneously:

0→+1，1→-1。

FHT input conversion and FHT computing module 506: this module is carried out following computing:

? $T_{i,j}=b_j^{*}\&times;V_{i,j}^{*},$ I ∈ [0,15], j ∈ [0,31]. wherein

Be j symbol of the back TFCI code word that interweaves,

Be j symbol among the decoded vector Vi.

Recomputate T according to following rule _{I, j}:

$T_{i,0}^{*}=T_{i,0}\&times;T_{i,8}\text{\&times;}{T}_{i,16}\&times;T_{i,24},$

$T_{i,1}^{*}=T_{i,1}\&times;T_{i,9}\text{\&times;}{T}_{i,17}\&times;T_{i,25},$

……

$T_{i,7}^{*}=T_{i,7}\&times;T_{i,15}\text{\&times;}{T}_{i,23}\&times;T_{i,31}.$

Carry out 16 times 8 input FHT computing.In each FHT computing, be input as 1 * 8 vector T _i ^*, be output as h _{I, j}, j ∈ [0,7].All FHT computings will generate one 16 * 8 correlation matrix after finishing.If two correlation matrixes that decoder generated are respectively H ⁽¹⁾With H ⁽²⁾

Data decision module 507: this module is carried out data decision:

$C_{x,y}=\arg \max \left|h_{i,j}^{\left(1\right)}\right|,$ $C_{m,n}=\arg \max \left|h_{i,j}^{\left(2\right)}\right|,$ $h_{i,j}^{\left(1\right)}\&Element;H^{\left(1\right)},$ $h_{i,j}^{\left(2\right)}\&Element;H^{\left(2\right)},$ i∈[0，15]，j∈[0，7]，

The binary number that x is expressed as 4 bits is a after the decoding ₆, a ₇, a ₈, a ₉

The binary number that y is expressed as 3 bits is a after the decoding ₂, a ₁, a ₀

(n-4) binary number that is expressed as 2 bits is a after the decoding ₃, a ₄

If C _{X, y}0, a then ₅=0, otherwise a ₅=1.

The a that judgement obtains ₀, a ₁, a ₂, a ₃, a ₄, a ₅, a ₆, a ₇, a ₈, a ₉Be decoder output.

Present embodiment adopts the single-shot list to receive the 3GPP communication system that antenna is formed.Channel is a systems of quasi-static flat Rayleigh fading channels, does not consider Doppler frequency shift.Decoder is input as the non-quantification input of TFCI.

In this embodiment, carried out emulation to decoder that the present invention carries and based on the 32 TFCI decoding performances of decoder under non-compact model of importing FHT respectively.Simulation result as shown in Figure 6.Abscissa is E among the figure _b/ N ₀Value, ordinate is system's frame error rate (FER) index.

According to simulation result, compare interpretation method based on 32 input FHT, institute of the present invention extracting method has maximum FER performance losss near 0.5dB.Consider the implementation complexity and the hardware implementation cost of system that the present invention puies forward, than present existing detection method, institute of the present invention extracting method be put to aspect the practical application more superior.

Claims (10)

1. Reed-Muller interpretation method comprises step:

A) the non-quantification transmitting format combined that receives input is indicated the TFCI symbol, generates the basic coding sequence;

B) the TFCI symbol of input and the basic coding sequence of generation are once interweaved respectively;

C) utilize TFCI symbol that has interweaved and the basic coding sequence that has interweaved, generate first data matrix that constitutes by data vector, and the data vector in first data matrix is carried out Hadamard transform successively, obtain first correlation matrix;

D) the TFCI symbol of input and the basic coding sequence of generation being carried out secondary respectively interweaves, utilize TFCI symbol that has interweaved and the basic coding sequence that has interweaved, second data matrix that generation is made of data vector, and the data vector in second data matrix carried out Hadamard transform successively, obtain second correlation matrix;

E) utilize first correlation matrix and second correlation matrix to determine decoding parameters, and carry out decoding, with output binary decoding result.

2. method according to claim 1, wherein, described basic coding sequence comprises four sequences, in step c), utilizes the basic coding sequence generating solution code vector that interweaved, is used for generating last four of decode results numerical digit.

3. method according to claim 1, wherein, described decoding parameters comprises four, when deciphering, first parameter is expressed as the binary number of 4 bits, as back 4 of decode results, second parameter is expressed as the binary number of 3 bits, as preceding 3 of decode results, tri-consult volume and the 4th parameter are expressed as the binary number of 2 bits and 1 bit respectively, as sandwich digit.

4. method according to claim 3, wherein, described first and second parameters are peaked location dependent informations of element in first correlation matrix, described tri-consult volume is the peaked location dependent information of element in second correlation matrix, and the 4th parameter is the peaked relevant information of element in first correlation matrix.

5. method according to claim 1 and 2, wherein, utilizing once interweaves obtains the first of numerical digit in the decode results, utilizes secondary to interweave to obtain the second portion of numerical digit in the decode results.

6. Reed-Muller decoder comprises:

Code word input module (501), the quantification transmitting format combined that receives input is indicated the TFCI symbol;

Coded sequence generation module (502) generates the basic coding sequence;

An interleaving block (503) interweaves respectively to the TFCI symbol of input and the basic coding sequence of generation;

Secondary interleaving block (505) carries out secondary respectively to the TFCI symbol of input and the basic coding sequence of generation and interweaves;

Decoded vector generates and modular converter (504), utilizes interleaving block and the TFCI symbol that has interweaved of secondary interleaving block output and the basic coding sequence that has interweaved, generates first data matrix and second data matrix that are made of data vector respectively;

Hadamard transform module (506) is carried out Hadamard transform to first data matrix and second data matrix respectively, obtains first correlation matrix and second correlation matrix; And

Judging module (507) utilizes first correlation matrix and second correlation matrix to determine decoding parameters, and carries out decoding, with output binary decoding result.

7. decoder according to claim 6, wherein, described basic coding sequence comprises four sequences, in decoded vector generation and modular converter (504), utilize the basic coding sequence generating solution code vector that interweaved, be used for generating last four of decode results numerical digit.

8. decoder according to claim 6, wherein, described decoding parameters comprises four, when deciphering, first parameter is expressed as the binary number of 4 bits, as back 4 of decode results, second parameter is expressed as the binary number of 3 bits, as preceding 3 of decode results, tri-consult volume and the 4th parameter are expressed as the binary number of 2 bits and 1 bit respectively, as sandwich digit.

9. decoder according to claim 8, wherein, described first and second parameters are peaked location dependent informations of element in first correlation matrix, described tri-consult volume is the peaked location dependent information of element in second correlation matrix, and the 4th parameter is the peaked relevant information of element in first correlation matrix.

10. according to claim 6 or 7 described decoders, wherein, utilizing once interweaves obtains the first of numerical digit in the decode results, utilizes secondary to interweave to obtain the second portion of numerical digit in the decode results.

Images