We construct linear codes over odd prime fields for correcting two-dimensional (2-D) Lee-errors on the hexagonal signal constellations. They are obtained by puncturing and enlarging either RS codes or BCH codes. We introduce 2-D Lee-weight on the hexagonal constellations in the same way as the method presented by the first author in ISIT’19, and propose an effective and efficient method for correcting Lee-errors of small weight. The concept of value-locator of an error, which was introduced implicitly by K. Nakamura in the late 1970s and early 1980s and inherited to the ISIT’19 paper, is a key for decoding Lee-error-correcting codes. Our method is based on the Buchberger algorithm for finding Gröbner bases of ideals in the multivariate polynomial ring. A result of simulations shows that our method works well for correcting Lee-errors of small weight.

The multipoint codes from algebraic curves are a broad class of algebraic geometry codes derived from algebraic functions, which have multiple poles/zeros on their defining curves. Each of them is defined as either a primal code or a dual code. The dual one-point codes which are viewed as a subclass can be decoded efficiently up to the Feng-Rao bound by using the Berlekamp-Massey-Sakata (BMS) algorithm with majority logic. Since a primal code is equivalent to a dual code, one can decode as either of them, while their decoding methods are different. Recently, we published a fast method for decoding primal multipoint codes from curves based on the vectorial BMS algorithm. But, that is neither for dual codes nor up to the Goppa bound dGoppa. Although we can guarantee theoretically that every error vector of weight only up to (1/2)(dGoppa- g) can be corrected, where the integer g is the genus of the defining curve, the simulation shows that the method can correct most error patterns of weight up to (1/2)dGoppa. In this paper we present a fast method for decoding dual multipoint codes from algebraic curves up to the Kirfel-Pellikaan bound, based on the vectorial BMS algorithm with majority logic, and show that algebraic geometry codes from generic algebraic curves can be decoded up to the Goppa bound efficiently. Similar to the case of one-point codes, the computational complexity of decoding is O(a1n2), where the integer a1 is the minimum nonzero pole order of algebraic functions on the defining curve and the integer n is the code length, and in particular, O(n(7/3)) for Hermitian codes. This complexity is less than the complexity O(a1gn2) of Lee's method for decoding dual multipoint codes as a unique alternative.

Multipoint codes are a broad class of algebraic geometry codes derived from algebraic functions, which have multiple poles and/or zeros on an algebraic curve. Thus, they are more general than one-point codes, which are an important class of algebraic geometry codes in the sense that they can be decoded efficiently using the Berlekamp-Massey-Sakata algorithm. We present a fast method for decoding multipoint codes from a plane curve, particularly a Hermitian curve. Our method with some adaptation can be applied to decode multipoint codes from a general algebraic curve embedded in the N-dimensional affine space FqNover a finite field Fq, so that those algebraic geometry codes can be decoded efficiently if the dimension N of the affine space, including the defining curve is small.

Multipoint codes are a broad class of algebraic geometry codes derived from algebraic functions which have multiple poles on their defining curves. Thus, they are more general than one-point codes which are an important class of algebraic codes in the sense that they can be decoded efficiently by using the BMS algorithm. In this paper we present a fast decoding method of multipoint codes from algebraic curves. Since algebraic geometry codes from algebraic curves are essentially the same as multipoint codes, this means that almost all algebraic geometry codes can be decoded efficiently.

In this paper, we propose a class of regular LDPC codes from a cyclic difference family, which is a kind of combinatorial design. These LDPC codes have no 4-cycles, i.e., cycles of length 4. We clarify the conditions on which these codes with column weight 3 have no 6-cycles and discuss their minimum distance. Finally, we show the performance of the proposed codes with high rates and moderate lengths

We present a simple modification of the Berlekamp-Massey (BM) algorithm by which one can solve the problem solved by the 'multiple-sequence BM algorithm' [Feng and Tzeng, IEEE IT Trans. 1989, 1991]. The original BM algorithm which we call 'single-sequence BM algorithm' finds a simplest linear feedback shift register (LFSR) capable of generating a given (single) sequence while the multiple-sequence BM algorithm finds a simplest LFSR capable of generating each of given (multiple) sequences. We have only to repeat our algorithm with reinitialization. The computational complexity is the same as the multiple-sequence BM algorithm. It allows that given sequences have different lengths

We construct a two-dimensional systolic array implementing the Berlekamp-Massey-Sakata (BMS) algorithm to provide error-locator polynomials for codes on selected algebraic curves. This array is constructed by introducing some new polynomials in order to increase the parallelism of the algorithm. The introduced polynomials are used in the majority logic scheme by Sakata et al. to correct errors up to the designed minimum distance without affecting its high speed. The arrangement of the nearest local connection of processing units in the systolic array is obtained for the general case. Furthermore, shortened systolic arrays that reduce the circuit scale and have the same function are constructed with only a slight modification of the connections and controls; this enables the adjustment of the circuit scale for different types of systems.

