CN111384975A - Optimization method and device of multi-system LDPC decoding algorithm and decoder - Google Patents
Optimization method and device of multi-system LDPC decoding algorithm and decoder Download PDFInfo
- Publication number
- CN111384975A CN111384975A CN201811645882.1A CN201811645882A CN111384975A CN 111384975 A CN111384975 A CN 111384975A CN 201811645882 A CN201811645882 A CN 201811645882A CN 111384975 A CN111384975 A CN 111384975A
- Authority
- CN
- China
- Prior art keywords
- confidence
- multiplication
- decoding algorithm
- division
- ldpc decoding
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000004422 calculation algorithm Methods 0.000 title claims abstract description 48
- 238000000034 method Methods 0.000 title claims abstract description 40
- 238000005457 optimization Methods 0.000 title abstract description 17
- 238000013139 quantization Methods 0.000 claims abstract description 29
- 238000012545 processing Methods 0.000 claims abstract description 12
- 238000004590 computer program Methods 0.000 claims description 19
- 238000004364 calculation method Methods 0.000 claims description 9
- 238000006243 chemical reaction Methods 0.000 claims description 6
- 230000008569 process Effects 0.000 description 8
- 230000006870 function Effects 0.000 description 7
- 238000010586 diagram Methods 0.000 description 6
- 230000008878 coupling Effects 0.000 description 3
- 238000010168 coupling process Methods 0.000 description 3
- 238000005859 coupling reaction Methods 0.000 description 3
- 239000000758 substrate Substances 0.000 description 3
- 230000008859 change Effects 0.000 description 2
- 238000004891 communication Methods 0.000 description 2
- 238000013459 approach Methods 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 239000011159 matrix material Substances 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
- H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
- H03M13/1105—Decoding
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
- H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
- H03M13/1148—Structural properties of the code parity-check or generator matrix
- H03M13/1171—Parity-check or generator matrices with non-binary elements, e.g. for non-binary LDPC codes
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D30/00—Reducing energy consumption in communication networks
- Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Error Detection And Correction (AREA)
Abstract
The embodiment of the invention is suitable for the technical field of coding and decoding, and provides an optimization method, a device and a decoder of a multi-system LDPC decoding algorithm, wherein the method comprises the following steps: receiving an operation instruction aiming at elements in a finite field, wherein the operation instruction comprises a multiplication and division operator; converting the multiplication-division operation corresponding to the multiplication-division operator into an addition-subtraction operation according to a preset element-power table; calculating an operation result of the addition and subtraction operation; determining a target element corresponding to an operation result by inquiring a preset power-element table, and optimizing the space complexity of the multi-system LDPC decoding algorithm; and quantizing the confidence degrees of different symbols corresponding to each code in the multi-system LDPC decoding algorithm into finite digits. In the embodiment, by converting the multiplication and division operation in the finite field into the addition and subtraction operation and performing optimization processing on the confidence coefficients of different symbols corresponding to each code in non-uniform quantization, the spatial complexity of the decoding algorithm is reduced, and the decoding efficiency is improved.
Description
Technical Field
The invention belongs to the technical field of coding and decoding, and particularly relates to an optimization method of a multilevel LDPC decoding algorithm, an optimization device of the multilevel LDPC decoding algorithm, a decoder and a computer readable storage medium.
Background
Binary Low-Density-Parity-Check (B-LDPC) code is a packet error correcting code with sparse Check matrix, is suitable for almost all channels, can quickly approach the channel capacity of Shannon theory in the form of code length index, and is a research hotspot in recent years in the coding field. However, when the code length is relatively short, the performance of the B-LDPC code may be degraded to some extent. Therefore, researchers have proposed a multilevel LDPC (Non-binary low-Density-Parity-Check, NB-LDPC for short) code based on the B-LDPC code. Compared with the B-LDPC code, the NB-LDPC code has theoretically more excellent performance particularly when the code length is shorter, and at present, the NB-LDPC code is also gradually adopted as the coding standard by related industries. Such as the beidou satellite navigation system (BDS).
The application of NB-LDPC codes also brings about more complex decoding algorithms. Therefore, in order to reduce the complexity of the NB-LDPC decoding algorithm, it is necessary to convert the probability represented in a confidence manner in the decoding algorithm into a logarithmic form, thereby quantizing it to a finite number of bits. However, under the condition of high signal-to-noise ratio, the probability of receiving a code word as a certain symbol is very large, and the probability of receiving the code word as other symbols is very small, namely the probability distribution of the symbols is very concentrated; under the condition of low signal-to-noise ratio, the symbol probability distribution is balanced. According to the definition of the confidence coefficient, the confidence coefficient change range is large when the signal-to-noise ratio is high, and the confidence coefficient change range is small when the signal-to-noise ratio is low. Notably, the greater the confidence value, the more abundant the decoding information it provides. In the prior art, the confidences of different values are quantized according to the same standard, so that the part with smaller confidence degree also occupies more bit numbers, and the storage space is increased.
On the other hand, NB-LDPC decoding algorithms also involve multiply-divide operations in the finite field. Since the multiplication-division operation in the finite field is different from the ordinary arithmetic multiplication-division rule, it is a common practice to store a multiplication table and a division table in the finite field in advance, and then perform a fast multiplication-division calculation by a table look-up method. The above method is very simple and very effective when the order of the finite field is low. However, the above finite field multiplication table and division table are proportional to the square of their orders, i.e. the high order finite field multiplication table and division table require a very large memory space. The occupation of the storage space is further increased, and the space complexity of the NB-LDPC decoding algorithm is improved.
Disclosure of Invention
In view of this, embodiments of the present invention provide an optimization method and apparatus for a multilevel LDPC decoding algorithm, and a decoder, so as to solve the problem in the prior art that a NB-LDPC decoding algorithm has a high spatial complexity.
A first aspect of an embodiment of the present invention provides an optimization method for a multilevel LDPC decoding algorithm, including:
receiving an operation instruction for an element in a finite field, the operation instruction comprising a multiply-divide operator;
converting the multiplication-division operation corresponding to the multiplication-division operator into an addition-subtraction operation according to a preset element-power table;
calculating an operation result of the addition and subtraction operation;
determining a target element corresponding to the operation result by inquiring a preset power-element table, and optimizing the space complexity of the multi-system LDPC decoding algorithm;
the step of optimizing the spatial complexity of the multilevel LDPC decoding algorithm further comprises:
and quantizing the confidence degrees of different symbols corresponding to each code in the multi-system LDPC decoding algorithm into finite digits.
A second aspect of the embodiments of the present invention provides an optimization apparatus for a multilevel LDPC decoding algorithm, including:
the receiving module is used for receiving an operation instruction aiming at elements in a finite field, and the operation instruction comprises a multiplication-division operator;
the conversion module is used for converting the multiplication-division operation corresponding to the multiplication-division operator into an addition-subtraction operation according to a preset element-power table;
the calculation module is used for calculating the operation result of the addition and subtraction operation;
the determining module is used for inquiring a preset power-element table and determining a target element corresponding to the operation result;
and the quantization module is used for quantizing the confidence degrees of different symbols corresponding to each code in the multi-system LDPC decoding algorithm into finite digits.
A third aspect of the embodiments of the present invention provides a terminal device, including a memory, a processor, and a computer program stored in the memory and executable on the processor, where the processor implements the steps of the optimization method of the multilevel LDPC decoding algorithm when executing the computer program.
A fourth aspect of embodiments of the present invention provides a computer-readable storage medium storing a computer program that, when executed by a processor, implements the steps of the above-described optimization method of the multilevel LDPC decoding algorithm.
Compared with the prior art, the embodiment of the invention has the following advantages:
according to the embodiment of the invention, the multiplication-division operation in the finite field can be converted into the addition-subtraction operation by presetting the simple element-power table and the power-element table, so that the problem that the preset high-order finite field multiplication table and the preset division table occupy very large storage space is solved; on the basis of this, by non-uniformly quantizing the confidence levels, each confidence level can be expressed in the form of a finite number of bits, and the memory space of the confidence level can be optimized. Through the optimization processing of the two aspects, the occupation of the NB-LDPC decoding algorithm on the storage space is greatly reduced, the space complexity of the NB-LDPC decoding algorithm is reduced, and the decoding efficiency is improved.
Drawings
In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the drawings used in the embodiments or the description of the prior art will be briefly described below. It is obvious that the drawings in the following description are only some embodiments of the invention, and that for a person skilled in the art, other drawings can be derived from them without inventive effort.
FIG. 1 is a flow chart illustrating the steps of a method for optimizing a multilevel LDPC decoding algorithm according to an embodiment of the present invention;
FIG. 2 is a circuit schematic of a finite field multiply/divide according to one embodiment of the present invention;
FIG. 3 is a schematic diagram of an optimization apparatus for a multilevel LDPC decoding algorithm according to an embodiment of the present invention;
fig. 4 is a schematic diagram of a decoder according to an embodiment of the present invention.
Detailed Description
In the following description, for purposes of explanation and not limitation, specific details are set forth, such as particular system structures, techniques, etc. in order to provide a thorough understanding of the embodiments of the invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced in other embodiments that depart from these specific details. In other instances, detailed descriptions of well-known systems, devices, circuits, and methods are omitted so as not to obscure the description of the present invention with unnecessary detail.
The technical solution of the present invention will be described below by way of specific examples.
Referring to fig. 1, a schematic step flow diagram illustrating an optimization method of a multilevel LDPC decoding algorithm according to an embodiment of the present invention is shown, which may specifically include the following steps:
s101, receiving an element operation instruction in a finite field, wherein the operation instruction comprises a multiplication and division operator;
it should be noted that the method can be applied to the decoding process of the multilevel LDPC (NB-LDPC) code.
In abstract algebra, a field is an algebraic structure that can perform addition, subtraction, multiplication, and division operations. If a field contains only a limited number of elements, it is called a finite field.
In the embodiment of the present invention, when an operation instruction for each element in a finite field is received, the element may be subjected to a multiplication-division operation according to a multiplication-division operator included in the operation instruction.
S102, converting the multiplication-division operation corresponding to the multiplication-division operator into an addition-subtraction operation according to a preset element-power table;
in general, in finite fields, any non-0 element can be expressed as a power of any of the non-0 elements. Let Ω be any non-0 element in the finite field gf (q), X and Y be any element in gf (q), and can be represented as:
then the multiplication and division in gf (q) can be expressed as:
wherein, (J + -K)qAnd (4) the addition and subtraction result is shown to be complemented by the finite field order q.
Taking 64 advanced finite field as an example for explanation, 64 finite fields have 64 elements in total, which can be expressed as a0,a1,…,a63(or represented directly by 0,1, … 63), divide by 0 element (a)0(0) Other elements can be expressed as a power of one of the elements (power of the finite field). For example, a1Can be expressed as a1Power of 1 a2Is shown as a1…, a to the power of 563Is shown as a1The power of the above elements to the 17 th power is merely illustrative and is not a true power value. In other words, a1-a63Can be expressed as a1To the power of a, substrate a1Change to a2,a3Other non-0 elements are also true.
Therefore, according to the characteristics of the finite field, a simple element-power table and a power-element table can be stored in advance, and the multiplication and division operation in the finite field is converted into the addition and subtraction operation, so that the requirement on a storage space during decoding by adopting a multilevel LDPC decoding iterative algorithm can be greatly reduced.
In the embodiment of the present invention, the preset element-power table may record power values corresponding to elements other than 0 according to the selected basis. That is, each non-0 element can be expressed as a power of the base.
For example, if the substrate is a1Then, each non-0 element that can be recorded in the element-power table can be represented as a1To the power of several, e.g. [1,5, … 17 in the preceding example]。
Therefore, for a first element and a second element in the operation instruction, by querying a preset element-power table, a power value of the first element and a power value of the second element can be obtained respectively, so that the multiplication and division operation on the first element and the second element is converted into the addition and subtraction operation.
For example, the first element, the second element, and the multiplication-division operator in the finite field may be represented by X, Y and OP, respectively, i.e., the first element X, the second element Y, and the multiplication-division operator OP, which may be further distinguished as a multiplication operator and a division operator.
S103, calculating an operation result of the addition and subtraction operation;
the power J of the first element X and the power K of the second element Y can be determined by looking up a preset element-power table.
Then, corresponding calculation is carried out for different operators.
For example, for a multiplication operator, the sum of the power value J of the first element X and the power value K of the second element Y (J + K) can be calculatedq(ii) a For a division operator, the difference (J-K) between the power value J of the first element X and the power value K of the second element Y can be calculatedq。
S104, determining a target element corresponding to the operation result by inquiring a preset power-element table, and optimizing the space complexity of the multi-system LDPC decoding algorithm;
calculating the sum/difference (J + -K) of J and K according to the operator OPqThen, the above (J + -K) can be obtained by looking up the preset power-element tableqThe corresponding target element Z.
In the embodiment of the invention, the power-element table records the elements corresponding to any power value of the selected substrate.
FIG. 2 is a schematic diagram of a finite field multiply/divide circuit according to an embodiment of the present invention; by presetting the element-power table and the power-element table, after the finite field element and the corresponding operator are input, the multiplication and division operation in the finite field can be converted into the addition and subtraction operation according to the operator, so that the corresponding target element is output.
The multiplication/division of the finite field is different from the common multiplication-division, if the finite field elements of the 64 system are represented by 0-63, the element 2 × is not equal to 6 elements, the calculation of the multiplication or the division is more complex, and generally needs to be realized by a lookup table, therefore, the multiplication of the 64 system needs to be realized by inquiring the table of 64 × 64, and the division is also the same.
And S105, quantizing the confidence degrees of different symbols corresponding to each code in the multi-system LDPC decoding algorithm into finite digits.
In general, the confidence LDR (Log-sensitivity-Ratio) can be defined as:
wherein p (c ═ s)n) Indicating the code word c as the symbol snThe probability of (c).
In the embodiment of the invention, in order to reduce the spatial complexity of the multilevel LDPC decoding, the LDR can be usednQuantization is performed and represented by a finite number of bits. Under the condition of high signal-to-noise ratio, the probability that the received code word c is a certain symbol is very high, and the probability that the received code word c is other symbols is very low, namely the probability distribution of the symbols is very concentrated; when in the condition of low signal-to-noise ratio,the symbol probability distribution is then relatively balanced. According to the definition of LDR, the LDR variation range is large when the signal-to-noise ratio is high, and the LDR variation range is small when the signal-to-noise ratio is low. Notably, the larger the LDR value, the more abundant the decoding information it provides. In other words, more bits have to be used for distinguishing the parts with larger LDR values during quantization, while less bits are used for distinguishing the parts with smaller LDR values, i.e. the parts with larger LDR values occupy more bits, the parts with smaller LDR values occupy less bits, and even if the number of quantization bits is limited, the parts do not occupy bits.
Therefore, according to the above-mentioned LDR value distribution characteristics and their physical meanings, this embodiment can perform non-uniform quantization on the confidence of each symbol of the multilevel LDPC code based on the maximum LDR, and represent the confidence of each symbol in the form of a finite number of bits.
In the embodiment of the present invention, confidence sets of a plurality of symbols may be obtained, respectively, where the confidence sets include a plurality of confidences corresponding to a plurality of symbols of the multilevel LDPC code one to one. For example, the confidence of multiple symbols may be obtained and represented as a set of confidences.
Taking 64-ary LDPC as an example, there are 64 symbols in total, which can be expressed as S0-S63It is assumed that a multilevel LDPC code is denoted as Cn, and the decoding process is a process of determining which symbol Cn is, so-called a confidence set, i.e., a confidence level that Cn takes different symbols.
In a specific implementation, initial confidences of a plurality of symbols may be first obtained, where the initial confidences are Floating Point (Floating Point) initial confidences or Integer (Integer) initial confidences.
Floating point numbers are digital representations of numbers belonging to a particular subset of rational numbers and can be used in computers to represent any real number approximately.
In the embodiment of the present invention, for the initial floating point confidence, the initial floating point confidence may be rounded, and the floating point confidence is converted into an integer confidence, so as to generate a confidence set of multiple elements.
Confidence of multiple symbolsThe set may be represented as LDRk,βkK), where β denotes the sign to which the codeword corresponds, i.e. Sn in the above confidence definition.
After the confidence sets are obtained, the numerical values of the confidence degrees can be compared, and the maximum value { LDR ] of the confidence degree in the confidence degree sets is identifiedmax,βkmax}。
In an embodiment of the present invention, the confidence maximum may be quantized to a maximum of N-bit signed integers, where the maximum of the signed integers may be 2N-1-1。
For example, when N is 5, the unsigned value ranges from 0 to 31, and the signed value ranges from-16 to 15.
Therefore, before this step, the number of bits N for quantization needs to be determined, and the number of bits N for quantization needs to be determined according to the decoding performance to be achieved and the requirement of the memory space, and needs to be determined in a compromise manner between the above two factors.
After quantizing the confidence maximum to an N-bit signed integer maximum, the quantized element may be represented as
Then, by respectively determining the numerical difference between each confidence in the confidence set and the maximum value of the confidence, each confidence can be quantized into a finite number of bits according to the magnitude relation between the numerical difference and a preset threshold, wherein the preset threshold is determined by a preset number of bits of quantization processing.
In a specific implementation, each element { LDR in the confidence coefficient set can be selected one by onek,βkCalculating LDRkLDR with the above maximum valuemaxNumerical value difference DLDRk. Then, each confidence is quantified according to the magnitude relation between the numerical difference and a preset threshold.
The preset threshold may be determined according to the number of bits N of quantization processing, i.e. the preset threshold may be represented as 1-2N。
In the present inventionIn the embodiment, if the value difference is greater than or equal to the predetermined threshold 1-2NThe confidence may be quantified as the difference between the above values and 2N-1-1 and; if the difference is less than 1-2NThe confidence can be directly quantified as-2N-1。
That is, if the above numerical difference is greater than or equal to the preset threshold 1-2NThen LDR can be usedkQuantization is 2N-1-1+DLDRkThe quantized element may be represented as {2 }N-1-1+DLDRk,βk}; if the difference is less than 1-2NThen LDR can be usedkDirect quantization to-2N-1The quantized element can be represented as { -2N-1,βk}。
Similarly, taking N-5 as an example, if the confidence value before quantization is [31,28, -4], the maximum confidence value 31 may be first quantized to 15 according to the foregoing description; since 28-31 is-3, -3 is greater than-31, 28 can be quantified as 12 (15-3); since-4-31 is-35 and-35 is less than-31, it is possible to quantify-4 to-16. The quantified values were found to be [15,12, -16 ].
In the embodiment of the invention, according to the distribution characteristics and the physical meaning of the confidence degrees of the multi-system LDPC code, by carrying out non-uniform quantization on each confidence degree, each confidence degree can be represented in the form of limited bits, more bits are used for distinguishing parts with higher confidence degrees, and less bits are used for distinguishing parts with lower confidence degrees, namely, the parts with higher confidence degrees occupy more bits, the parts with lower confidence degrees occupy less bits, and even the parts do not occupy bits under the condition of limited quantization bit number, so that the storage space of the confidence degree can be optimized, and the complexity of an NB-LDPC decoding algorithm is reduced.
In the embodiment of the invention, the multiplication-division operation in the finite field can be converted into the addition-subtraction operation by presetting the simple element-power table and the power-element table, thereby solving the problem that the preset high-order finite field multiplication-division table needs to occupy a very large storage space; on the basis of this, by non-uniformly quantizing the confidence levels, each confidence level can be expressed in the form of a finite number of bits, and the memory space of the confidence level can be optimized. Through the optimization processing of the two aspects, the occupation of the NB-LDPC decoding algorithm on the storage space is greatly reduced, the space complexity of the NB-LDPC decoding algorithm is reduced, and the decoding efficiency is improved.
It should be noted that, the sequence numbers of the steps in the foregoing embodiments do not mean the execution sequence, and the execution sequence of each process should be determined by the function and the internal logic of the process, and should not constitute any limitation on the implementation process of the embodiments of the present invention.
Referring to fig. 3, a schematic diagram of an optimization apparatus for a multilevel LDPC decoding algorithm according to an embodiment of the present invention is shown, which may specifically include the following modules:
a receiving module 301, configured to receive an operation instruction for an element in a finite field, where the operation instruction includes a multiplication-division operator;
a conversion module 302, configured to convert the multiplication-division operation corresponding to the multiplication-division operator into an addition-subtraction operation according to a preset element-power table;
a calculating module 303, configured to calculate an operation result of the addition and subtraction operation;
a determining module 304, configured to query a preset power-element table, and determine a target element corresponding to the operation result;
a quantization module 305, configured to quantize the confidence levels of different symbols corresponding to each code in the multilevel LDPC decoding algorithm into finite bits.
In this embodiment of the present invention, the operation instruction further includes a first element and a second element, and the conversion module 302 may specifically include the following sub-modules:
and the conversion submodule is used for inquiring a preset element-power table, respectively obtaining the power value of the first element and the power value of the second element, and converting the multiplication-division operation into an addition-subtraction operation.
In an embodiment of the present invention, the multiplication-division operator includes a multiplication operator or a division operator, and the calculation module 303 may specifically include the following sub-modules:
a first calculation submodule configured to calculate, for the multiplication operator, a sum of a power value of the first element and a power value of the second element;
a second calculation submodule, configured to calculate, for the division operator, a difference between the power value of the first element and the power value of the second element.
In this embodiment of the present invention, the quantization module 305 may specifically include the following sub-modules:
the obtaining submodule is used for respectively obtaining confidence sets of a plurality of symbols, and the confidence sets comprise a plurality of confidences which are in one-to-one correspondence with the symbols of the multi-system LDPC code;
the identification submodule is used for identifying the maximum confidence value in the confidence set;
a determining submodule, configured to determine a numerical difference between each confidence in the confidence set and the maximum confidence value, respectively;
and the quantization submodule is used for quantizing each confidence coefficient into a finite bit number according to the size relation between the numerical difference and a preset threshold value, and the preset threshold value is determined by the preset bit number of quantization processing.
In the embodiment of the present invention, the obtaining sub-module may specifically include the following units:
the initial confidence coefficient acquisition unit is used for acquiring initial confidence coefficients of a plurality of symbols, and the initial confidence coefficients are floating point type initial confidence coefficients or integer type initial confidence coefficients;
and the confidence set generating unit is used for rounding the floating point type initial confidence and generating a confidence set of a plurality of elements.
In this embodiment of the present invention, the quantization module 305 may further include the following sub-modules:
a bit number determining submodule for determining the bit number N of the quantization processing;
a maximum quantization submodule for quantizing said confidence maximum to a maximum of a signed integer 2 corresponding to said number of bitsN-1-1。
In this embodiment of the present invention, the quantization sub-module may specifically include the following units:
a first quantization unit for determining if the value difference is greater than or equal to 1-2NThen the confidence is quantized to the difference of the numerical value and 2N-1-1 and;
a second quantization unit for determining if the difference is less than 1-2NQuantize the confidence to-2N-1。
For the apparatus embodiment, since it is substantially similar to the method embodiment, it is described relatively simply, and reference may be made to the description of the method embodiment section for relevant points.
Referring to fig. 4, a schematic diagram of a decoder according to an embodiment of the present invention is shown. As shown in fig. 4, the decoder 400 of the present embodiment includes: a processor 410, a memory 420, and a computer program 421 stored in the memory 420 and executable on the processor 410. The processor 410, when executing the computer program 421, implements the steps in the various embodiments of the optimization method of the multilevel LDPC decoding algorithm described above, such as the steps S101 to S105 shown in fig. 1. Alternatively, the processor 410, when executing the computer program 421, implements the functions of each module/unit in the above-mentioned device embodiments, for example, the functions of the modules 301 to 305 shown in fig. 3.
Illustratively, the computer program 421 may be partitioned into one or more modules/units, which are stored in the memory 420 and executed by the processor 410 to implement the present invention. The one or more modules/units may be a series of computer program instruction segments capable of performing specific functions, which may be used to describe the execution of the computer program 421 in the decoder 400. For example, the computer program 421 may be divided into a receiving module, a converting module, a calculating module, a determining module, and a quantifying module, and each module has the following specific functions:
the receiving module is used for receiving an operation instruction aiming at elements in a finite field, and the operation instruction comprises a multiplication-division operator;
the conversion module is used for converting the multiplication-division operation corresponding to the multiplication-division operator into an addition-subtraction operation according to a preset element-power table;
the calculation module is used for calculating the operation result of the addition and subtraction operation;
the determining module is used for inquiring a preset power-element table and determining a target element corresponding to the operation result;
and the quantization module is used for quantizing the confidence degrees of different symbols corresponding to each code in the multi-system LDPC decoding algorithm into finite digits.
The decoder 400 may be a computing device such as a desktop computer, a notebook, a palm computer, a cloud server, a navigation module, a time service module, and the like. The decoder 400 may include, but is not limited to, a processor 410, a memory 420. Those skilled in the art will appreciate that fig. 4 is merely an example of the decoder 400, and does not constitute a limitation on the decoder 400, and may include more or less components than those shown, or combine certain components, or different components, e.g., the decoder 400 may also include input-output devices, network access devices, buses, etc.
The Processor 410 may be a Central Processing Unit (CPU), other general purpose Processor, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), an off-the-shelf Programmable Gate Array (FPGA) or other Programmable logic device, discrete Gate or transistor logic device, discrete hardware component, etc. A general purpose processor may be a microprocessor or the processor may be any conventional processor or the like.
The memory 420 may be an internal storage unit of the decoder 400, such as a hard disk or a memory of the decoder 400. The memory 420 may also be an external storage device of the decoder 400, such as a plug-in hard disk, a Smart Media Card (SMC), a Secure Digital (SD) Card, a Flash memory Card (Flash Card), etc. provided on the decoder 400. Further, the memory 420 may also include both an internal storage unit of the decoder 400 and an external storage device. The memory 420 is used for storing the computer program 421 and other programs and data required by the decoder 400. The memory 420 may also be used to temporarily store data that has been output or is to be output.
It will be apparent to those skilled in the art that the foregoing division of the functional units and modules is merely illustrative for the convenience and simplicity of description. In practical applications, the above function allocation may be performed by different functional units or modules as needed, that is, the internal structure of the apparatus/terminal device is divided into different functional units or modules, so as to perform all or part of the above described functions. Each functional unit and module in the embodiments may be integrated in one processing unit, or each unit may exist alone physically, or two or more units are integrated in one unit, and the integrated unit may be implemented in a form of hardware, or in a form of software functional unit. In addition, specific names of the functional units and modules are only for convenience of distinguishing from each other, and are not used for limiting the protection scope of the present invention. The specific working processes of the units and modules in the system may refer to the corresponding processes in the foregoing method embodiments, and are not described herein again.
In the above embodiments, the descriptions of the respective embodiments have respective emphasis, and reference may be made to the related descriptions of other embodiments for parts that are not described or illustrated in a certain embodiment.
Those of ordinary skill in the art will appreciate that the various illustrative elements and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware or combinations of computer software and electronic hardware. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the implementation. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.
In the embodiments provided in the present invention, it should be understood that the disclosed apparatus/terminal device and method may be implemented in other ways. For example, the above-described embodiments of the apparatus/terminal device are merely illustrative, and for example, the division of the modules or units is only one logical division, and there may be other divisions when actually implemented, for example, a plurality of units or components may be combined or integrated into another system, or some features may be omitted, or not executed. On the other hand, the shown or discussed mutual coupling or direct coupling or communication connection may be an indirect coupling or communication connection through some interfaces, devices or units, and may be in an electrical, mechanical or other form.
The units described as separate parts may or may not be physically separate, and parts displayed as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the units can be selected according to actual needs to achieve the purpose of the solution of the embodiment.
In addition, functional units in the embodiments of the present invention may be integrated into one processing unit, or each unit may exist alone physically, or two or more units are integrated into one unit. The integrated unit can be realized in a form of hardware, and can also be realized in a form of a software functional unit.
The integrated modules/units, if implemented in the form of software functional units and sold or used as separate products, may be stored in a computer readable storage medium. Based on such understanding, all or part of the flow in the method according to the above embodiments may be implemented by a computer program, which may be stored in a computer readable storage medium and used by a processor to implement the steps of the above embodiments of the method. Wherein the computer program comprises computer program code, which may be in the form of source code, object code, an executable file or some intermediate form, etc. The computer-readable storage medium may include: any entity or device capable of carrying the computer program code, recording medium, usb disk, removable hard disk, magnetic disk, optical disk, computer Memory, Read-Only Memory (ROM), Random Access Memory (RAM), electrical carrier wave signals, telecommunications signals, software distribution medium, and the like. It should be noted that the computer readable storage medium may contain content that is subject to appropriate increase or decrease as required by legislation and patent practice in jurisdictions, for example, in some jurisdictions, computer readable storage media that does not include electrical carrier signals and telecommunications signals in accordance with legislation and patent practice.
The above-mentioned embodiments are only used for illustrating the technical solutions of the present invention, and not for limiting the same. Although the present invention has been described in detail with reference to the foregoing embodiments, it will be understood by those of ordinary skill in the art that: the technical solutions described in the foregoing embodiments may still be modified, or some technical features may be equivalently replaced; such modifications and substitutions do not substantially depart from the spirit and scope of the embodiments of the present invention, and are intended to be included within the scope of the present invention.
Claims (10)
1. A method for optimizing a multilevel LDPC decoding algorithm, comprising:
receiving an operation instruction for an element in a finite field, the operation instruction comprising a multiply-divide operator;
converting the multiplication-division operation corresponding to the multiplication-division operator into an addition-subtraction operation according to a preset element-power table;
calculating an operation result of the addition and subtraction operation;
determining a target element corresponding to the operation result by inquiring a preset power-element table, and optimizing the space complexity of the multi-system LDPC decoding algorithm;
the step of optimizing the spatial complexity of the multilevel LDPC decoding algorithm further comprises:
and quantizing the confidence degrees of different symbols corresponding to each code in the multi-system LDPC decoding algorithm into finite digits.
2. The method of claim 1, wherein the operation instruction further comprises a first element and a second element, and the step of converting the multiplication-division operation corresponding to the multiplication-division operator into the addition-subtraction operation according to a preset element-power table comprises:
and querying a preset element-power table to obtain the power value of the first element and the power value of the second element respectively, and converting the multiplication and division operation into an addition and subtraction operation.
3. The method of claim 2, wherein the multiply-divide operator comprises a multiply operator or a divide operator, and wherein the step of calculating the operation result of the add-subtract operation comprises:
for the multiplication operator, calculating a sum of a power value of the first element and a power value of the second element;
calculating a difference between a power value of the first element and a power value of the second element for the division operator.
4. The method of claim 1, wherein the step of quantizing the confidence level of each code corresponding to a different symbol in the multilevel LDPC decoding algorithm to a finite number of bits comprises:
respectively obtaining confidence sets of a plurality of symbols, wherein the confidence sets comprise a plurality of confidences which are in one-to-one correspondence with the symbols of the multi-system LDPC code;
identifying a confidence maximum in the confidence set;
respectively determining the numerical difference between each confidence coefficient in the confidence coefficient set and the maximum confidence coefficient;
and quantizing each confidence coefficient into a finite bit number according to the size relation between the numerical difference and a preset threshold, wherein the preset threshold is determined by a preset bit number subjected to quantization processing.
5. The method of claim 4, wherein the step of obtaining confidence sets for a plurality of symbols respectively comprises:
acquiring initial confidence degrees of a plurality of symbols, wherein the initial confidence degrees are floating point type initial confidence degrees or integer type initial confidence degrees;
and rounding the floating point type initial confidence coefficient to generate a confidence coefficient set of a plurality of symbols.
6. The method of claim 5, further comprising:
determining the bit number N of quantization processing;
quantizing the confidence maximum to a signed integer maximum of 2 corresponding to the number of bitsN-1-1。
7. The method according to claim 6, wherein the step of quantizing the respective confidence levels into a finite number of bits according to a magnitude relationship between the value difference and a preset threshold value comprises:
if the numerical difference is more than or equal to 1-2NThen the confidence is quantized to the difference of the numerical value and 2N-1-1 and;
if the difference is less than 1-2NQuantize the confidence to-2N-1。
8. An apparatus for optimizing a multilevel LDPC decoding algorithm, comprising:
the receiving module is used for receiving an operation instruction aiming at elements in a finite field, and the operation instruction comprises a multiplication-division operator;
the conversion module is used for converting the multiplication-division operation corresponding to the multiplication-division operator into an addition-subtraction operation according to a preset element-power table;
the calculation module is used for calculating the operation result of the addition and subtraction operation;
the determining module is used for inquiring a preset power-element table and determining a target element corresponding to the operation result;
and the quantization module is used for quantizing the confidence degrees of different symbols corresponding to each code in the multi-system LDPC decoding algorithm into finite digits.
9. A terminal device comprising a memory, a processor and a computer program stored in the memory and executable on the processor, characterized in that the processor when executing the computer program implements the steps of the method for optimizing a multilevel LDPC decoding algorithm according to any one of claims 1 to 7.
10. A computer-readable storage medium storing a computer program, wherein the computer program when executed by a processor implements the steps of the method for optimizing a multilevel LDPC decoding algorithm according to any one of claims 1 to 7.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811645882.1A CN111384975B (en) | 2018-12-29 | 2018-12-29 | Optimization method, device and decoder of multi-system LDPC decoding algorithm |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811645882.1A CN111384975B (en) | 2018-12-29 | 2018-12-29 | Optimization method, device and decoder of multi-system LDPC decoding algorithm |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN111384975A true CN111384975A (en) | 2020-07-07 |
| CN111384975B CN111384975B (en) | 2023-05-26 |
Family
ID=71219463
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811645882.1A Active CN111384975B (en) | 2018-12-29 | 2018-12-29 | Optimization method, device and decoder of multi-system LDPC decoding algorithm |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111384975B (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112650863A (en) * | 2020-12-01 | 2021-04-13 | 深圳力维智联技术有限公司 | Cross-media data fusion method, device and storage medium |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104052501A (en) * | 2014-06-26 | 2014-09-17 | 北京航空航天大学 | Low-complexity multi-ary LDPC decoding method |
| CN106936444A (en) * | 2015-12-29 | 2017-07-07 | 北京航空航天大学 | One kind set interpretation method and set decoder |
| WO2018015325A1 (en) * | 2016-07-21 | 2018-01-25 | Koninklijke Philips N.V. | Device and method for performing obfuscated arithmetic |
-
2018
- 2018-12-29 CN CN201811645882.1A patent/CN111384975B/en active Active
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104052501A (en) * | 2014-06-26 | 2014-09-17 | 北京航空航天大学 | Low-complexity multi-ary LDPC decoding method |
| CN106936444A (en) * | 2015-12-29 | 2017-07-07 | 北京航空航天大学 | One kind set interpretation method and set decoder |
| WO2018015325A1 (en) * | 2016-07-21 | 2018-01-25 | Koninklijke Philips N.V. | Device and method for performing obfuscated arithmetic |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112650863A (en) * | 2020-12-01 | 2021-04-13 | 深圳力维智联技术有限公司 | Cross-media data fusion method, device and storage medium |
Also Published As
| Publication number | Publication date |
|---|---|
| CN111384975B (en) | 2023-05-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10491239B1 (en) | Large-scale computations using an adaptive numerical format | |
| US11249721B2 (en) | Multiplication circuit, system on chip, and electronic device | |
| EP4328744A2 (en) | Computer processor for higher precision computations using a mixed-precision decomposition of operations | |
| KR20210096679A (en) | Neural networks and systems for decoding encoded data | |
| EP4258135A1 (en) | Matrix calculation apparatus, method, system, circuit, chip, and device | |
| CN114640354B (en) | Data compression methods, apparatus, electronic devices and computer-readable storage media | |
| CN116594589A (en) | Method, device and arithmetic logic unit for multiplication calculation of floating-point numbers | |
| CN115827555B (en) | Data processing method, computer device, storage medium, and multiplier structure | |
| CN111384972B (en) | Optimization method, device and decoder of multi-system LDPC decoding algorithm | |
| CN111384975A (en) | Optimization method and device of multi-system LDPC decoding algorithm and decoder | |
| CN111384971B (en) | Data processing method, device and decoder in finite fields | |
| US20250103295A1 (en) | Method for processing feature data through multiply-accumulate array | |
| CN111384974B (en) | Confidence quantization method, device and decoder for multi-system LDPC code | |
| AU2020425196B2 (en) | Secure computation apparatus, secure computation method, and program | |
| CN105302520B (en) | Reciprocal operation solving method and reciprocal operation solving system | |
| CN118573189A (en) | Adaptive quantization coding method, device, equipment and storage medium | |
| CN118713678A (en) | A data compression method, a decompression method, a bit width determination method and a system | |
| US20170302933A1 (en) | Method of coding a real signal into a quantized signal | |
| CN111224674B (en) | Decoding method, device and decoder for multi-system LDPC code | |
| CN113919289B (en) | Bitcoin wallet address string encoding method and address number table generation method | |
| CN114207609B (en) | Information processing device, information processing system and information processing method | |
| CN111384973B (en) | Optimization method, device and decoder of multi-system LDPC decoding algorithm | |
| WO2023024796A1 (en) | Data compression/decompression method and communication apparatus | |
| CN117200800A (en) | Data compression method, device, equipment and storage medium | |
| CN119512438B (en) | A data compression method and a data decompression method |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |