CN101807928B

CN101807928B - Recording controller and parity check code decoder

Info

Publication number: CN101807928B
Application number: CN 200910006705
Authority: CN
Inventors: 王承康; 洪佳君
Original assignee: Realtek Semiconductor Corp
Current assignee: Realtek Semiconductor Corp
Priority date: 2009-02-13
Filing date: 2009-02-13
Publication date: 2013-06-05
Anticipated expiration: 2029-02-13
Also published as: CN101807928A

Abstract

A parity-check code decoder, comprising: a verification device, which multiplies the matrix with N rows by N-bit nodes to obtain a plurality of check nodes; a reliability generating device for generating a reliability index for each bit node according to a channel; a reliability updating device, which makes the allele node and the check nodes iterate each other based on the reliability index to update N exchange results corresponding to the N rows respectively; and a recording controller, comprising: a separator for dividing the matrix into at least one row group according to the row weight and outputting N characteristic signals respectively corresponding to the switching results; a quantization decision device for deciding a shift signal for each row group according to the characteristic signal; and a quantizer for quantizing the characteristic signals based on the shifted signals and outputting the quantized characteristic signals.

Description

Recording controller and parity check code decoder

Technical field

The invention relates to a kind of recording technique, refer to especially the recording mode of a kind of parity check code (parity-check code) decoder.

Background technology

Low density parity check code (low-density parity-check code, LDPC) is a kind of error correcting code.Because coding gain approaches shannon limit (Shannon limit), recently also be employed in gradually in some communication standards, for example: second generation satellite digital video broadcast (Digital Video Broadcast-Satellite version 2, DVB-S2), digital TV ground multimedia broadcasting (Digital Terrestrial Multimedia Broadcasting, DTMB) or IEEE 802.11.In receiving terminal, ldpc decoder is that each position to be decoded from passage is considered as a node (bit node), and wherein N position node must satisfy (N-K) individual condition, just can obtain correct decoding, and these conditions namely is called inspection node (check node).Check that nodes are that under zero prerequisite, ldpc decoder can make this equipotential node mutually exchange this equipotential node with these inspection nodes take iterative manner may be as 0 or 1 probability satisfying these.

And many ldpc decoders all adopt logarithm similarity ratio (Log-likelihood ratio, LLR) to simplify calculating, and are to make the node may be for 0 probability divided by may be for after 1 probability, get LLR and form the expression of a reliability.Along with the increase of iterations, a position node may be higher for the probability of a particular value (0 or 1), and the absolute value of reliability also thereby increase.But in side circuit, can only realize with limited location length, be an important topic so how to record huge reliability.Though the Chinese patent application case of China's application number 200610012000.9 proposes to record reliability according to iterations, but because the number of times of transformation range sets in advance, therefore, determine that according to iterations reliability may not be certain to meet running treatment situation at that time.

Summary of the invention

Therefore, purpose of the present invention namely can dynamically be adjusted the parity check code decoder that records the required bit length of reliability according to reliability size providing a kind of, helps to reduce the cost of realizing circuit.

So, parity check code decoder of the present invention, be applicable to receive N position to be decoded through the parity check code coding at least by a passage, comprise: a demo plant, be a node depending on each position to be decoded, and have the capable parity check matrix of N with one and be multiplied by this N node and obtain a plurality of inspection nodes; One reliability generation device produces a reliability index according to this passage for each node; One reliability updating device makes this equipotential node and these check the mutual iteration exchange message of nodes based on these reliability indexs, and exchanges to upgrade N respectively to should the capable exchange result of N with iteration each time; An and recording controller, comprise: a separator, the capable weight capable according to this N is divided into delegation's group at least with this matrix, more export N the characteristic signal of corresponding these exchange results respectively according to the capable weight of every delegation group, and the row that belongs to delegation's group has identical capable weight, and the characteristic signal that belongs to delegation's group is to represent with identical bits length; One quantizes the ruling device, according to these characteristic signals, for every delegation group determines a shift signal; And a quantizer, quantize just to export after these characteristic signals based on this shift signal.

And recording controller of the present invention, be applicable to receive N signal to be recorded at least, and have the capable matrix of N and control according to one, comprise: a separator, the capable weight capable according to this N is divided into delegation's group at least with this matrix, more export N the characteristic signal of distinguishing these signals to be recorded of correspondence according to the capable weight of every delegation group, and the row that belongs to delegation's group has identical capable weight, the characteristic signal that belongs to delegation's group is to represent with identical bits length; One quantizes the ruling device, according to these characteristic signals, for every delegation group determines a shift signal; And a quantizer, quantize just to write an internal memory after these characteristic signals based on this shift signal.

