Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes

by Fossorier, Marc; Imai, Hidekiarc; Lin, Shu; Poli, Alain

• ISBN13: 9783540667230
• ISBN10: 3540667237
• eBook ISBN(s): 9783540467960
• Format: Paperback
• Copyright: 1999-11-01
• Publisher: Springer Verlag
• More Book Details
• Purchase Benefits

Summary

This book constitutes the refereed proceedings of the 19th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-13, held in Honolulu, Hawaii, USA in November 1999.The 42 revised full papers presented together with six invited survey papers were carefully reviewed and selected from a total of 86 submissions. The papers are organized in sections on codes and iterative decoding, arithmetic, graphs and matrices, block codes, rings and fields, decoding methods, code construction, algebraic curves, cryptography, codes and decoding, convolutional codes, designs, decoding of block codes, modulation and codes, Gröbner bases and AG codes, and polynomials.

Table of Contents

Invited Talks
Codes on Graphs: A Survey for Algebraists	1	(9)
G. David Forney, Jr.
RA Codes Achieve AWGN Channel Capacity	10	(9)
Hui Jin
Robert J. McEliece
Monomial Ideals and Planar Graphs	19	(10)
Ezra Miller
Bernd Sturmfels
A Fast Program Generator of Fast Fourier Transforms	29	(14)
Michael Clausen
Meinard Muller
On Integer Programming Problems Related to Soft-Decision Iterative Decoding Algorithms	43	(12)
Todao Kasami
Curves with Many Points and Their Applications	55	(10)
Ian F. Blake
Codes and Iterative Decoding
New Sequences of Linear Time Erasure Codes Approaching the Channel Capacity	65	(12)
M. Amin Shokrollahi
On the Theory of Low-Density Convolutional Codes	77	(10)
Karin Engdahl
Michael Lentmaier
Kamil Sh. Zigangirov
Combinatorics I: Arithmetic
On the Distribution of Nonlinear Recursive Congruential Pseudorandom Numbers of Higher Orders	87	(7)
Frances Griffin
Harald Niederreiter
Igor E. Shparlinski
A New Representation of Boolean Functions	94	(10)
Claude Carlet
Philippe Guillot
Combinatorics II: Graphs and Matrices
An Algorithm to Compute a Nearest Point in the Lattice An	104	(17)
I. Vaughan
L. Clarkson
Sequences from Cocycles	121	(10)
Kathy J. Horadam
Block Codes I
On the Second Greedy Weight for Binary Linear Codes	131	(11)
Wende Chen
Torleiv Klove
On the Size of Identifying Codes	142	(6)
Uri Blass
Iiro Honkala
Simon Litsyn
Algebra I: Rings and Fields
Fast Quantum Fourier Transforms for a Class of Non-abelian Groups	148	(12)
Markus Puschel
Martin Rotteler
Thomas Beth
Linear Codes and Rings of Matrices	160	(10)
M. Greferath
S. E. Schmidt
On ZZ4-Simplex Codes and Their Gray Images	170	(11)
Mahesh C. Bhandari
Manish K. Gupta
Arbind K. Lal
Decoding Methods
Some Results on Generalized Concatenation of Block Codes	181	(10)
M. Bossert
H. Grieβer
J. Maucher
V. V. Zyablov
Near Optimal Decoding for TCM Using the BIVA and Trellis Shaping	191	(10)
Qi Wang
Lei Wei
Rodney A. Kennedy
An Optimality Testing Algorithm for a Decoded Codeword of Binary Block Codes and Its Computational Complexity	201	(10)
Yuansheng Tang
Tadao Kasami
Toru Fujiwara
Algebra II
Recursive MDS-codes and Pseudogeometries	211	(10)
Elena Couselo
Santos Gonzalez
Victor Markov
Alexandr Nechaev
Strength of MISTY1 without FL Function for Higher Order Differential Attack	221	(10)
Hidema Tanaka
Kazuyuki Hisamatasu
Toshinobu Kaneko
Code Construction
Quantum Reed-Solomon Codes	231	(14)
Markus Grassl
Willi Geiselmann
Thomas Beth
Capacity Bounds for the 3-dimensional (0,1) Runlength Limited Channel	245	(7)
Zsigmond Nagy
Kenneth Zeger
Rectangular Codes and Rectangular Algebra	252	(8)
V. Sidorenko
J. Maucher
M. Bossert
Codes and Algebra I: Algebraic Curves
Decoding Hermitian Codes with Sudan's Algorithm	260	(11)
T. Hoholdt
R. Refslund Nielsen
Computing a Basis of L(D) on an Affine Algebraic Curve with One Rational Place at Infinity	271	(11)
Ryutaroh Matsumoto
Shinji Miura
Cryptography
Critical Noise for Convergence of Iterative probabilistic Decoding with Belief Propagation in Cryptographic Applications	282	(12)
Marc P. C. Fossorier
Miodrag J. Mihaljevic
Hideki Imai
An Authentication Scheme over Non-authentic Public Channel in Information Theoretic Secret-Key Agreement	294	(8)
Shengli Liu
Yumin Wang
Codes and Decoding
A Systolic Array Architecture for Fast Decoding of One-Point AG Codes and Scheduling of parallel Processing on It	302	(12)
Shojiro Sakata
Masazumi Kurihara
Convolutional Codes
Computing Weight Distributions of Convolutional Codes via Shift Register Synthesis	314	(10)
Mehul Motani
Chris Heegard
Properties of Finite Response Input Sequences of Recursive Convolutional Codes	324	(10)
Didier Le Ruyet
Hong Sun
Han Vu Thien
Combinatorics III: Designs
Lower Bounds for Group Covering Designs	334	(12)
K. K. P. Chanduka
Mahesh C. Bhandari
Arbind K. Lal
Characteristic Functions of Relative Difference Sets, Correlated Sequences and Hadamard Matrices	346	(9)
Garry Hughes
Decoding of Block Codes
Double Circulant Self-Dual Codes Using Finite-Field Transforms	355	(10)
F. Fekri
S. W. McLaughlin
R. M. Mersereau
R. W. Schafer
Algebra III: Rings and Fields
Linear Codes and Polylinear Recurrences over Finite Rings and Modules (a Survey)	365	(27)
V. L. Kurakin
A. S. Kuzmin
V. T. Markov
A. V. Mikhalev
A. A. Nechaev
Calculating Generators for Invariant Fields of Linear Algebraic Groups	392	(12)
Jorn Muller-Quade
Thomas Beth
Constructing Elements of Large Order in Finite Fields	404	(6)
Joachim von zur Gathen
Igor Shparlinski
Modulation and Codes
New Lower Bounds on the Periodic Crosscorrelation of QAM Codes with Arbitrary Energy	410	(10)
S. Boztas
Conjectures on the Size of Constellations Constructed from Direct Sums of PSK Kernels	420	(10)
Matthew G. Parker
Codes and Algebra II: Grobner Bases and AG Codes
A New Criterion for Normal Form Algorithms	430	(14)
B. Mourrain
Discrete Fourier Transform and Grobner Bases	444	(10)
A. Poli
M. C. Gennero
D. Xin
Block Codes II
On the State Complexities of Ternary Codes	454	(8)
Sylvia Encheva
Gerard Cohen
Binary Optimal Linear Rate 1/2 Codes	462	(10)
Koichi Betsumiya
T. Aaron Gulliver
Masaaki Harada
On Binary/Ternary Error-Correcting Codes with Minimum Distance 4	472	(10)
Patric R. J. Ostergard
Algebra IV: Polynomials
The Euclidean Algorithm and Primitive Polynomials over Finite Fields	482	(10)
James W. Bond
Stefen Hui
Hank Schmidt
On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials	492	(6)
Marek Karpinski
Igor Shparlinski
Mastrovito Multiplier for General Irreducible Polynomials	498	(11)
A. Halbutogullari
C. K. Koc
Author Index	509