RS (12, 9) quick decoding method aiming at DMR standardTechnical Field
The invention belongs to the technical field of communication, and particularly relates to a RS (12, 9) quick decoding method aiming at a DMR standard.
Background
The wireless intercom is a professional wireless communication tool and has the characteristics of timely communication, convenient use, no consumption of communication cost, low operation cost and the like. The European Telecommunications Standards Institute (ETSI) proposed DMR (Digital Mobile Radio) a digital trunking communication standard in 2004, and compared with other trunking communication protocols, the DMR has advantages of high spectrum utilization, good communication quality, good security, and low cost of terminal equipment. In the DMR standard, a plurality of coding algorithms including Golay (20, 8), QR (16,7,6) and RS (12, 9) are included, for decoding an RS code, the conventional decoding algorithm needs to go through three steps, firstly, solving an error occurrence position by checking sub-entry correlation algorithm, such as Beriekamp Massey iterative algorithm and money search algorithm, then solving an error difference value by checking sub-entry correlation algorithm through error position information, such as Forney algorithm, and finally obtaining a corrected RS code by xoring the received value of the position where the RS code error is located and the error difference value. However, for such error correction codes that correct only one bit as RS (12, 9), the ability of conventional algorithms to correct multi-bit codes is virtually unnecessary.
The prior art is suitable for solving various forms of RS codes, but for RS codes such as RS (12, 9) codes in the DMR standard and the like which only correct one dislocation, the decoding process of the prior art is too complicated, a large amount of computation resources are consumed, and the implementation of hardware is not facilitated.
The prior art documents to which reference is made are as follows, and it can be seen that the above-mentioned problems are all present:
[1] li Yuliang, li Jianhua, lan Wu, etc. an RS encoder and an RS encoding and decoding method [ P ]. Jiangxi province: CN202111469533.0,2022-03-08.
[2] Song Yangjun, lin Xiaokang. FPGA of DMR standard RS code encoder-decoder implements [ J ]. Communication technique, 2010,43 (06): 13-15.
[3] Yang Liangyong, bing. An implementation of an FPGA-based RS decoding method [ J ]. Electronic test, 2017, (15) 40-42.DOI:10.16520/J. Cnki.1000-8519.2017.15.019.
[4] J.square Zhang Guowei Low delay decoder for Reed-Solomon code [ P ]. Singapore: CN201710765440.X,2023-01-13.
For example, in the prior art scheme, an RS encoder and an RS encoding and decoding method
The technical scheme is that the method comprises 4 steps, wherein the first step is to calculate an accompanying polynomial and calculate error position polynomial coefficients according to the accompanying polynomial, the second step is to calculate the root of the error position polynomial according to the error position polynomial coefficients and Galois field element alpha, the third step is to generate an error position matrix according to the root of the error position polynomial, the fourth step is to calculate error positions according to the error position matrix and the accompanying polynomial, and finally, error correction is carried out according to the error positions and the root of the error position polynomial, decoded data is output, and error correction is completed.
Prior art scheme low delay decoder for reed-solomon codes
The scheme also calculates a syndrome, inputs the syndrome into a Key Equation Solver (KES) to iteratively solve an error positioning polynomial, calculates two values in parallel in each iteration to perform difference comparison, obtains new candidates from the difference, and performs iteration to finally obtain error information to realize error correction.
Disclosure of Invention
Therefore, aiming at the blank and the deficiency of the prior art, the invention provides a RS (12, 9) quick decoding method aiming at the DMR standard, aiming at the RS (12, 9) error correction code which is only used for correcting one dislocation, and by storing the information of the syndrome and the error position in a lookup table in advance, a large amount of calculation resources for solving error positioning are saved, the error correction efficiency of the RS (12, 9) is greatly improved, and the implementation of hardware circuits such as a Field Programmable Gate Array (FPGA) is facilitated.
The method comprises the steps of utilizing the characteristic that a syndrome itself contains error value information and error position information, and the characteristic that when an RS code corrects only one dislocation, the recurrence relation of the syndrome is only related to the position where an error occurs, is irrelevant to the value of the error, and the like, so that the recurrence relation of the syndrome corresponding to the error position can be stored in advance, when the RS code is received, if one bit of error occurs, the recurrence relation of the syndrome is only needed to be calculated, the error position is obtained through a table look-up mode, the error position information is substituted into the syndrome, the error difference value can be obtained, and finally the error difference value and the received RS code are subjected to exclusive or, so that the error-corrected RS code can be obtained. The invention can save a large number of algorithm processes for solving error position information and solving equations, realize the rapid decoding of RS (12, 9) codes with only one dislocation corrected in the DMR standard, save a large number of decoding resources and realize the rapid decoding performance compared with the traditional algorithm.
The technical scheme adopted for solving the technical problems is as follows:
A quick RS (12, 9) decoding method aiming at a DMR standard stores a recurrence relation of a syndrome corresponding to an error position in advance, when an RS code is received, if one bit is wrong, only the recurrence relation of the syndrome is needed to be calculated, the wrong position is obtained through a table look-up mode, wrong position information is substituted into the syndrome to obtain a wrong difference value, and finally the wrong difference value and the received RS code are subjected to exclusive OR to obtain an error-corrected RS code.
Further, before the RS (12, 9) is corrected, each syndrome ratio relation of 12 code element positions which are possibly in error is stored in an error position ratio table, when the RS (12, 9) is corrected, if the ratios among the syndromes are equal, a dislocation appears, the error is corrected, the error position ratio table is searched according to the ratio relation to obtain error position information, under the condition that the syndromes S1 and the error position j are obtained, the error pattern is directly obtained through calculation by means of the following formula, namely ej＝S1/2j, and finally, the value of the error position corresponding to the received data r (x) is exclusive-or with the error pattern ej, so that an error correction result is obtained.
Further, the method specifically comprises the following steps:
step one, storing the adjacent syndrome ratio relation value lambda of the RS (12, 9) when 1 bit error occurs into a lookup table, if the 1 st position error occurs, the corresponding ratio is lambda1, and so on, constructing the lookup table with 12 lambda values corresponding to 12 different positions when each bit error occurs;
Step two, receiving RS (12, 9) code element data, calculating syndromes, if the syndromes are all 0, indicating that the code element data has no error, if the syndromes are not all 0, calculating the ratio relation of adjacent syndromes, namely S3/S2 and S2/S1;
if the adjacent syndrome ratio values are not equal, the error exceeding 1 dislocation is indicated to occur, the error correction can be carried out, and the retransmission is applied or the error code element is discarded;
And fourthly, if the ratio of adjacent syndromes is equal, looking up a table in a lookup table to obtain an error position j, substituting ej＝S1/2j, solving to obtain an error pattern ej, and finally performing exclusive or on the data of the j-th position of the received code element data and the error pattern ej to obtain an error correction result, thereby completing error correction.
And a radio interphone system adopting the DMR standard, which adopts the RS (12, 9) rapid decoding method when in use.
An electronic device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, the processor implementing the steps of the RS (12, 9) fast decoding method for DMR standards as described above when the program is executed.
A non-transitory computer readable storage medium having stored thereon a computer program which, when executed by a processor, implements the steps of the RS (12, 9) fast decoding method for DMR standards as described above.
Compared with the prior art, the invention and the preferred scheme aim at RS (12, 9) error correction codes with only one bit error in the DMR standard, and realize the rapid decoding of the error correction codes according to the characteristic that the ratio relation between adjacent syndromes is only related to the error occurrence position.
Compared with the existing RS decoding algorithm, the application scene of the RS (12, 9) error correction code which is only used for correcting one bit in the DMR standard is more targeted, and the traditional RS decoding algorithm has the capability of correcting multiple bit errors, but consumes larger algorithm operation resources, and is excessively wasteful for the RS code which is only used for correcting one bit. The application proposes to realize two processes (searching for the error position and solving the error pattern) in the steps of the traditional RS decoding algorithm by skillfully utilizing the syndrome characteristics, and has the advantages of small algorithm resource consumption, high speed and the like.
Drawings
The invention is described in further detail below with reference to the attached drawings and detailed description:
FIG. 1 is a flowchart of RS (12, 9) decoding operations of an algorithm provided by an embodiment of the present invention.
Detailed Description
In order to make the features and advantages of the present patent more comprehensible, embodiments accompanied with figures are described in detail below:
It should be noted that the following detailed description is illustrative and is intended to provide further explanation of the application. Unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this application belongs.
It is noted that the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of exemplary embodiments according to the present application. As used herein, the singular is also intended to include the plural unless the context clearly indicates otherwise, and furthermore, it is to be understood that the terms "comprises" and/or "comprising" when used in this specification are taken to specify the presence of stated features, steps, operations, devices, components, and/or combinations thereof.
Considering that the traditional RS decoding algorithm has the capability of correcting the multi-dislocation RS code, but the consumed decoding resources are large, and the RS (12, 9) in the DMR standard only needs to correct one dislocation and does not need the capability of correcting the multi-dislocation of the traditional decoding algorithm.
In the RS (n, k) code, n is the code length, k is the information bit length, the code length of the RS (12, 9) is 12, the information bit length is 9, and the check bit length is 3, and the capability of detecting 3 dislocation and correcting 1 dislocation is provided. The RS code is expressed and calculated by using data of Galois Field (GF) finite Field with primitive element alpha of 2, and the addition and subtraction in Galois Field is bitwise exclusive or, and multiplication and division calculation can be realized by using an index table and an opposite table, so that the method is suitable for hardware circuit realization. For RS decoding, the received data can be represented by the following equation:
r(x)=s(x)+e(x)
where r (x) is the received symbol data, s (x) is the transmitted symbol data, which is the target of decoding, e (x) is the error pattern, containing error value information and error location information, as follows:
for RS (12, 9), n has a value of 12, and represents 12 symbol positions where errors may occur, ei represents an error value, xi represents error position information, and the main objective of the error correction algorithm is to solve e (x), and exclusive-or the received symbol data r (x) in the galois field to obtain corrected symbol data s (x), which is expressed as follows:
The generator polynomial of the RS code in the DMR standard is:
g(x)=x3+0e*x2+38*x+40
Since the information bits of the parity bits, i.e., the RS (12, 9), are divided by g (x) to obtain 3 remainders, it is known that the root of g (x) is the root of r (x) when the received symbol r (x) is correct. Because under the Galois field the roots of g (x) are 21、22 and 23, i.e., 2,4 and 8, then the roots of r (x) are likewise 2,4 and 8. The syndrome is obtained for r (x), that is, r (x) is basically substituted into the 3 roots, if the obtained 3 results are 0, it is indicated that r (x) has no error, and if the obtained 3 results are not 0, it is indicated that an error occurs, and it is necessary to perform error correction. In the case of an error in r (x) of RS (12, 9), the values of the three syndromes S1、S2 and S3 correspond to e (21)、e(22) and e (23), respectively, assuming that the j-th bit in r (x) is erroneous (j e [1,12 ]), the relationship of S1、S2 and S3 is as follows:
S1＝e(21)＝ej*(21)j
S2＝e(22)＝ej*(22)j
S3＝e(23)＝ej*(23)j
It can be found that the ratio of adjacent syndromes is equal when one dislocation occurs in the RS (12, 9), and the ratio is irrelevant to the error value, and is only relevant to the position where the error occurs, but when more than one dislocation occurs, the ratio is not relevant, i.e. when S3/S2≠S2/S1 occurs, multiple dislocations are generated, and error correction cannot be performed.
The key of the implementation of the scheme of the invention is that each syndrome ratio relation of 12 positions is stored in an error position ratio table before the RS (12, 9) is corrected, when the RS (12, 9) is corrected, if the syndrome ratio is equal, a dislocation appears, the error correction can be carried out, and the error position ratio table is searched according to the ratio relation to obtain error position information. Meanwhile, under the condition of one dislocation, the method for solving the error pattern is very simple, under the condition of obtaining S1 and the error position, the error pattern ej＝S1/2j saves the algorithm resource for solving the error pattern ej in the traditional algorithm, and finally, the error correction result can be obtained by carrying out exclusive or on the value of the error position corresponding to r (x) and the error pattern ej.
As shown in fig. 1, the present embodiment provides a design of an RS (12, 9) fast decoding method for DMR standard, and the implementation process includes the following steps:
Step one, the adjacent syndrome ratio relation value lambda of the RS (12, 9) when 1 bit error occurs is stored in a lookup table, if the 1 st position error occurs, the corresponding ratio is lambda1, and the lookup table is provided with 12 lambda values (lambda1、λ2......λ12) corresponding to 12 different positions when each bit error occurs.
And step two, receiving the RS (12, 9) code element data, calculating the syndromes, if all the syndromes are 0, indicating that the code element data has no error, and if the syndromes are not 0, calculating the ratio relation of adjacent syndromes, namely S3/S2 and S2/S1.
And step three, if the adjacent syndrome ratio is equal, indicating that 1 dislocation appears and error correction can be performed, and switching to step four for error correction. If the adjacent syndrome ratios are not equal, it is indicated that errors exceeding 1 bit occur, the error correction cannot be performed, and retransmission is applied or the error symbol is discarded.
And fourthly, if the ratio of adjacent syndromes is equal, looking up a table in a lookup table to obtain an error position j, substituting ej＝S1/2j, solving to obtain an error pattern ej, and finally performing exclusive or on the data of the j-th position of the received code element data and the error pattern ej to obtain an error correction result, thereby completing error correction.
It will be appreciated by those skilled in the art that embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.
The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the application. It will be understood that each flow and/or block of the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
It is to be noted that unless otherwise defined, technical or scientific terms used herein should be taken in a general sense as understood by one of ordinary skill in the art to which the present invention belongs. The terms "first," "second," and the like, as used herein, do not denote any order, quantity, or importance, but rather are used to distinguish one element from another. The word "comprising" or "comprises", and the like, means that elements or items preceding the word are included in the element or item listed after the word and equivalents thereof, but does not exclude other elements or items. The terms "connected" or "connected," and the like, are not limited to physical or mechanical connections, but may include electrical connections, whether direct or indirect. "upper", "lower", "left", "right", etc. are used merely to indicate relative positional relationships, which may also be changed when the absolute position of the object to be described is changed.
The above description is only a preferred embodiment of the present invention, and is not intended to limit the invention in any way, and any person skilled in the art may make modifications or alterations to the disclosed technical content to the equivalent embodiments. However, any simple modification, equivalent variation and variation of the above embodiments according to the technical substance of the present invention still fall within the protection scope of the technical solution of the present invention.
The present patent is not limited to the above-mentioned best mode, any person can obtain other various forms of RS (12, 9) fast decoding method aiming at DMR standard under the teaching of the present patent, and all equivalent changes and modifications made according to the claims of the present application shall be covered by the present patent.