On Decoding of the (73, 37, 13) Quadratic Residue Code

In this paper, a method to search the set of syndromes´ indices needed in computing the unknown syndromes for the (73, 37, 13) quadratic residue (QR) code is proposed. According to the resulting index sets, one computes the unknown syndromes and thus finds the corresponding error-locator polynomial by using an inverse-free Berlekamp-Massey (BM) algorithm. Based on the modified Chase-II algorithm, the performance of soft-decision decoding for the (73, 37, 13) QR code is given. This result is new. Moreover, the error-rate performance of linear programming (LP) decoding for the (73, 37, 13) QR code is also investigated, and LP-based decoding is shown to be significantly superior in performance to the algebraic soft-decision decoding while requiring almost the same computational complexity. In fact, the algebraic hard-decision and soft-decision decoding of the (89, 45, 17) QR code outperforms that of the (73, 37, 13) QR code because the former has a larger minimal distance. However, experimental results indicate that the (73, 37, 13) QR code outperforms the (89, 45, 17) QR code with much fewer arithmetic operations when using the LP-based decoding algorithms. The pseudocodewords analysis partially explains this seemingly strange phenomenon.