Article

Free access

Faster solution of the key equation for decoding BCH error-correcting codes

Author:

Victor Y. PanAuthors Info & Claims

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

Pages 168 - 175

https://doi.org/10.1145/258533.258577

Published: 04 May 1997 Publication History

PDF eReader

References

[1]

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.

Google Scholar

[2]

R.P. Brent, F. G. Gustavson, D. Y. Y.Yun, Fast Solution of Toeplitz Systems of Equations and Computation of Pad~ Approximations, J. of Algorithms, 1, 259-295, 1980.

Crossref

Google Scholar

[3]

D. Bini, V.Y. Pan, Polynomial Division and its Computational Complexity, J. of Complexity, 1, 179-203, 1986.

Digital Library

Google Scholar

[4]

D. Bini, V.Y. Pan, Matrix and Polynomial Computations, Volume 1: Fundamental Algorithms, Birkhaeuser, Boston, 1994.

Digital Library

Google Scholar

[5]

R. P. Brent, Multiple-precision Zero-finding Methods and the Complexity of Elementary Function Evaluation, Analytic Computational Complexity, J. F. Traub, Ed., Academic Press, New York, 151-176, 1975.

Google Scholar

[6]

D.G. Cantor, E. Kaltofen, On Fast Multiplication of Polynomials over Arbitrary Rings, Acta Informatica, 28, 7, 697-701, 1991.

Digital Library

Google Scholar

[7]

L. Csanky, Fast Parallel Matrix Inversion Algorithm, SIAM J. on Comput., 5, 4, 618-623, 1976.

Digital Library

Google Scholar

[8]

J. von zur Gathen, Representation and Parallel Computations for Rational Functions, SIAM J. on Computing, 15, 432-452, 1986.

Digital Library

Google Scholar

[9]

W.B. Gragg, The Pad~ Table and Its Relation to Certain Algorithms of Numerical Analysis, SIAM Review, 14, 1, 1-62, 1972.

Digital Library

Google Scholar

[10]

S. Kakeya, On Fundamental Systems of Symmetric Functions, Japan J. of Math., 2, 69-80, 1925.

Crossref

Google Scholar

[11]

S. Kakeya, On Fundamental Systems of Symmetric Functions, Japan J. of Math., 4, 77-85, 1927.

Crossref

Google Scholar

[12]

D.M. Mandelbaum, A Method for Decoding of Generalized Goppa Codes, IEEE Trans. on Information Theory, 23, 137-140, 1977.

Digital Library

Google Scholar

[13]

J.L. Massey, Shift -Register Synthesis and BCH Decoding, IEEE Trans. on Information Theory, 15, 122-127, 1969.

Digital Library

Google Scholar

[14]

W.H. Mills, Continued Fractions and Linear Recurrences, Math. of Computation, 29,173-180, 1975.

Crossref

Google Scholar

[15]

R. Moenck, Fast Computation of GCDs, Proc. 5th Ann. A CM Syrup. on Theory of Computing, 142-151, ACM Press, New York, 1973.

Crossref

Google Scholar

[16]

K. Nakamura, On the Representation of Symmetric Functions by Power-Sums Which Form the Fundamental System, Japan J. Math., 4, 87-92, 1927.

Crossref

Google Scholar

[17]

V.Y. Pan, Parallel Least-Squares Solution of General and Toeplitz-like Linear Syatems, Proc. ~nd Ann. ACM Syrup. on Parallel Algorithms and Architectures, 244-253, ACM Press, New York, 1990.

Digital Library

Google Scholar

[18]

V.Y. Pan, Parallel Computation of Polynomial GCD and Some Related Parallel Computations over Abstract Fields, Theoretical Computer Science, 162, 2, 173-223, 1996.

Digital Library

Google Scholar

[19]

V.Y. Pan, Improved Pad~ Approximation Approach to Decoding the BCH Error-Correcting Codes, manuscript, 1996.

Google Scholar

[20]

V.Y. Pan, A Simplification of the Key Equation for Decoding BCH Error-Correcting Codes, manuscript, 1996.

Google Scholar

[21]

N.J. Patterson, The Algebraic Decoding of Goppa Codes, IEEE Trans. on Information Theory, 21, 203-207, 1975.

Digital Library

Google Scholar

[22]

M.K. SaJn, Minimum Torsion Spaces and the Practical Input/Output Problem, Information and Control, 29, 103-124, 1975.

Crossref

Google Scholar

[23]

D.V. Sarwate, On the Complexity of Decoding Goppa Codes, IEEE Trans. on Information Theory, 23, 515-516, 1977.

Digital Library

Google Scholar

[24]

