TW201029339A - Method of decoding Golay code and decoder - Google Patents

Abstract

A method of decoding Golay code comprises the following steps: (a) receiving a binary sequence; (b) computing a first syndrome vector according to the binary sequence and a first auxiliary verification matrix; (c) computing a second syndrome vector according to the binary sequence and a second auxiliary verification matrix; (d) computing a first extended syndrome vector, a second extended syndrome vector, a third extended syndrome vector, and a fourth extended syndrome vector according to the first and second syndrome vectors and the first and second auxiliary verification matrixes; (e) computing the weights corresponding to the first and second syndrome vectors and the first, second, third and fourth extended syndrome vectors; (f) performing condition judgment according to the weights so as to determine an error position vector; and (g) finding the corresponding original data by decoding according the error position vector and the binary sequence.

Description

201029339 VI. Description of the Invention: [Technical Field] The present invention relates to a decoding technique of a quadratic residue (QR) code, and more particularly to a decoding method and decoder for a Golay code. [Prior Art] In recent years, there has been an increasing demand for reliability of signal transmission from consumer electronics to communication electronics; therefore, error detection and correction mechanisms are becoming increasingly important. In the digital communication process, in order to ensure the correctness of the original data to be transmitted, the transmitting end generally adds redundant data to the original data, and the receiving end can perform error correction based on the redundant data. Since the binary square residual code has a good correcting ability for errors generated in the transmission channel, it has become one of the most popular channel coding methods, and is currently a satellite communication system, a digital television system, and each An error correction code (Error Correction Code) widely used in digital video recording media. Among them, (23,12, 7) Gray code is a well-known binary square residual code. The existing decoding methods mainly include algebraic algorithms, Euclid algorithms, and step-by-step decoding algorithms. These algorithms have long delays in operation ( Long time delay ), high complexity, low regularity, and high gate count are difficult to implement and costly. SUMMARY OF THE INVENTION 201029339 Accordingly, it is an object of the present invention to provide a decoding method for Gray code. Therefore, the decoding method of the Gray code of the present invention comprises the following steps: (a) receiving a binary sequence; (b) receiving the binary sequence according to the received one, and a predefined first auxiliary school Determining a first symptom vector according to the matrix; (determining a second symptom vector according to the received two-bit sequence and a predefined second auxiliary check matrix; (d) according to the a first symptom vector, the second symptom vector, and the first auxiliary check matrix, the second auxiliary check matrix, and determining a first extended symptom vector, a plurality of second extended symptom vectors, and a plurality of third extensions a symptom vector, and a plurality of fourth extended symptom vectors; (e) respectively determining a corresponding first symptom vector, the second symptom vector, the first extended symptom vector, the second extended symptom vector, the third Extending the symptom vector, and a plurality of weight values of the fourth extended symptom vector; ^ f) performing conditional judgment based on the weight values to determine an error position vector: and (g) according to the error position And the two received sequence of bits of a decoded data corresponding to the original. Another object of the present invention is to provide a Gray code decoder.疋 'The Gray code grammar of the present invention' comprises a data buffer storage unit, a symptom vector calculation unit, an extended symptom vector calculation unit, a weight value calculation unit, an error position vector decision unit, and a Arithmetic unit. The resource buffer storage unit is configured to store a received binary sequence. The symptom vector calculation unit is configured to obtain a first symptom vector according to the binary sequence and a first auxiliary check matrix defined in advance 201029339, and to use the predefined sequence according to the binary sequence The second auxiliary check matrix finds a second symptom vector. The extended symptom vector calculation unit is configured to obtain a first extended symptom vector and a plurality of second according to the first symptom vector, the second symptom vector, the first auxiliary check matrix, and the second auxiliary check matrix. The extended symptom vector, the plurality of third extended symptom vectors, and the plurality of fourth extended symptoms to #. The (four) value calculation unit is configured to respectively obtain a corresponding '•Hui symptom vector, the second symptom vector, the first extended symptom to β 4, the second extended symptom vector, the third extended symptom vector, and The plurality of weight values of the fourth extended symptom vector. The error position vector decision block 70 is used for conditional judgment based on the weight values to determine an error position vector. The operation unit is configured to decode a corresponding original data according to the error location vector and the received binary sequence. The effect of the invention is that the error location vector is determined by the condition of the weight value, and the original data is obtained according to the condition; not only can the Gray code be efficiently decoded, but also the operation complexity, The required number of gates Φ and cost are significantly lower than the existing algorithms 'suitable for hardware implementation. The above and other technical contents, features, and advantages of the present invention will be apparent from the following detailed description of the preferred embodiments. Referring to FIG. 1, a preferred embodiment of the Gray code decoder i of the present invention comprises a data buffer storage unit 11, a symptom vector calculation unit 12, an extension vector calculation unit 13, a weight value calculation unit 14, and an error location. Vector 5 201029339 determines unit 15 'and an arithmetic unit i6. The data buffer storage unit u is used to store the received pen-bit sequence. The symptom vector calculation unit 12 calculates a first symptom vector according to the binary sequence and the predefined-auxiliary check matrix, and uses the predefined two-second auxiliary school according to the two-bit sequence. Check the matrix 'to find the H-shaped vector. The extension vector calculation unit 13 is configured to extract a first extended symptom vector according to the first symptom vector, the second symptom vector, and the first auxiliary check matrix, and the second auxiliary check matrix Two extended symptom vectors, a plurality of third extended symptom vectors, and a plurality of fourth extended symptom vectors. The weight value calculation unit 14 is configured to respectively determine a corresponding first symptom vector, the second symptom vector, the first extended symptom vector, the second extended symptom vector, the third extended symptom vector, and the like The plurality of weight values of the fourth extended symptom vector. The error position vector determining unit 15 is configured to perform conditional judgment based on the equal weight values to determine an error-error position vector. The operation unit 16 is configured to decode a corresponding original data according to the error location vector and the received binary sequence. In the preferred embodiment, the decoder 1 of the Gray code is implemented in a hardware manner, but it can also be implemented in a software or firmware manner, and is not limited to the preferred embodiment. An illustration. The matrix used in the steps is pre-defined before the description of the Gray code decoding method is performed. (23, i2'7) Gray code generation polynomial is as shown in equation (1). Rong (^ = 1X^0-#).................................... (where ' h is the set of non-〇 binary squared remainder 201029339 under modulo 23; A is the root of the Gray code generator polynomial. For each _/· = 〇, ι,···, 22, β is as shown in the formula (2). β +..·~,................................(7) Among them, 'the root of the GF(2„) of Gal〇is Field, \., £1),1,..”0^. The root coefficient of the root of the polynomial is generated for Gray code, and GF(2) defines the root coefficient matrix (represented by A) of the root of the Gray code generator polynomial, as shown in equation (3).