This article gives an errata (that is erasure- and error-) decoding algorithm of one-point algebraic-geometry codes up to the Feng-Rao (1994) designed minimum distance using Sakata's (see Proc. 1995 IEEE Int. Symp. Information Theory, Whistler, BC, Canada, 1995) multidimensional generalization of the Berlekamp-Massey (1969) algorithm and the voting procedure of Feng and Rao.

We treat a general class of algebraic-geometric codes and show how to decode these up to half the Feng-Rao bound, using an extension and modification of the Sakata algorithm (1990). The Sakata algorithm is a generalization to N dimensions of the classical Berlekamp-Massey algorithm.

We present a decoding algorithm for algebraic-geometric codes from regular plane curves, in particular the Hermitian curve, which corrects all error patterns of weight less than d*/2 with low complexity. The algorithm is based on the majority scheme of Feng and Rao (1993) and uses a modified version of Sakata's (1988) generalization of the Berlekamp-Massey algorithm.

A method of decoding two-dimensional (2-D) cyclic codes by applying the 2-D Berlekamp-Massey algorithm is proposed. To explain this decoding method, the author introduces a subclass of 2-D cyclic codes, which are called 2-D BCH codes due to their similarity with BCH codes. It is shown that there are some short 2-D cyclic codes with a better cost parameter value. The merit of the approach is verified by showing several simple examples of 2-D cyclic codes.>

A method is presented for determining the unknown degree and system function of any 2-D discrete linear shift-invariant system characterized by a 2-D impulse response array, i.e., the coefficients of the formal double power series that are obtained by expanding a rational transfer function. Problems of 2-D Pade approximation and 2-D system reduction can be solved by the same method by making a reasonable assumption in the context of 2-D linear systems theory. The method is based on a 2-D extension of the Berlekamp-Massey algorithm for synthesis of linear feedback shift registers. It gives a novel approach to identification and approximation of 2-D linear systems and is comparable in efficiency with other methods for 2-D rational approximation based on the block Toeplitz and block Hankel matrices.

A common problem of Pattern projection methods to measure surfaces of 3-D objects is that an observed pattern possibly i ncludes disorders such as deficiency, d isplacement, and permutation of subpatterns. These disorders make it difficult to match observed patterns with its position on the projected one and cause wrong m easurements as a result. This paper proposes a new technique to correct pattern disorders by using a pattern made from an M-array which is a two-dimensional extension of a well-known M-sequence.

The author presents a method of finding the cycle representatives of any quasi-irreducible (QIR) 2-D cyclic code by extending A.P. Kurdjukov's (Probl. Peredach. Inform., vol.12, no.4, p.107-8, 1976) result on quasi-irreducible (i.e. nonsquare-free) 10D cyclic codes. The algorithm is not strictly deterministic in the sense that it is necessary to obtain a set of representative arrays for the code by a trial-and-error method. The result is useful for finding the cycle representatives of any 2D cyclic code by combining QIR components with the aid of G. Sequin's (1974) method to the case where the symbol field is the binary Galois field GF(2). In particular, the result is useful for determining the weight distribution of any two-dimensional cyclic code.>

For the purpose of encoding two-dimensional cyclic (TDC) codes, an effective algorithm for finding the independent point set of an arbitrary module of doubly periodic (DP) arrays is proposed. In addition, a method for determining the characteristic ideal of a given set of DP arrays is exhibited. With the aid of these methods it is possible to specify the structure of the generator and check ideals of TDC codes. By applying this algorithm to nonsemisimple binary TDC codes with small areas, several optimal linear codes have been found and their previously unknown TDC structures have been exhibited.

A general theory of doubly periodic (DP) arrays over an arbitrary finite field GF(q)is presented. First the basic properties of DP arrays are examined. Next modules of linear recurring (LR) arrays are defined and their algebraic properties discussed in connection with ideals in an extension ring\tilde{R}of the ringRof bivariate polynomials with coefficients in GF(q). A finite\tilde{R}-module of DP arrays is shown to coincide with the\tilde{R}-module of LR arrays dermed by a zero-dimensional ideal in\tilde{R}. Equivalence relations between DP arrays are explored, i.e., rearrangements of arrays by means of unimodular transformations. Decimation and interleaving of arrays are defined in a two-dimensional sense. The general theory is followed by application to irreducible LR arrays. Among irreducible arrays,M-arrays are a two-dimensional analog ofM-sequences and may be constructed fromM-sequences by means of unimodular transformations. The results of this paper are also important in studying properties of Abelian codes.