A. SchSnhage, The Fundamental Theorem of Algebra in Terms of Computational Complexity, manuscript, University of Tfibingen, Germany, 1982.

Google Scholar

[25]

A. SchSnhage, Fast Parallel Computation of Characteristic Polynomials by Leverrier's Power Sum Method Adapted to Fields of Finite Characteristic, Proc. SOth ICALP, Lecture Notes in Computer Science, 700, 410-417, Springer, Berlin, 1993.

Digital Library

Google Scholar

[26]

Y. Sugiyama, M. Kasahara. S. Hirawawa, T. Namekawa, A Method for Solving Key Equation for Decoding Goppa Codes, Information and Control, 27, 87-99, 1975.

Crossref

Google Scholar

[27]

K.T. Vahlen, LYber FundamentaJsysteme fiir symmetrisch Functionen, Acta Mathematica, 23, 91- 120, 1900.

Crossref

Google Scholar

[28]

B.L. van der Waerden, Modern Algebra, Frederick Ungar Publishing Co., New York, 1953.

Google Scholar

[29]

J.H. van Lint, introduction to Coding Theory, Springer, New York, 1982.

Digital Library

Google Scholar

Cited By

View all

Clifford RKociumaka TPorat EChan T(2019)The streaming k-mismatch problemProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310503(1106-1125)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310503
Lin SAl-Naffouri THan Y(2016)FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed–Solomon CodesIEEE Transactions on Information Theory10.1109/TIT.2016.260041762:10(5343-5358)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TIT.2016.2600417
Tseng FLiu YHwu JChen R(2011)A Secure Reed–Solomon Code Incentive Scheme for Commercial Ad Dissemination Over VANETsIEEE Transactions on Vehicular Technology10.1109/TVT.2011.217247160:9(4598-4608)Online publication date: Nov-2011
https://doi.org/10.1109/TVT.2011.2172471
Show More Cited By

Index Terms

Faster solution of the key equation for decoding BCH error-correcting codes
1. Mathematics of computing
2. Security and privacy
  1. Cryptography
    1. Mathematical foundations of cryptography

Recommendations

Sum-Product Decoding of BCH Codes

This paper proposes methods to improve soft-input and soft-output decoding performance of BCH codes by sum-product algorithm (SPA). A method to remove cycles of length four (RmFC) in the Tanner graph has been proposed. However, the RmFC can not realize ...
Decoding error-correcting codes via linear programming
Decoding interleaved Reed---Solomon codes beyond their joint error-correcting capability

A new probabilistic decoding algorithm for low-rate interleaved Reed---Solomon (IRS) codes is presented. This approach increases the error correcting capability of IRS codes compared to other known approaches (e.g. joint decoding) with high probability. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

May 1997

752 pages

ISBN:0897918886

DOI:10.1145/258533

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC97

Sponsor:

SIGACT

STOC97: 29th Annual Symposium on Theory of Computing

May 4 - 6, 1997

Texas, El Paso, USA

Acceptance Rates

STOC '97 Paper Acceptance Rate 75 of 211 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
931
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)19

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Clifford RKociumaka TPorat EChan T(2019)The streaming k-mismatch problemProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310503(1106-1125)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310503
Lin SAl-Naffouri THan Y(2016)FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed–Solomon CodesIEEE Transactions on Information Theory10.1109/TIT.2016.260041762:10(5343-5358)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TIT.2016.2600417
Tseng FLiu YHwu JChen R(2011)A Secure Reed–Solomon Code Incentive Scheme for Commercial Ad Dissemination Over VANETsIEEE Transactions on Vehicular Technology10.1109/TVT.2011.217247160:9(4598-4608)Online publication date: Nov-2011
https://doi.org/10.1109/TVT.2011.2172471
Junod PKarlov ALenstra A(2009)Improving the Boneh-Franklin Traitor Tracing SchemeProceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography: PKC '0910.1007/978-3-642-00468-1_6(88-104)Online publication date: 12-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-642-00468-1_6
Spielman D(2005)The complexity of error-correcting codesFundamentals of Computation Theory10.1007/BFb0036172(67-84)Online publication date: 21-Jun-2005
https://doi.org/10.1007/BFb0036172
Boneh DFranklin M(1999)An Efficient Public Key Traitor Tracing SchemeAdvances in Cryptology — CRYPTO’ 9910.1007/3-540-48405-1_22(338-353)Online publication date: 16-Dec-1999
https://doi.org/10.1007/3-540-48405-1_22

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Sum-Product Decoding of BCH Codes

Decoding error-correcting codes via linear programming

Decoding interleaved Reed---Solomon codes beyond their joint error-correcting capability