Description of drawings

Fig. 1 is a calcspar, and the preferred embodiment of parity check code decoder of the present invention is described;

Fig. 2 is a calcspar, and the recording controller of this preferred embodiment is described;

Fig. 3 is a calcspar, and the saturated counters of this preferred embodiment is described; And

Fig. 4 is a calcspar, and the displacement resolver of this preferred embodiment is described.

Embodiment

About aforementioned and other technology contents, characteristics and effect of the present invention, in the following detailed description that coordinates with reference to a graphic preferred embodiment, can clearly present.

Consult Fig. 1, the preferred embodiment of parity check code decoder 100 of the present invention is applicable to receive plural number through the position to be decoded of LDPC coding by a passage 200, comprises a reliability generation device 1, a reliability updating device 2, a demo plant 3, a recording controller 5 and an internal memory 4.And parity check code decoder 100 of the present invention is ldpc decoders.

It is a Node B that demo plant 3 is looked each position to be decoded ₀, B ₁, B ₂..., and be that the low density parity check matrix of take a matrix size as (N-K) * N (namely have (N-K) be listed as and to have a N capable) is multiplied by N position Node B ₀, B ₁, B ₂... B _N-1Obtain (N-K) individual inspection node C ₀, C ₁, C ₂... C _N-K-1, (N-K)＞0 wherein.It is 1 that the m+1 of hypothesis matrix is listed as the n+1 row element, and definition checks node C _mWith the position Node B _nArq message, and same inspection node C mutually _mCan with at least two mutual arq messages of position node, m=0 wherein, 1,2... (N-K-1), n=0,1,2... (N-1).

Reliability generation device 1 can be each Node B according to passage 200 quality _nProduce a reliability index Q _nReliability updating device 2 is based on reliability index Q _nAnd make this equipotential Node B _nCheck node C with these _mMutual iteration exchange message, and exchange to upgrade these reliability indexs Q with iteration each time _nWith the different Index for examination Q of plural number _mnDemo plant 3 is based on these reliability indexs Q _nUpgrade this equipotential Node B _nAfter, then with position Node B after on Matrix Multiplication, these upgrade ₀～B _N-1Obtain upgrading rear inspection node C ₀～C _N-K-1, and determine according to this whether continue the next iteration exchange.In addition, recording controller 5 also can (refer in the present embodiment that these upgrade rear reliability index Q with plural number signal to be recorded _n) write memory 4.

And the exchange result of reliability updating device 2 (is reliable index Q _nWith different Index for examination Q _mn) capable to N that should matrix respectively, and be defined as follows.Reliability index Q _nDefinition be: the position Node B _nPossible probability ratio (namely may for 0 probability with may be the ratio of 1 probability) get the result after LLR.And different Index for examination Q _mnDefinition be: satisfying except checking node C _mOuter other can with the position Node B _nThe inspection node C of mutual arq message _m, be under zero prerequisite, a Node B of weighing out _nPossible probability ratio get result after LLR.Therefore, when the position Node B _nMay be higher for 0 probability, reliability index Q _nWith different Index for examination Q _mnCan be greater than 0.Otherwise, be not more than 0.And with the increase of iterations, the position Node B _nMay be for the probability of a particular value (0 or 1) be higher, reliability index Q _nWith different Index for examination Q _mnAbsolute value also larger.At this moment, if recording controller 5 directly records the exchange result without special processing, the confined space of internal memory 4 will not applied use.

Consult Fig. 2, recording controller 5 comprises that a separator 51, quantizes ruling device 50 and a quantizer 54.Reliability index Q after corresponding renewal of this N difference of separator 51 output _nCharacteristic signal.Whether this quantification ruling device 50 reaches the saturated plural shift signal that decides according to these characteristic signals.And this quantizer 54 makes these characteristic signals quantize rear (that is: divided by after shift signal) just write memory 4 based on these shift signals, shortens to reach by the quantification program purpose that records required bit length.

Matrix size according to demo plant 3 employings, but this matrix of inference has (N-K) * N element (entry) (element value is 0 or 1), usually claim the non-zero element of row wherein to add up to the row weight (row weight) of these row, claim the non-zero element of delegation wherein to add up to the capable weight (column weight) of this row.All row weights all equate and all row weights all equate if satisfy, and look matrix and are rule (regular) type; If do not satisfy, it is irregular (irregular) type.For convenience of description, this preferred embodiment will be done the example explanation with the irregular type matrix.

