×

Doubly-periodic sequences and two-dimensional recurrences. (English) Zbl 0571.12010

Let R be a commutative ring with identity and \({\mathbb{N}}\) the set of nonnegative integers. The double sequence \(S=(S_{ij}): {\mathbb{N}}\times {\mathbb{N}}\to R\) is said to be doubly periodic if there exist positive integers p and q such that \(S_{i+p,j}=S_{ij}=S_{i,j+q}\) for all i,j\(\in {\mathbb{N}}\). A number of properties and characterizations of such sequences are given using power series rings in two variables. Conditions for the factorization of such sequences as tensor products of single sequences are given. Applications of these results to automata and product codes are given and conditions determined under which certain sets of doubly periodic sequences can be endowed with a field structure.
Reviewer: I.F.Blake

MSC:

11T99 Finite fields and commutative rings (number-theoretic aspects)
94B05 Linear codes (general theory)
94A99 Communication, information
68Q45 Formal languages and automata
Full Text: DOI

References:

[1] Birkhoff, G.; Bartee, T., Modern Applied Algebra, (1970) · Zbl 0215.31302
[2] Dornhoff, L.; Hohn, F., Applied modern algebra, (1978) · Zbl 0408.00001
[3] Dickson, L., History of the theory of numbers, (1952)
[4] Goldman, Jerry; Homer, Steven, Quadratic automata, J. Comput. System Sci., 24, 180, (1982) · Zbl 0492.68046 · doi:10.1016/0022-0000(82)90047-2
[5] Grünbaum, B.; Shephard, G., Satins and twills: an introduction to the geometry of fabrics, Math. Mag., 53, 139, (1980) · Zbl 0462.05025
[6] Hall, Marshall, An isomorphism between linear recurring sequences and algebraic rings, Trans. Amer. Math. Soc., 44, 196, (1938) · Zbl 0019.19301
[7] Hoffman de Visme, G., Binary Sequences, (1971)
[8] Jacobson, Nathan, Lectures in abstract algebra. Vol III: Theory of fields and Galois theory, (1964) · Zbl 0124.27002
[9] van Lint, J., Coding theory, (1973) · Zbl 0936.94014
[10] Liu, C. L., Introduction to combinatorial mathematics, (1968) · Zbl 0188.03801
[11] MacWilliams, F.; Sloane, N., Pseudo-random sequences and arrays, Proc. IEEE, 64, 1715, (1976)
[12] Nerode, A., Linear automaton transformations, Proc. Amer. Math. Soc., 9, 541, (1958) · Zbl 0089.33403
[13] Nomura, Tamiya; Miyakawa, Hiroshi; Imai, Hideki; Fukuda, Akira, A theory of two-dimensional linear recurring arrays, IEEE Trans. Information Theory, IT-18, 775, (1972) · Zbl 0249.94001 · doi:10.1109/TIT.1972.1054914
[14] Sakata, Shojiro, General theory of doubly periodic arrays over an arbitrary finite field and its applications, IEEE Trans. Inform. Theory, 24, 719, (1978) · Zbl 0396.94016 · doi:10.1109/TIT.1978.1055964
[15] Sakata, Shojiro, On determining the independent point set for doubly periodic arrays and encoding two-dimensional cyclic codes and their duals, IEEE Trans. Inform. Theory, 27, 556, (1981) · Zbl 0474.94030 · doi:10.1109/TIT.1981.1056396
[16] Stark, H.; Naab, R., Application of optimum coding sequences to computerized classical tomography, Applied Optics, 17, 3133, (1978)
[17] Willsky, A., Digital signal processing and control and estimation theory, (1979) · Zbl 0512.93001
[18] Zierler, Neal, Linear recurring sequences, J. Soc. Indust. Appl. Math., 7, 31, (1959) · Zbl 0096.33804
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.