-
Previous Article
All binary linear codes of lengths up to 18 or redundancy up to 10 are normal
- AMC Home
- This Issue
-
Next Article
Explicit formulas for real hyperelliptic curves of genus 2 in affine representation
Fast multi-sequence shift-register synthesis with the Euclidean algorithm
1. | Institute of Communications Engineering, Ulm University, Albert-Einstein-Allee 43, 89083 Ulm, Germany, and Research Center INRIA Saclay - Île-de-France, École Polytechnique, 91128 Palaiseau Cedex, France |
2. | Institute of Communications Engineering, Ulm University, Albert-Einstein-Allee 43, 89083 Ulm, Germany, and Institut de Recherche Mathémathique de Rennes (IRMAR), Université de Rennes 1, 35042 Rennes Cedex, France |
References:
[1] |
A. V. Aho and J. E. Hopcroft, "The Design and Analysis of Computer Algorithms,'' Addison-Wesley Longman Publishing Co., 1974. |
[2] |
R. E. Blahut, "Fast Algorithms for Digital Signal Processing,'' Addison-Wesley, 1985. |
[3] |
D. Bleichenbacher, A. Kiayias and M. Yung, Decoding interleaved Reed-Solomon codes over noisy channels, Theor. Comput. Sci., 379 (2007), 348-360.
doi: 10.1016/j.tcs.2007.02.043. |
[4] |
G. L. Feng and K. K. Tzeng, A generalized Euclidean algorithm for multisequence shift-register synthesis, IEEE Trans. Inform. Theory, 35 (1989), 584-594.
doi: 10.1109/18.30981. |
[5] |
G. L. Feng and K. K. Tzeng, A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes, IEEE Trans. Inform. Theory, 37 (1991), 1274-1287.
doi: 10.1109/18.133246. |
[6] |
J. Gathen and J. Gerhard, "Modern Computer Algebra'', Cambridge University Press, 2003. |
[7] |
C. Hartmann, Decoding beyond the BCH bound, IEEE Trans. Inform. Theory, 18 (1972), 441-444.
doi: 10.1109/TIT.1972.1054824. |
[8] |
V. Y. Krachkovsky, Reed-Solomon codes for correcting phased error bursts, IEEE Trans. Inform. Theory, 49 (2003), 2975-2984.
doi: 10.1109/TIT.2003.819333. |
[9] |
V. Y. Krachkovsky and Y. X. Lee, Decoding for iterative Reed-Solomon coding schemes, IEEE Trans. Magnetics, 33 (1997), 2740-2742.
doi: 10.1109/20.617715. |
[10] |
J. D. Lipson, "Elements of Algebra and Algebraic Computing,'' Addison-Wesley Educational Publishers Inc, 1981. |
[11] |
C. Roos, A generalization of the BCH bound for cyclic codes, including the Hartmann-Tzeng bound, J. Combin. Theory Ser. A, 33 (1982), 229-232.
doi: 10.1016/0097-3165(82)90014-0. |
[12] |
G. Schmidt, V. R. Sidorenko and M. Bossert, Syndrome decoding of Reed-Solomon codes beyond half the minimum distance based on shift-register synthesis, IEEE Trans. Inform. Theory, 56 (2010), 5245-5252.
doi: 10.1109/TIT.2010.2060130. |
[13] |
Y. Sugiyama, M. Kasahara, S. Hirasawa and T. Namekawa, A method for solving key equation for decoding Goppa codes, Inform. Control, 27 (1975), 87-99.
doi: 10.1016/S0019-9958(75)90090-X. |
[14] |
L. Wang, Euclidean modules and multisequence synthesis, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes'' (eds. S. Boztaş and I.E. Shparlinski), Springer, Berlin, Heidelberg, (2001), 239-248. |
[15] |
A. Zeh and W. Li, Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm, in "Proceedings of the 2010 International Symposium on Information Theory and its Applications (ISITA),'' Taichung, Taiwan, (2010), 986-990.
doi: 10.1109/ISITA.2010.5649520. |
show all references
References:
[1] |
A. V. Aho and J. E. Hopcroft, "The Design and Analysis of Computer Algorithms,'' Addison-Wesley Longman Publishing Co., 1974. |
[2] |
R. E. Blahut, "Fast Algorithms for Digital Signal Processing,'' Addison-Wesley, 1985. |
[3] |
D. Bleichenbacher, A. Kiayias and M. Yung, Decoding interleaved Reed-Solomon codes over noisy channels, Theor. Comput. Sci., 379 (2007), 348-360.
doi: 10.1016/j.tcs.2007.02.043. |
[4] |
G. L. Feng and K. K. Tzeng, A generalized Euclidean algorithm for multisequence shift-register synthesis, IEEE Trans. Inform. Theory, 35 (1989), 584-594.
doi: 10.1109/18.30981. |
[5] |
G. L. Feng and K. K. Tzeng, A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes, IEEE Trans. Inform. Theory, 37 (1991), 1274-1287.
doi: 10.1109/18.133246. |
[6] |
J. Gathen and J. Gerhard, "Modern Computer Algebra'', Cambridge University Press, 2003. |
[7] |
C. Hartmann, Decoding beyond the BCH bound, IEEE Trans. Inform. Theory, 18 (1972), 441-444.
doi: 10.1109/TIT.1972.1054824. |
[8] |
V. Y. Krachkovsky, Reed-Solomon codes for correcting phased error bursts, IEEE Trans. Inform. Theory, 49 (2003), 2975-2984.
doi: 10.1109/TIT.2003.819333. |
[9] |
V. Y. Krachkovsky and Y. X. Lee, Decoding for iterative Reed-Solomon coding schemes, IEEE Trans. Magnetics, 33 (1997), 2740-2742.
doi: 10.1109/20.617715. |
[10] |
J. D. Lipson, "Elements of Algebra and Algebraic Computing,'' Addison-Wesley Educational Publishers Inc, 1981. |
[11] |
C. Roos, A generalization of the BCH bound for cyclic codes, including the Hartmann-Tzeng bound, J. Combin. Theory Ser. A, 33 (1982), 229-232.
doi: 10.1016/0097-3165(82)90014-0. |
[12] |
G. Schmidt, V. R. Sidorenko and M. Bossert, Syndrome decoding of Reed-Solomon codes beyond half the minimum distance based on shift-register synthesis, IEEE Trans. Inform. Theory, 56 (2010), 5245-5252.
doi: 10.1109/TIT.2010.2060130. |
[13] |
Y. Sugiyama, M. Kasahara, S. Hirasawa and T. Namekawa, A method for solving key equation for decoding Goppa codes, Inform. Control, 27 (1975), 87-99.
doi: 10.1016/S0019-9958(75)90090-X. |
[14] |
L. Wang, Euclidean modules and multisequence synthesis, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes'' (eds. S. Boztaş and I.E. Shparlinski), Springer, Berlin, Heidelberg, (2001), 239-248. |
[15] |
A. Zeh and W. Li, Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm, in "Proceedings of the 2010 International Symposium on Information Theory and its Applications (ISITA),'' Taichung, Taiwan, (2010), 986-990.
doi: 10.1109/ISITA.2010.5649520. |
[1] |
Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015 |
[2] |
Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057 |
[3] |
Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69 |
[4] |
Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053 |
[5] |
Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005 |
[6] |
José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467 |
[7] |
Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008 |
[8] |
Jaedal Jung, Ertugrul Taciroglu. A divide-alternate-and-conquer approach for localization and shape identification of multiple scatterers in heterogeneous media using dynamic XFEM. Inverse Problems and Imaging, 2016, 10 (1) : 165-193. doi: 10.3934/ipi.2016.10.165 |
[9] |
Michael Baake, John A. G. Roberts, Reem Yassawi. Reversing and extended symmetries of shift spaces. Discrete and Continuous Dynamical Systems, 2018, 38 (2) : 835-866. doi: 10.3934/dcds.2018036 |
[10] |
Wenjun Xia, Jinzhi Lei. Formulation of the protein synthesis rate with sequence information. Mathematical Biosciences & Engineering, 2018, 15 (2) : 507-522. doi: 10.3934/mbe.2018023 |
[11] |
Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046 |
[12] |
Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021 |
[13] |
Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427 |
[14] |
Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195 |
[15] |
Kin Ming Hui, Jinwan Park. Asymptotic behaviour of singular solution of the fast diffusion equation in the punctured euclidean space. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5473-5508. doi: 10.3934/dcds.2021085 |
[16] |
B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037 |
[17] |
Lu Tan, Ling Li, Senjian An, Zhenkuan Pan. Nonlinear diffusion based image segmentation using two fast algorithms. Mathematical Foundations of Computing, 2019, 2 (2) : 149-168. doi: 10.3934/mfc.2019011 |
[18] |
Leonid Kunyansky. Fast reconstruction algorithms for the thermoacoustic tomography in certain domains with cylindrical or spherical symmetries. Inverse Problems and Imaging, 2012, 6 (1) : 111-131. doi: 10.3934/ipi.2012.6.111 |
[19] |
Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems and Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067 |
[20] |
Gemma Huguet, Rafael de la Llave, Yannick Sire. Computation of whiskered invariant tori and their associated manifolds: New fast algorithms. Discrete and Continuous Dynamical Systems, 2012, 32 (4) : 1309-1353. doi: 10.3934/dcds.2012.32.1309 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]