Separator 51 meetings be divided into G (G 〉=1) row according to the capable capable weight of this N with matrix to be organized, and more exports this N difference correspondence according to the capable weight of every delegation group and upgrades rear reliability index Q _nCharacteristic signal.And the row that belongs to delegation's group has identical capable weight, and the characteristic signal that belongs to delegation's group is to represent with identical bits length, and the increase of bit length retinue weight and become large.

This is because the capable weight of n+1 is larger, representative exist more a plurality of can with the position Node B _nThe inspection node C of mutual arq message _m, reliability index Q _nAbsolute value also can thereby increase fast.So separator 51 can give the larger bit length of characteristic signal of corresponding larger row weight, to avoid saturated too soon.For example: suppose that separator 51 is divided into G=3 row group (being the first row group, the second row group, the third line group) with matrix, the capable weight of each row group is sequentially 3,4,11.So, separator 51 can represent to belong to the characteristic signal of the first row group with the A=6 bit length, represent to belong to the characteristic signal of the second row group with the B=7 bit length, and represent to belong to the characteristic signal of the third line group with the C=9 bit length.

Because recording controller 5 is to record in the same manner reliability index Q after the renewal of every delegation group _nSo, only explain with the first row group herein.After separator 51 determines to represent to belong to the characteristic signal of the first row group with the A=6 bit length, each characteristic signal is divided into one show the symbol indication (1) of its symbol (sign) and the absolute value signal (5) of its absolute value of demonstration.That is to say, if the absolute value of characteristic signal is not less than (2 ⁵-1), can export absolute value signal (value is 11111); If less than (2 ⁵-1), can be take 5 bit lengths equivalence is used as absolute value signal (for example: characteristic signal is as 18, and absolute value signal is 10010).

Determine that for every delegation group one presents the shift signal of 2 power side according to these absolute value signal and quantize ruling device 50.And quantize ruling device 50 have respectively to should G=3 3 saturated counters 52 and 3 displacement resolvers 53 of capable group.The saturated counters 52 of corresponding the first row group can judge whether the absolute value signal that belongs to the first row group reaches saturated (namely value is 11111) and export a saturation count, and it represents the reliability index Q that reaches capacity in the rear the first row group of iteration exchange each time _nNumber.Then, the displacement resolver 53 of corresponding the first row group can further decide shift signal according to saturation count.And (that is: divided by after shift signal) ability write memory 4 after quantizer 54 can make the absolute value signal that belongs to the first row group quantize based on shift signal, so quantizer 54 can be the updating memory of iteration exchange each time 4 contents.In addition, recording controller 5 also comprises a symbol buffer 55, records each symbol indication, for the symbol of identification internal memory 4 contents.Certainly, in another embodiment, also can ellipsis buffer 55, directly symbol is indicated write memory 4.

Consult Fig. 3 and Fig. 4, in more detail, each saturated counters 52 has a judging unit 521, a multi-task unit 522, an adder unit 523 and a saturated buffer unit 524, and each displacement resolver 53 has a judging unit 531, a multi-task unit 532, displacement statistic unit 533 and a shift cache unit 534.Each shift cache unit 534 produces these reliability indexs Q with reliability generation device 1 _nAnd the replacement shift signal is a default value, and each saturated buffer unit 524 is with each these reliability indexs Q that upgrades of reliability updating device 2 _nAnd the replacement saturation count is zero.

For the first row group, be after zero in saturated buffer unit 524 replacement saturation count, judging unit 521 just can begin to compare the absolute value signal that belongs to the first row group and whether equal a saturation value (namely 11111), if equal, multi-task unit 522 can output 1 value; If be not equal to, multi-task unit 522 can output 0 value.Then, adder unit 523 can add this output the last saturation count of saturated buffer unit 524, for saturated buffer unit 524 with addition result as saturation count after upgrading.Then, judging unit 521 continues next absolute value signal that belongs to the first row group is compared again, until the absolute value signal that all belong to the first row group is completed in comparison.