Α〇,〇 αο,ι ... αο,ιο A = «1,0 α\,\ ... αΜ〇 _ Λ _α22,0 α22Λ α22,1〇 αη,ο αη,ι ** . Λ απ, ιο

Among them, 疋 4 is an upper half submatrix of the original root coefficient matrix ^; * is the lower half submatrix of the original root coefficient matrix A. Further, a first auxiliary check matrix (represented by $) and a second auxiliary check matrix (represented by )) are defined, as shown in equations (4) and (5), respectively.

...............(4) ·**············ (5) 7χ Refer to Figure i and Figure 2, together with the above-mentioned Gray code decoder The preferred embodiment of the decoding method of the Gray code of the present invention comprises the following steps. In step 21, the decoder i of the Gray code receives the binary sequence (represented by "-(/^,..,,^2",, 22)); and stores in the data buffer storage unit According to the two bits in step 22, the symptom vector calculation unit 201029339 Γ: two; auxiliary: -, second auxiliary one-shaped vector (represented by Α), and the second symptom vector (2 represents)' They are shown in equations (4) and (7) respectively. ^?Γ>......................,,.................. ............................. = %................... . . , , - In step 23, the extended symptom vector calculation unit ι3 finds the first based on the first:: vector vector Α, the second symptom vector, and the first auxiliary check matrix [ _ auxiliary check matrix I - The extended symptom vector, the first extended symptom vector, the third extended symptom vector, and the fourth extended symptom vector ' are represented by equations (8), (", (1), and (U), respectively. An extended symptom vector = ϊ 2θ ^ 12)................................ 〇) Two extended symptom vectors 4 俨, 匕 {11,12,...,22}......................(9) Third Extended symptom vector = ϊ (four) " 十私1), iM12, 13"", 22}.............. (1〇) Fourth extension symptom vector = ί-2@ρ, Similar, called ......................(1〇 where 乂(/) is the first, the second auxiliary check matrix is the first /column vector, J = l, 2; ten is a finite field addition operation, here is a mutually exclusive or (x〇r) operation. In step 24, the weight value calculation unit 14 first finds the first symptom vector 5. The second symptom vector 4, the first extended symptom vector, the second extended symptom vector, the third extended symptom vector, and the weight values of the fourth extended symptom vector are respectively 咐(8), 咐(6) , Finance $10 private 2)), Η^, θλ/1)), Shiji "ten"), and Cai's ten 杞 2)). Then, the error position vector decision unit 15 judges the following conditions according to the financial (8), (10) (6), state 咕 咕 咕)), Μ 十 η 2010) 201029339, η ^ ΛΘ / ^ Θ ::) 'and the state 咐 # 俨}, And based on the results of the conditional judgment, the error vector (represented by ?) is determined. It is worth mentioning that for the decodable binary sequence f, the weight value determined by the above operation must only meet one of the following six cases. Case 1: If OSw咕)<3, then &=〇' its order,; condition 1. if 1^〇2)<3, and i2=(s.,"), then 吒=〇 ~12=\, where,Of <10; Case 3: If, and ?2 十纪) = (m, W, then _ =1 and heart 12, where 0S/S1O; Case 4: If there is a unique An f value, ie {11, 丨2,, 22

