- 學位論文
三元平方剩餘碼(23, 11, 9)解碼法使用新式症狀值矩陣
Ternary (23, 11, 9) quadratic residue decoder using new syndrome matrices
摘要
近幾年，使用牛頓不等式的方法來解三元循環碼已經被提出。因牛頓不等式解碼法需要連續的已知症狀值，若是無法取得連續症狀值，在進行解碼上會需要先解出未知症狀值後再去求的錯誤位置多項式的各係數值，才可解出正確的錯誤位置。因此，本研究希望找的一個新方法可以利用未知症狀值來進行解碼。 本論文中，提出使用新式症狀值矩陣來進行解碼，因為可以利用新式症狀值矩陣展開後的多項式表示出未知症狀值，該多項式是以已知症狀值表示。從解碼第一步，判斷錯誤位置數量的條件式，可利用已知症狀值矩陣多項式來進行判斷；第二步，使用新式症狀值矩陣進行解碼以解出錯誤位置及錯誤係數。 針對三元循環碼，將未知症狀值表示式與牛頓不等式進行解碼時間比較，而在解兩個錯時，使用未知症狀值表示式優於利用牛頓不等式；但在解三個錯時卻僅接近牛頓不等式的時間，其原因是未知症狀值表示式在解三個錯時，所需已知症狀值多於牛頓不等式。最後，本論文提供一個(23, 11, 9)三元平方剩餘碼使用未知症狀值多項式的完整解碼例子。
並列摘要
Algebraic decoding of ternary QR codes has been investigated in a series of paper [1-10]. Recently, the (23, 11, 9), (23, 12, 8) ternary QR codes have been decoded by using the Newton’s identities. In [11], it is known that the unknown syndromes can be determined by the syndrome matrices and are expressed as the functions of some known syndromes. This is helpful in solving the coefficients of the error locator polynomial obtained from Newton’s identities. The aim of this research is to develop the new matrices to be used in finding the error locator polynomial needed in the decoding of a ternary QR code. In this thesis, two novel syndrome matrices are proposed to obtain the polynomials whose roots correspond to the error locations. The resulting polynomials can be represented as functions of some known syndromes, which derived from the determinant of a syndrome matrix. As a result, the algebraic decoding of a ternary QR code consist of four steps. First, compute the known syndromes and use the syndrome polynomials to determine the number of the occurred errors. Next, determine the error locator polynomials obtained from the syndrome matrices and then determine their roots by using Chein search. Finally, solve the linear system to find the error values. A complete decoding of the (23, 11, 9) ternary QR code is presented in this thesis. This decoding method is based on the new syndrome matrices. Compared our method with traditional decoding method by using the Newton’s identities, the experimental results shown that the proposed method requires less computational time than the traditional decoding method in decoding two errors of the (23, ,11, 9) ternary QR code.