Then, whether the saturation count that the judging unit 531 of displacement resolver 53 can the judgement comparison be completed gained greater than a critical value, and impels multi-task unit 532 output one progression signals.Greater than critical value, multi-task unit 532 is chosen a shift amount and is used as the progression signal when saturation count; When being not more than, choosing 1 and be used as the progression signal.After iteration exchange for the first time, displacement statistic unit 533 can be used as output with the default value of shift signal with the progression signal times.And in the exchange of subsequently iteration, the shift signal that displacement statistic unit 533 can get iteration clearing house before the progression signal times.And shift cache unit 534 can be with the output of displacement statistic unit 533 as the shift signal after upgrading.

Lift an example start of displacement resolver 53 is described, and suppose that the default value of shift signal is 2 ^-2After iteration exchange for the first time, if judging unit 531 judges saturation count greater than critical value, multi-task unit 532 will be chosen a shift amount 2 ²Be used as the progression signal, for displacement statistic unit 533, it be multiplied by the default value 2 of shift signal ^-2, be 1 and make shift cache unit 534 upgrade shift signal.This is representing that also quantizer 54 can be directly with absolute value signal write memory 4.

And after iteration exchange for the second time, if judging unit 531 judges again saturation count greater than critical value, multi-task unit 532 will be chosen a shift amount 2 ², before can being multiplied by it, the statistic unit 533 that then is shifted once reaches the shift signal (value is 1) for gained, be 2 and make shift cache unit 534 upgrade shift signal ²Then, quantizer 54 can (value be 2 divided by upgrading the backward shift signal with absolute value signal ²) after write memory 4.

Although it should be noted that this preferred embodiment is that to have the irregular type matrixes of 3 row groups be example, row group number is not limited to this.Certainly, also visual regular pattern composite matrix is a special case wherein, and organizing at once number is 1.And, be write memory 4 again after symbol indication and absolute value signal although separator 51 is distinguishing characteristic signals.But in another embodiment, also can omit separator 51, directly in sign (sign) mode, characteristic signal be write.For example: when characteristic signal is-1, write 11111; When characteristic signal is 1, write 00001.

Moreover in the present embodiment, these shift signals of determining of displacement resolvers 53 are (for example: 2 to present 2 power side ^X), and quantizer 54 is ability write memories 4 after making absolute value signal divided by shift signal.But in other is used, also can change shift signal into and refer to that (for example: X), and quantizer 54 is divided by 2 to power side's index ^X, wherein X equals the value of shift signal.

Even more noteworthy, for these displacement resolvers 53, it is identical that the selected critical value of each judging unit 531 does not need shift amount identical and that each multi-task unit 532 is selected not need yet, and can adjust with the capable weight of corresponding row group.Even need not limit the shift signal that each shift cache unit 534 has identical default value, can set different default values according to passage 200 quality, and passage 200 quality be better, default value is larger.This is because passage 200 quality are better, the position Node B _nNot disturbed by passage 200, it is that the probability of a particular value is also just higher.

In addition, this preferred embodiment is based on the reliability index Q that reliability updating device 2 each iteration clearing houses get _nCome record, but the reliability index Q that also can produce based on reliability generation device 1 again _nCome record.And also can make into based on the different Index for examination Q that produces in iterative process in another embodiment, _mnCome record.

Although and this preferred embodiment is built-in memory 4 records with parity check code decoder 100, can be also to write an external memory 4.And recording controller 5 is independently to go out parity check code decoder 100.

In sum, parity check code decoder 100 of the present invention decides shift signal according to the saturation count of iteration exchange each time, and with absolute value signal divided by shift signal after write memory 4, record required bit length so can effectively shorten, and help to reduce the cost of realizing circuit, therefore really can reach purpose of the present invention.

The above person of thought, it is only preferred embodiment of the present invention, when not limiting scope of the invention process with this, the simple equivalence of namely generally doing according to the present patent application the scope of the claims and invention description content changes and modifies, and all still remains within the scope of the patent.

Claims

1. A kind of parity code decoder, is suitable for receiving at least N bits to be decoded through parity code encoding by a channel, comprising:

A verification device regards each bit to be decoded as a bit node, and multiplies the N bit nodes by a parity check matrix with N rows to obtain a plurality of check nodes, and uses the parity check matrix with N rows Multiply by the updated bit node to get the updated check node;

A reliability generation device generates a reliability index for each bit node according to the quality of the channel, wherein the definition of the reliability index is: the ratio of the probability of the bit node that may be 0 to the probability that may be 1 is right The result after counting the similarity ratio;