Bw 明十Α7”β2, then ^;=1, and ~=〇, where nsx22, and slice case five: if there is a unique value, like, to 22), making you called the ten )):], then ~=1, e, =1, and 勹=〇, where 12^以, and _/_#·; and case six: if there is a unique £• value, ie{〇1 ,, 1〇}, such that ♦ ten 〇 = 2, and ί2θ Α -, (2) = (M, ..., ~), then ~ = 〜 and ~ 3, where 5 5 0 ^; < 10 0 e in the above case , represents the z-th bit of the error position vector 5, and the bit of the error position vector e-bit 70 that is not given (assign) value represents the don't care bit. In step 25, the arithmetic unit 16 mutually exclusive ORs the error position vector g with the two-bit sequence F to decode the original data (represented by the equation) as shown in equation (12). (12) 201029339 In summary, the present invention determines that the error location vector can be determined by fewer operands by the condition of the weight values, and the original data is obtained according to the condition, and six of the above condition determinations In this case, it can be implemented in parallel on the hardware; not only greatly improves the decoding efficiency of Gray code, but also has high computational regularity, and the complexity, required gate number and cost are far lower than the existing algorithms. It is very suitable for hardware implementation, so it can achieve the object of the present invention.

The above is only the preferred embodiment of the present invention, and the scope of the invention is not limited thereto, that is, the simple equivalent changes and modifications made by the scope of the invention and the description of the invention are All remain within the scope of the invention patent. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram, an embodiment; and FIG. 2 is a flow chart, a preferred embodiment. DESCRIPTION OF THE PREFERRED EMBODIMENT OF THE GRAPHIC CODE OF THE INVENTION

10 201029339 [Description of main component symbols] 1 «>««««>» ...Decoding unit of Gray code 11 ... data buffer storage list*| 4 > *·«·»»» t Weight value calculation unit Element 1 • Error position vector decision 1 4 Φ Φ V ft ... symptom vector calculation unit cell 16 arithmetic unit 1 α 1 ^ '... extended symptom vector meter 21~2 5...* - steps

11

Claims (1)

