CN113556133B - Mixed decoding method and device for CRC-Polar cascade codes - Google Patents
Mixed decoding method and device for CRC-Polar cascade codes Download PDFInfo
- Publication number
- CN113556133B CN113556133B CN202110660278.1A CN202110660278A CN113556133B CN 113556133 B CN113556133 B CN 113556133B CN 202110660278 A CN202110660278 A CN 202110660278A CN 113556133 B CN113556133 B CN 113556133B
- Authority
- CN
- China
- Prior art keywords
- crc
- polar
- decoder
- information
- likelihood ratio
- 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.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 61
- 239000013598 vector Substances 0.000 claims description 42
- 238000004364 calculation method Methods 0.000 claims description 27
- 230000007704 transition Effects 0.000 claims description 6
- 238000012163 sequencing technique Methods 0.000 claims description 2
- 238000004891 communication Methods 0.000 abstract description 3
- 238000004422 calculation algorithm Methods 0.000 description 59
- 241000169170 Boreogadus saida Species 0.000 description 6
- 238000010586 diagram Methods 0.000 description 3
- 230000009191 jumping Effects 0.000 description 3
- 238000012986 modification Methods 0.000 description 3
- 230000004048 modification Effects 0.000 description 3
- 238000006467 substitution reaction Methods 0.000 description 3
- 125000004122 cyclic group Chemical group 0.000 description 2
- 239000000463 material Substances 0.000 description 2
- 238000010420 art technique Methods 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 238000000354 decomposition reaction Methods 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000013507 mapping Methods 0.000 description 1
- 239000011159 matrix material Substances 0.000 description 1
- 238000012216 screening Methods 0.000 description 1
- 238000004088 simulation Methods 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
- 239000002699 waste material Substances 0.000 description 1
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/09—Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
-
- 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/13—Linear codes
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
Abstract
The invention discloses a mixed decoding method and a device for CRC-Polar cascade codes, wherein the method comprises the following steps: encoding at an encoding end by adopting CRC-pol ar cascade codes; after receiving information to be decoded, calling a Fano decoder to decode the information to be decoded, and determining the updating times of the log likelihood ratio in the decoding process; judging whether the updating times are greater than a times threshold value, if yes, calling an SC decoder to decode the rest information bits, and further obtaining a complete codeword; otherwise, the complete codeword is determined according to the result of the CRC check. The invention reduces the storage cost and the computation complexity, reduces the time delay and can be widely applied to the technical field of communication.
Description
Technical Field
The invention relates to the technical field of communication, in particular to a mixed decoding method and device for CRC-Polar cascade codes.
Background
Channel coding is an important component of a communication system, and adds a certain redundancy to the transmitted information to acquire the capability of correcting errors. The channel coding is various and has different application scenes. Polar codes are used as a first coding scheme which is theoretically proved to be capable of approaching the shannon limit, and have excellent decoding performance under the condition of long code length. However, when the code length of the code is reduced to a middle-short range, the pure Polar code has poor performance due to poor codeword distance characteristics and the like. Concatenating with a cyclic redundancy check (Cyclic Redundancy Check, CRC) may effectively improve this situation, such concatenated code structure is also known as CRC-polar concatenated code.
The current decoding algorithm for CRC-Polar concatenated codes is mainly a successive erasure list decoding algorithm (Successive Cancellation, SCL). The algorithm obtains better bit error rate performance by generating a path list of a plurality of possible codewords and then screening the list by using CRC. But this algorithm requires storage of multiple paths in the decoding process and therefore requires additional storage costs. Meanwhile, the bit error rate performance of the algorithm is related to the size of the list, and a larger list size is required to obtain the ideal performance, which also means a larger computational complexity.
There are also related art techniques that use the concept of successive cancellation bit flipping algorithms (Successive Cancellation Filpping, SCF) in combination with Fano algorithm to decode CRC-Polar concatenated codes. The algorithm controls the complexity by controlling the number of the flip bits, but due to the characteristics of the Fano algorithm, the algorithm has the defect of uncontrollable time delay and complexity under the condition of poor channel conditions.
Disclosure of Invention
In view of this, the embodiments of the present invention provide a hybrid decoding method and apparatus for CRC-Polar concatenated codes to reduce latency and complexity.
An aspect of the present invention provides a hybrid decoding method for a CRC-Polar concatenated code, including:
encoding at an encoding end by adopting CRC-Polar cascade codes;
after receiving information to be decoded, calling a Fano decoder to decode the information to be decoded, and determining the updating times of the log likelihood ratio in the decoding process;
judging whether the updating times are greater than a times threshold value, if yes, calling an SC decoder to decode the rest information bits, and further obtaining a complete codeword; otherwise, the complete codeword is determined according to the result of the CRC check.
Optionally, the encoding with the CRC-Polar cascade code at the encoding end includes:
Acquiring an information vector;
encoding the information vector to obtain a CRC codeword polynomial;
determining a message vector and a codeword vector of the CRC-Polar concatenated code;
Sequencing the reliability of a plurality of polarized channels of the message vector by adopting a Gaussian approximation method;
determining a freeze bit and a fixed bit in the message vector according to the ordering order of the reliability;
and filling the frozen bit and the fixed bit according to the CRC code word polynomial to obtain a complete message vector.
Optionally, after receiving the information to be decoded, invoking a Fano decoder to decode the information to be decoded, and determining the update times of the log-likelihood ratio in the decoding process, including:
After receiving the information to be decoded, configuring the step length, the initial threshold value and the frequency threshold value of the Fano decoder;
calculating the update times of the log likelihood ratio in the decoding process of the Fano decoder according to the step length and the initial threshold value;
The updated calculation formula of the log likelihood ratio is as follows:
Or (b)
Wherein,
α,/> Representing generation decoding information of 1 st to N th; /(I)Representing the estimated message vectors of 1 to i,/>Respectively represent/>Odd and even terms of (a); /(I)Adding the representative model 2; /(I)Representing the calculation result of the log likelihood ratio of the ith message vector corresponding to the polar code with the code length of N.
Optionally, the method further comprises:
calculating the likelihood ratio of the conditional transition probability corresponding to the message vector according to the log likelihood ratio;
According to the calculation result of the likelihood ratio, carrying out iterative updating on the log likelihood ratio;
Converting the iterative updating result of the log-likelihood ratio into posterior probability;
and calculating to obtain a path value of the Fano decoder according to the posterior probability.
Optionally, the path ratio of the Fano decoder is determined by a method of density evolution and gaussian approximation;
The calculation formula of the path value is as follows:
Wherein, Representing the path value; /(I)For/>Error probability of (2);
Optionally, the method further comprises:
Expanding the target path according to the size of the path value;
Or alternatively
And according to the size of the path value, carrying out rollback operation on the decoder so as to traverse the father node of the current node, obtaining a target node meeting the preset condition, and expanding the path corresponding to the target node.
Optionally, during the expanding process or the rollback operation, the method includes:
dynamically updating a target threshold according to the step length of the Fano decoder;
In particular, the method comprises the steps of,
In the expansion process, when the path value is larger than the target threshold value, performing first update on the target threshold value according to the step length of the Fano decoder;
And in the rollback process, when the maximum value of the path value is smaller than the target threshold value, performing second updating on the target threshold value according to the step length of the Fano decoder.
Optionally, in the extending process, when extending to a leaf node, an estimated vector is extracted from the message vector, and CRC encoding is performed on the estimated vector to determine to output the estimated vector.
Another aspect of an embodiment of the present invention provides a hybrid decoding apparatus for a CRC-Polar concatenated code, including:
the first module is used for encoding at the encoding end by adopting CRC-Polar cascade codes;
the second module is used for calling the Fano decoder to decode the information to be decoded after receiving the information to be decoded, and determining the updating times of the log likelihood ratio in the decoding process;
A third module, configured to determine whether the update number is greater than a number threshold, and if yes, call an SC decoder to decode the remaining information bits, thereby obtaining a complete codeword; otherwise, the complete codeword is determined according to the result of the CRC check.
Another aspect of an embodiment of the present invention provides an apparatus comprising computer instructions stored in a computer-readable storage medium; the computer instructions may be read by a processor of a computer device from a computer readable storage medium and executed by the processor to perform the hybrid decoding method for CRC-Polar concatenated codes described previously.
The embodiment of the invention adopts CRC-Polar cascade codes to code at the coding end; after receiving information to be decoded, calling a Fano decoder to decode the information to be decoded, and determining the updating times of the log likelihood ratio in the decoding process; judging whether the updating times are greater than a times threshold value, if yes, calling an SC decoder to decode the rest information bits, and further obtaining a complete codeword; otherwise, the complete codeword is determined according to the result of the CRC check. The invention reduces the storage cost and the calculation complexity and reduces the time delay.
Drawings
In order to more clearly illustrate the technical solutions of the embodiments of the present application, the drawings required for the description of the embodiments will be briefly described below, and it is apparent that the drawings in the following description are only some embodiments of the present application, and other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.
Fig. 1 is a schematic diagram of a decoder in a hybrid decoding algorithm according to an embodiment of the present invention;
FIG. 2 is a diagram of a CRC-Polar concatenated code frame error rate according to an embodiment of the present invention;
FIG. 3 is a chart of the average computation complexity of CRC-Polar concatenated codes according to an embodiment of the present invention;
fig. 4 is an SC decoding butterfly diagram provided in an embodiment of the present invention;
FIG. 5 is a flowchart of an SC decoding algorithm code tree provided by an embodiment of the present invention;
fig. 6 is a flowchart of a Fano decoding algorithm code tree according to an embodiment of the present invention.
Detailed Description
The present application will be described in further detail with reference to the drawings and examples, in order to make the objects, technical solutions and advantages of the present application more apparent. It should be understood that the specific embodiments described herein are for purposes of illustration only and are not intended to limit the scope of the application.
Aiming at the problems existing in the prior art, the Fano algorithm is combined with the SC algorithm, and the method which takes the update times of the log likelihood ratio (Logarithm Likelihood Ratio, LLR) in the calculation process as the control condition realizes the purposes of low storage cost, low calculation complexity and controllable maximum time delay.
The specific implementation principle of the invention is described in detail below with reference to the drawings of the specification:
The SC decoding algorithm is combined with the Fano decoding algorithm, and a hybrid decoding algorithm for CRC-polar concatenated codes is proposed herein. In order to improve the performance of the middle short code, the scheme selects CRC-Polar cascade codes at the coding end to code. When the receiving end receives the received symbol When it is decoded by the Fano decoder. Unlike the conventional Fano decoder, the decoding result is not directly output when the decoder reaches a leaf node. Instead, the CRC check is performed first, if the CRC check passes, the result is output, and if the CRC check does not pass, the decoder will rollback and find another possible path. Meanwhile, in order that the inverse Fano decoder cannot find the correct path all the time and generate excessive computational complexity and time delay, an update frequency threshold value phi of the LLR value is introduced, wherein phi is set as eta times of the update frequency of the LLR value of one-time SC decoding, namely phi=eta nlogN, and the parameter is input in advance before decoding. In the decoding process, the mixed decoder counts the update times ρ of LLR values, and once the accumulated value exceeds Φ, the Fano decoder stops working, and the rest message bits are decoded by SC decoding, so that a complete decoding result is obtained.
The decoding flow of the receiving end is shown in fig. 1, fig. 1 shows an example of SC decoding, and for a Polar code with code length of 4, the receiving end receives the received symbolAfter that, the following operations were performed:
First calculate out
By means ofThe update is calculated and updated through twice f + to obtain/>, respectively/>
By means of/>Update by one f + calculationAnd making a decision to obtain an estimated symbol/>
By means of/>Estimated symbol/>Calculated by f + once to obtain/>And making a decision to obtain an estimated symbol/>
And the like, respectively and sequentially obtaining by updating operation Is a value of (2);
obtaining a complete message estimation vector And (5) finishing decoding.
In summary, the invention receives at the receiving endWhen the decoder performs the following operations:
(1) Invoking a Fano decoder to decode, and counting the update times rho of LLR in the decoding process;
(2) Calling the SC decoder to decode the rest information bit once ρ > Φ, and jumping to (4);
(3) Performing a CRC check once the leaf node is reached;
A. if the CRC check is met, jumping to (4);
B. if the CRC check is not met, carrying out rollback and jumping to (1);
(4) Outputting the complete code word.
The specific flow is as follows:
Receiving end receives Setting a Fano step delta, a Fano initial threshold T and an LLR update times threshold phi. Φ is set to η times the number of LLR value updates for one SC decoding, i.e., Φ=ηnlogn. In this scheme, generally, Δ=1, t=0, Φ is set according to the requirement, and a larger Φ corresponds to better performance, which means higher computational complexity and time delay.
(1) Through type son
Where u 1 represents a message vector when=1; y i represents the i-th information to be decoded; a calculation result representing the log likelihood ratio of the 1 st message vector corresponding to the polar code with the code length of 1; p () represents the channel condition transition probability.
And calculating LLR of the receiving end.
(2) By iteratively updating LLR at the receiving end
And calculating the likelihood ratio of the conditional transition probability corresponding to u i.
The number of updates of the LLR value is increased by one for each calculation, i.e., ρ=ρ+1. Once ρ > Φ, jump to (6).
(3) Converting the LLR results into posterior probabilities (a posteriori probability, APP)
And calculate the path value required by Fano decoding
Wherein, The values of (2) can be obtained by a density evolution and Gaussian approximation method:
Wherein Q (·) is defined as follows:
The value of (2) may be obtained by the following iterative calculation:
Initial value of iteration An initial value for a signal-to-noise ratio of 0dB is constructed corresponding to the Gaussian approximation, wherein δ (·) is defined as follows:
(4) If (if) Will/>/>Compared to a threshold T.
A. If the larger of the two values satisfiesThe decoder will select the path with the larger value for expansion;
B. If the larger of the two values satisfies It means that neither current choice is ideal and the decoder will generate a rollback operation, i.e. traverse the parent node/>, of the current node again near and far0.Ltoreq.j < i, searching for a node satisfying the following two conditions:
1) The smaller of the two values of the node satisfies
2) The path corresponding to the smaller value of the node has not been extended.
When a node meeting the condition is found, the path corresponding to the smaller value of the node is expanded.
During the expansion and rollback process, the threshold T will be based onIs dynamically changed according to the step length.
A. during the expansion process, ifThen t=t+hΔ, h is such that the updated T satisfiesIs an integer of (a).
B. During rollback, ifThen t=t- Δ
C. If the back-off is to the start point, t=t- Δ
(5) If extended to leaf node, i.e. i=n, fromExtracting estimated vector/>, from k+k 1 information bitsI.e. where the former K is/>To estimate information vector/>Post K 1 is CRC check bit/>Will/>CRC encoding
Wherein g (x) is a CRC generator polynomial, and the CRC check code used in the present design is 8 bits long, and the corresponding generator polynomial is g (x) =x 8+x2 +x+1. Comparison/>If they are equal, it is stated that the decoding result can pass the CRC check, then the method will/>And (4) outputting, if the operation is not performed, performing a rollback operation, wherein the rollback operation is the same as that in (4).
(6) If ρ > Φ, only the likelihood ratio of the conditional transition probability corresponding to u i is calculated, based on the value pairAnd (3) estimating:
the operation is cycled until i=n. Obtaining complete estimated message sequence Extracting estimated information vector from the vectorAnd output.
To justify the advantages of this scheme, the following gives the relevant simulation results for (128,64) Polar codes, which are pure Polar codes for the SC algorithm and Fano algorithm, and for SCL and the Hybrid algorithm proposed herein (128,64) CRC-Polar concatenation code with CRC length 8. Wherein the average computational complexity is normalized by dividing ρ by NlogN.
Referring to fig. 2 and 3, fig. 2 shows Frame Error Rate (FER) curves for different decoding algorithms. It can be seen that the performance of the hybrid algorithm increases as the threshold for the number of LLR updates increases. For (128,64) CRC-Polar concatenated codes, when η=16, the performance of the hybrid decoding is better than that of SC decoding algorithm and Fano decoding algorithm. When η=64, the performance of the hybrid decoding is better than that of the SCL decoding algorithm (l=16). Figure 3 shows the average computational complexity of the different algorithms. It can be seen that as the SNR increases, the computational complexity of the hybrid decoding algorithm and Fano algorithm decreases. The computational complexity of the hybrid coding algorithm is much lower than SCL (l=16) and is close to that of SC coding at higher SNR.
In summary, the present invention is a hybrid decoding algorithm for CRC-Polar concatenated codes based on SC decoding and Fano decoding. The algorithm controls the switching between algorithms by the update times of LLR. Compared with other algorithms, the algorithm has the following advantages:
(1) Compared with the conventional SC algorithm without CRC and the Fano algorithm, the performance of the algorithm is obviously improved.
(2) Compared with an SCL algorithm commonly used for CRC-Polar cascade codes, the algorithm only needs to store one path, and has the advantage of low storage cost.
(3) Compared with the SCL algorithm commonly used for CRC-Polar cascade codes, the algorithm can achieve the same decoding performance and simultaneously requires much less calculation complexity than the SCL algorithm.
(4) Compared with the Fano algorithm, the maximum time delay of the algorithm is controllable, and when the quality of certain frame information is too bad, the algorithm can be terminated in advance, so that the waste of excessive computing resources is avoided.
(5) The algorithm parameter is flexible to adjust, and the LLR updating frequency threshold value can be set according to the target decoding performance, so that the overall calculation complexity is controlled.
In addition, the implementation process of the related technical means in the present invention is further described in this embodiment:
1. Encoding of CRC-Polar concatenated codes:
For an (N, K) CRC-Polar concatenated code, where n=2 n, the inner code is an (N, k+k 1) Polar code and the outer code is a (k+k 1, K) CRC codeword. Given information vector Its corresponding polynomial expression is: m (x) =m 1+m2x+…+mKxK-1. Encoding the information vector to obtain a corresponding CRC codeword polynomial s (x) as follows:
Wherein g (x) is a CRC generator polynomial, and the CRC check code used in the present invention is 8 bits long, and the corresponding generator polynomial is g (x) =x 8+x2 +x+1. Is provided with />A message vector and a codeword vector of the CRC-Polar concatenated code, respectively. The method of Gaussian approximation can be used for/>The reliability of the N corresponding polarized channels is sequenced, the most reliable front K+K 1 position is selected, and the corresponding subscript set is/>The remaining positions are freeze bits, and the subscript set is/>Filling the encoded CRC code words into/>Middle/>The corresponding position, other positions are fixed to 0, thus obtaining the complete message vector/>From this, the codeword of the CRC-Polar concatenated code is:
Wherein, For bit-flipping matrix,/>For/>Is the product of Cronecker for n times of F.
2. SC decoding algorithm
For code wordsBPSK modulation is carried out, and after channel transmission, a receiving end receives symbols as followsLet the estimated message vector be/>In the decoding process, if the translated position is a frozen bit, i.e./>It is judged as 0. If it is an information bit, i.e./>Then the corresponding LLR value is calculated:
Wherein the method comprises the steps of Is the channel condition transition probability. From this value can be paired/>And (3) estimating:
The LLR values described above may be iteratively calculated by a butterfly structure. As shown in fig. 4, fig. 4 represents an SC-decoded butterfly (n=4), a dashed arrow represents f + calculation, and a solid arrow represents f - calculation.
The butterfly of fig. 4 has a total of n+1 columns, each with N LLR values. Wherein,The LLR value of the ith symbol u i representing a polar code of code length N. It can be calculated by LLR values of two polar codes with a code length of N/2. By analogy, for a polar code with a code length of N, N polar codes with a code length of 1 can be disassembled through log 2 N decomposition operations, and their LLR values can be directly obtained through the received symbols at the receiving end:
Before introducing the specific calculation of LLR, two calculation symbols are defined:
wherein, alpha is the same as alpha, />The LLR value update procedure in the butterfly graph may be expressed as:
Wherein, />Respectively represent/>Odd and even terms of (a). Each call of the above equation (one calculation of f + or f _) is called one update of the LLR value. In the invention, the update count is used as the basis for algorithm switching. It can be seen that one SC decoding algorithm requires N log 2 LLR value updating operations.
As shown in the SC decoded butterfly graph, where the value of each node is a log-likelihood ratio (log likelihood ratio, LLR), the formula can be used
The representation is performed.
3. Code tree representation for SC decoding procedure
Assume thatEvenly distributed in {0,1}, then the posterior probability (a posteriori probability, posterior probability)/>The following formula is satisfied:
Wherein, The values of (2) may be obtained by updating the LLR values. Meanwhile, the SC decoding algorithm can be represented in the form of a code tree.
For a polar code of code length N, the code tree is a binary tree of depth n+1, and there are a total of 2 N leaf nodes. Fig. 5 shows a flow chart of the SC decoding algorithm code tree for a polar code of code length n=4, which, in this example, Wherein the numbers beside the nodes represent the posterior probability values of the path, and the numbers on the arrows represent the values of u i. In the coding process, for/>The decoder will first determine the received vector/>The previous decoding result/>Calculation/>/>And then selecting one side with a larger posterior probability value for expansion, wherein the expansion direction is the decoding result of u i. And sequentially expanding until a complete path from the root node to the leaf node is obtained, wherein the value represented on the path is the final decoding result.
4. Fano decoding algorithm
The Fano algorithm introduces the concept of a path value, which judges whether the current path is good or bad or not and whether the current path is worth expanding by comparing the posterior probability accumulated value of the current path with the accumulated value of the theoretical optimal path. Its path valueThe calculation formula of (2) is as follows:
Its initial value Wherein/>For/>Can be obtained by means of density evolution and gaussian approximation. Each path value calculation requires an update calculation of the LLR value. In order to measure whether the path is worth expanding, two new parameters need to be introduced, namely a threshold T and a step delta, wherein the threshold T dynamically changes according to the step delta, namely T epsilon {0, ±delta, ±2 delta, … }. In the decoding process, for each/> There are two values/>AndThe decoder compares it with a threshold T.
(1) If the larger of the two values satisfiesThe decoder will select the path with the larger value for expansion;
(2) If the larger of the two values satisfies It means that neither current choice is ideal and the decoder will generate a rollback operation, i.e. traverse the parent node/>, of the current node again near and far0.Ltoreq.j < i, searching for a node satisfying the following two conditions:
A. The smaller of the two values of the node satisfies
B. The path corresponding to the smaller value of the node has not been extended yet.
When a node meeting the condition is found, the smaller value of the node is expanded.
During the expansion and rollback process, the threshold T will be based onIs dynamically changed according to the step length.
A. during the expansion process, ifThen t=t+hΔ, h is such that the updated T satisfiesIs an integer of (a).
B. During rollback, ifThen t=t- Δ
C. If the back-off is to the start point, t=t- Δ
Once the decoder is extended to the leaf node, a complete path is obtained, the decoder stops decoding, and the result corresponding to the complete path is the final decoding result.
Mapping the path values to the code tree can result in a code tree representation of the Fano decoding algorithm flow. Fig. 6 shows a flow chart of the Fano decoding algorithm code tree for polar codes with a code length of n=4, which, in this example,Threshold t= -4, step size Δ=4. Wherein the numbers beside the nodes represent the path values of the path, and the numbers on the arrows represent the values of u i. When i=3, the/>, is calculated/>Satisfy the following requirementsSelect/>Is extended. Subsequent calculation/>Is found by the value of (2)At this time, the decoder rolls back to find/>Select/>Is extended. Followed by/>So far, the decoder is smoothly extended to the leaf node, the decoding is finished, and the decoding result is/>
The Fano decoder is a strategy for searching for global optimum by depth-first search, the performance of the algorithm is improved compared with that of SC, but the algorithm performs serial search in a code tree, and when the channel condition is poor or the code length is long, the algorithm may cause greater computational complexity and time delay, and affect the decoding of the next frame.
In the description of the present specification, a description referring to terms "one embodiment," "some embodiments," "examples," "specific examples," or "some examples," etc., means that a particular feature, structure, material, or characteristic described in connection with the embodiment or example is included in at least one embodiment or example of the present invention. In this specification, schematic representations of the above terms do not necessarily refer to the same embodiments or examples. Furthermore, the particular features, structures, materials, or characteristics described may be combined in any suitable manner in any one or more embodiments or examples.
While embodiments of the present invention have been shown and described, it will be understood by those of ordinary skill in the art that: many changes, modifications, substitutions and variations may be made to the embodiments without departing from the spirit and principles of the invention, the scope of which is defined by the claims and their equivalents.
While the preferred embodiment of the present application has been described in detail, the present application is not limited to the embodiments described above, and those skilled in the art can make various equivalent modifications or substitutions without departing from the spirit of the present application, and these equivalent modifications or substitutions are included in the scope of the present application as defined in the appended claims.
Claims (7)
1. A hybrid decoding method for CRC-Polar concatenated codes, comprising:
encoding at an encoding end by adopting CRC-Polar cascade codes;
after receiving information to be decoded, calling a Fano decoder to decode the information to be decoded, and determining the updating times of the log likelihood ratio in the decoding process;
judging whether the updating times are greater than a times threshold value, if yes, calling an SC decoder to decode the rest information bits, and further obtaining a complete codeword; otherwise, determining the complete code word according to the CRC result; the coding at the coding end by adopting CRC-Polar cascade codes comprises the following steps:
Acquiring an information vector;
encoding the information vector to obtain a CRC codeword polynomial;
determining a message vector and a codeword vector of the CRC-Polar concatenated code;
Sequencing the reliability of a plurality of polarized channels of the message vector by adopting a Gaussian approximation method;
determining a freeze bit and a fixed bit in the message vector according to the ordering order of the reliability;
filling the frozen bit and the fixed bit according to the CRC code word polynomial to obtain a complete message vector;
after receiving the information to be decoded, invoking a Fano decoder to decode the information to be decoded, and determining the update times of the log likelihood ratio in the decoding process, wherein the method comprises the following steps:
After receiving the information to be decoded, configuring the step length, the initial threshold value and the frequency threshold value of the Fano decoder;
calculating the update times of the log likelihood ratio in the decoding process of the Fano decoder according to the step length and the initial threshold value;
The updated calculation formula of the log likelihood ratio is as follows:
Or (b)
Wherein,
α,/> Representing generation decoding information of 1 st to N th; /(I)Estimated message vectors representing 1 st through i,/>/>Respectively represent/>Odd and even terms of (a); /(I)Adding the representative model 2; /(I)Representing the calculation result of the log likelihood ratio of the ith message vector corresponding to the polar code with the code length of N.
2. The hybrid decoding method for CRC-Polar concatenated codes of claim 1, further comprising:
calculating the likelihood ratio of the conditional transition probability corresponding to the message vector according to the log likelihood ratio;
According to the calculation result of the likelihood ratio, carrying out iterative updating on the log likelihood ratio;
Converting the iterative updating result of the log-likelihood ratio into posterior probability;
and calculating to obtain a path value of the Fano decoder according to the posterior probability.
3. The hybrid decoding method for CRC-Polar concatenated codes according to claim 2, characterized in that the path values of said Fano decoder are determined by means of density evolution and gaussian approximation;
The calculation formula of the path value is as follows:
Wherein, Representing the path value; /(I)For/>Is a function of the error probability of (1).
4. The hybrid decoding method for CRC-Polar concatenated codes of claim 3, further comprising:
Expanding the target path according to the size of the path value;
Or alternatively
And according to the size of the path value, carrying out rollback operation on the decoder so as to traverse the father node of the current node, obtaining a target node meeting the preset condition, and expanding the path corresponding to the target node.
5. The hybrid decoding method for CRC-Polar concatenated codes as claimed in claim 4, characterized in that in said extension process or back-off operation, it comprises:
dynamically updating a target threshold according to the step length of the Fano decoder;
In particular, the method comprises the steps of,
In the expansion process, when the path value is larger than the target threshold value, performing first update on the target threshold value according to the step length of the Fano decoder;
And in the rollback process, when the maximum value of the path value is smaller than the target threshold value, performing second updating on the target threshold value according to the step length of the Fano decoder.
6. The hybrid decoding method for CRC-Polar concatenated codes of claim 5, wherein in said expanding process, when expanding to leaf nodes, an estimated vector is extracted from said message vector, said estimated vector is CRC encoded to determine said estimated vector to be output.
7. An apparatus for applying the hybrid decoding method for CRC-Polar concatenated codes as claimed in any one of claims 1-6, comprising:
the first module is used for encoding at the encoding end by adopting CRC-Polar cascade codes;
the second module is used for calling the Fano decoder to decode the information to be decoded after receiving the information to be decoded, and determining the updating times of the log likelihood ratio in the decoding process;
A third module, configured to determine whether the update number is greater than a number threshold, and if yes, call an SC decoder to decode the remaining information bits, thereby obtaining a complete codeword; otherwise, the complete codeword is determined according to the result of the CRC check.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110660278.1A CN113556133B (en) | 2021-06-15 | 2021-06-15 | Mixed decoding method and device for CRC-Polar cascade codes |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110660278.1A CN113556133B (en) | 2021-06-15 | 2021-06-15 | Mixed decoding method and device for CRC-Polar cascade codes |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN113556133A CN113556133A (en) | 2021-10-26 |
| CN113556133B true CN113556133B (en) | 2024-05-28 |
Family
ID=78102092
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202110660278.1A Active CN113556133B (en) | 2021-06-15 | 2021-06-15 | Mixed decoding method and device for CRC-Polar cascade codes |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113556133B (en) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20240074523A (en) | 2022-11-21 | 2024-05-28 | 삼성전자주식회사 | Method and apparatus for performing pac code based hybrid decoding in wireless communication system |
| KR20240115015A (en) * | 2023-01-18 | 2024-07-25 | 삼성전자주식회사 | Method and apparatus for performing decoding based on fano decoding |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108494523A (en) * | 2018-01-31 | 2018-09-04 | 北京航空航天大学 | A kind of more CRC coding methods of Polar codes |
| CN110278002A (en) * | 2019-06-19 | 2019-09-24 | 东南大学 | Polarization code belief propagation list decoding method based on bit reversal |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20210006807A (en) * | 2019-07-09 | 2021-01-19 | 삼성전자주식회사 | Apparatus and method to transmit and receive signal in communication system |
-
2021
- 2021-06-15 CN CN202110660278.1A patent/CN113556133B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108494523A (en) * | 2018-01-31 | 2018-09-04 | 北京航空航天大学 | A kind of more CRC coding methods of Polar codes |
| CN110278002A (en) * | 2019-06-19 | 2019-09-24 | 东南大学 | Polarization code belief propagation list decoding method based on bit reversal |
Non-Patent Citations (1)
| Title |
|---|
| "基于5GeMBB场景下极化码译码及实现技术研究";冯旺;《中国优秀硕士学位论文全文数据库》;20190609;正文第1-78页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN113556133A (en) | 2021-10-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109660264B (en) | High performance polar code decoding algorithm | |
| USRE44421E1 (en) | Decoding apparatus for low-density parity-check codes using sequential decoding, and method thereof | |
| CN106506009B (en) | Decoding method of polarization code | |
| CN106803759A (en) | Polar yards of effective adaptive decoding method based on Gauss construction | |
| KR20090072972A (en) | Method and device for decoding low density parity check code | |
| CN107612560B (en) | Polarization code early iteration stopping method based on partial information bit likelihood ratio | |
| CN113556133B (en) | Mixed decoding method and device for CRC-Polar cascade codes | |
| CN113098530B (en) | LDPC code decoding method based on average cluster residual dynamic scheduling selection strategy | |
| CN107565978B (en) | BP decoding method based on Tanner graph edge scheduling strategy | |
| CN110661533B (en) | Method for optimizing decoding performance of decoder for storing polarization code | |
| CN107911195A (en) | A kind of tail-biting convolutional code channel decoding method based on CVA | |
| CN112332864B (en) | Polarization code decoding method and system for self-adaptive ordered mobile pruning list | |
| Lu et al. | Deep learning aided SCL decoding of polar codes with shifted-pruning | |
| US20210242885A1 (en) | Ldpc decoding method and ldpc decoding apparatus | |
| CN113131950A (en) | Self-adaptive continuous elimination priority decoding method for polarization code | |
| CN112737600A (en) | Decoding method and decoder | |
| Hadi et al. | A method to enhance the performance of successive cancellation decoding in polar codes | |
| CN116614142A (en) | Combined decoding method based on BPL decoding and OSD decoding | |
| CN115694515A (en) | Neural network assisted polarization code decoding method and device based on key bits | |
| EP2605410A1 (en) | Channel decoding method and tail biting convolutional decoder | |
| KR101562220B1 (en) | Apparatus and method for decoding for non binary low density parity check incodeing | |
| JP7542972B2 (en) | Method for adaptively scaling correction values in decoding and decoder therefor | |
| CN106603083B (en) | Improved method based on LDPC code node residual degree belief propagation decoding | |
| Xi et al. | A polar code hybrid rate matching scheme | |
| CN111835363A (en) | LDPC code decoding method based on alternative direction multiplier 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 |