A reliability update device, based on the reliability index, the peer node and the check nodes iteratively exchange messages with each other, and update N exchange results respectively corresponding to the N rows with each iterative exchange, wherein each exchange The result has the reliability index or at least one different check index, and the definition of the different check index is: under the premise that other check nodes that can exchange messages with the bit node except one check node are zero, the measured The ratio of the probability that the bit node may be 0 to the probability that may be 1 is obtained by taking the logarithmic similarity ratio; and

A record controller, including:

A separator, which divides the matrix into G (G≥1) row groups according to the row weights of the N rows, and outputs N characteristic signals respectively corresponding to the equivalent exchange results according to the row weights of each row group, and belongs to the same row The rows of the group have the same row weight, and the characteristic signals belonging to the same row group are represented by the same bit length;

A quantization decision device, based on the characteristic signals, determines a shift signal for each row group; and

a quantizer, which quantizes the characteristic signals based on the shift signal before outputting,

Wherein, the quantitative judgment device has:

G saturation counters respectively corresponding to each row group, judging whether the characteristic signal belonging to the same row group reaches saturation and outputting a saturation count; and

G shift determiners respectively corresponding to each row group determine the shift signal according to the saturation count.

2. The parity-check code decoder of claim 1, wherein each saturation counter has:

a saturation buffer unit, resetting the saturation count each time the reliability updating device updates the exchange results;

A judging unit, comparing whether the characteristic signal belonging to each row group is saturated;

a multitasking unit, outputting a specific value according to the comparison result of the judging unit; and

An addition unit adds the specific value to a previous saturation count for the saturation buffer unit to output the updated saturation count.

3. The parity-check code decoder as claimed in claim 1, wherein each shift determinator has:

a shift register unit, which resets the shift signal to a default value as the reliability generating device generates the reliability indicators;

A judging unit, judging whether the saturation count is greater than a critical value;

a multitasking unit, outputting a progressive signal based on the determination result of the determination unit; and

A shift statistics unit multiplies the progressive signal by a previous shift signal for the shift register unit to output the updated shift signal.

4. The parity-check code decoder as claimed in claim 1, wherein, after the separator distinguishes each characteristic signal into a symbol indication showing its sign and an absolute value signal showing its absolute value, the The quantization arbitration means decides the shift signal for each row group based on the absolute value signal belonging to each row group.

5. The parity-check code decoder as claimed in claim 1, wherein, the shift signals determined by the G shift determiners present a power of 2, and the quantizers will belong to the same row group The characteristic signal of is divided by the corresponding shift signal.

6. The parity-check code decoder as claimed in claim 1, wherein the shift signal determined by the G shift determiners presents a power exponent, and the quantizers will belong to the same row group The characteristic signal is divided by 2 ^x , and x is equal to the value of the corresponding shifted signal.

7. The parity-check code decoder as claimed in claim 3, wherein each shift register unit adjusts a default value of the shift signal based on the channel.

8. A recording controller for a parity-check code decoder, adapted to receive at least N signals to be recorded, and to control according to a parity check matrix with N rows, wherein the N signals to be recorded It is the updated N exchange results corresponding to N rows respectively generated by the parity-check code decoder processing the received N coded bits to be decoded by the parity-check code, and the recording controller includes :

A separator, which divides the matrix into G (G≥1) row groups according to the row weights of the N rows, and outputs N characteristic signals respectively corresponding to the signals waiting to be recorded according to the row weights of each row group, and belonging to the same row The rows of the group have the same row weight, and the characteristic signals belonging to the same row group are represented by the same bit length;

a quantizer, which quantizes the characteristic signals based on the shift signal before writing into a memory,

Wherein, the quantitative judgment device has:

9. The recording controller of claim 8, wherein each saturation counter has:

10. The recording controller as claimed in claim 8, wherein each shift determiner has:

11. The recording controller as claimed in claim 8, wherein, after the separator distinguishes each characteristic signal into a sign indication showing its sign and an absolute value signal showing its absolute value, the quantization and judging means can The shift signal is decided for each row group based on the absolute value signal belonging to each row group.

12. The recording controller as claimed in claim 8, wherein, the shift signals determined by the G shift determiners present a power of 2, and the quantizer divides the characteristic signals belonging to the same row group to correspond to the shift signal.

13. The recording controller as claimed in claim 8, wherein, the shift signal determined by the G shift determiners presents a power exponent, and the quantizer divides the characteristic signals belonging to the same row group by 2 ^x , and x is equal to the value of the corresponding shift signal.

14. The recording controller of claim 10, wherein each shift buffer unit adjusts a default value of the shift signal based on the channel.