201029339 VII. Patent application scope: 1. A Gray code solution method, comprising the following steps: (a) receiving a two-bit sequence; (b) according to the received binary sequence, and a predefined one An auxiliary check matrix is obtained to obtain a first symptom vector; (c) determining a second symptom vector according to the received binary sequence and a predefined second auxiliary check matrix; (d) Determining a first extended symptom vector, a plurality of second extended symptom vectors, and a plurality of numbers according to the first symptom vector, the second symptom vector, and the first auxiliary check matrix and the second auxiliary check matrix a third extended symptom vector, and a plurality of fourth extended symptom vectors; (e) respectively determining a corresponding first symptom vector, the second symptom vector, the first extended symptom vector, the second extended symptom vector, and the like a second extended symptom vector, and a plurality of weight values of the fourth extended symptom vector; (f) performing conditional judgment based on the weighted values to determine an error position vector; and (g) determining the error location based on the error location And the amount of the two received sequence of bits corresponding to a decoded original data. A is the root of the Gray code generator polynomial, the original root matrix ' is an upper half submatrix of A, and 4 is the lower half submatrix 72 of A is AAJ1, where the number matrix is, 12 201029339 3· t according to the towel The decoding method of the Gray code according to Item 2 of the patent scope, wherein the first symptom vector is the second symptom vector, wherein r is the received binary sequence. 4. According to the method for decoding Gray code according to item 3 of the patent application, wherein 'the first: the extended symptom vector is called 2), the second extended symptom vector is Αθρ, and the third extended symptom vector is The fourth extended symptom vector is _ corpse, wherein W is the first-assisted matrix and the second auxiliary check matrix 『the third column vector,: 1, 2 Ο 5. According to the lion's patent method, the Gray code decoding method described in item 4, wherein 'in this step is called (f) towel, the following condition is judged to determine the error position vector e, where e represents an error. Position vector g of the first / position 70, and tons), tons), ten 咕)), μ ((four))), ton shout "ten dumb", and the taste of ten ^ (7)) respectively represent the first symptom vector a weight value, a weight value of the second symptom vector, a weight value of the first extended symptom vector, a weight value of the second extended symptom vector, a weight value of the third extended symptom vector', and the fourth extension The weight value of the symptom vector: Case 1: If 0^ ah) 53, then ei = 0, where uygn; Case 2: If 1 "咐 2) < 3, and & = (^,, s〗.) , then 吒=〇 and ~2=\' where 0幺1幺1〇; Case 3: If “〇十咕))22, and ^十碎)=(5.,'” ”51.), Then 吒=1 and heart 12=\, where 0SK10; Case 4: If there is a unique I• value, ie {1112,,22丨, so that 纪纪υ)<2 ' then a =1 ' and ~ =〇, where, and _/Ά· 2010293 39 Case 5: If there is a unique value of t, ie {1213, , 22}, such that Wi(il φ乂1 )= 1 ' then ~=1, ¢, = 1 'and 1= 〇, where 12&lt 22, and; and condition 8. If there is a unique value, ie{〇1,1〇丨, make the spider 2Θ&)_2 'and 0 纪2>=(square.", then ~ and ~+1 〆, where, 0 < 7 <10 〇 6. According to the method of decoding the Gray code described in the scope of the patent application, wherein in the step (g), the error position vector and the received sequence of the 7-bit sequence are mutually exclusive OR. To solve the original data. 7. A Gray code decoder comprising: a material buffer storage unit for storing a received binary sequence; a syndrome vector calculation unit for defining a binary sequence according to the binary sequence a first - auxiliary check matrix, find the - first symptom vector And determining a second symptom vector according to the binary sequence and a predefined second auxiliary calibration matrix; an extended symptom vector 讣 gg - 重十算皂70, for using the first symptom amount The first symptom vector, and the poem and the first auxiliary check matrix, the auxiliary auxiliary check matrix, the bundle - each of the first extended symptom vector, the plurality of extended symptom vectors, and the stimuli _ a second extended symptom vector 'and a plurality of four extended symptom vectors; a weight value calculating unit vector, the second symptom vector is used to respectively determine the first extended symptom vector corresponding to the first symptom, and the 14th 201029339 second extension a symptom vector, the third extended symptom vector, and a plurality of weight values of the fourth extended symptom vector; an error position vector determining the single ι for determining the error position vector according to the weighting condition And the operation unit 1 is configured to decode the corresponding original data according to the error position vector and the received binary sequence. According to the gamma hopper of the Gray code described in Item 7 of the patent application, wherein the first auxiliary check matrix (for <, the second auxiliary check matrix is 4, wherein Λ is Gray code generation One of the roots of the polynomial, the root coefficient matrix 4 is the upper-sub-matrix of the ,, and the ^ is the lower-sub-matrix of the read_lower sub-matrix. The decoder of the Gray code according to item 8 of the u-profit range, wherein the symptom vector is calculated. The operation of the unit is as follows: the first symptom vector 'is A, and the second symptom vector 2 is Ting 2, where ? is the received binary sequence. According to the gray according to claim 9 a decoder of the code, wherein the operation of the extended symptom vector calculation unit is as follows: the first extended symptom vector is ten private, the second extended symptom vector is ^10, and the third extended symptom vector is (four) The tenth extension symptom vector is (10) (2), wherein ❸ is the first auxiliary check matrix of the second auxiliary check matrix 7; the f-th column vector,)=12. _The code of the Gray code described in item 1G, where 'this error The set vector decision unit performs the following conditional judgment to determine the error position vector pan, where the position representing the error position vector is, ·, and (4), turn 2), post 2, 咕), _ 十纪) ), 15 201029339 ννί (Α十纪十十, and wi(?2 φ杞2)) respectively represent the weight value of the first symptom vector, the weight value of the second symptom vector, and the weight value of the first extended symptom vector The weight value of the second extended symptom vector, the weight value of the third extended symptom vector, and the weight value of the fourth extended symptom vector: Case 1: If OSvv咕)53, Bay|J e, = 0, where 幺22; Case 2: If 1^(ϊ2)<3, and ί2=(νίι,~), then 吒=〇 and ei+12 = \, where 〇U <1〇; Three: If, and = is), then 611 = 1 and 6, + | 2 = \, where 〇 is 21 〇; Case 4: If there is a unique value, & {1U2,, 22丨, Heart e#)mU=1, and e;=0, where n^22, and case five: if there is a unique value, called 2,13,.·.,22}, making it ten times, 咕) =1, then en=1 , gi = 1, and ~=〇, its towel, called, and _;>ί; and where ey'+12 = Sj Case 6: If there is a unique value, ie{〇1,,1〇} , so that ten tons (2)) = 2, and? 2θρ=(Μ,, Si.), then 吒=〇, 00<10<10 〇12. According to the Gray code decoder described in claim 7, wherein the arithmetic unit is the error The location vector and the received binary sequence are mutually exclusive ORed to decode the original data. 16