Оказывается, что ортогональные системы, и только они, дают возможность построения q-арного кода с параметрами n = t + 2 и d = t + 1.

При построении кодов возникает вопрос: каково максимальное число слов длиной n q-арного кода с кодовым расстоянием d? Оно установлено и равно qn – d+1. Это число достижимо для всяких n, d и q, значения которых удовлетворяют теореме: если n £ q + 1 и d = n – 1 или если n £ q, а d = n, то максимальная граница для числа слов кода может быть достигнута, когда q – число, для которого существует полное множество в. о.л. к. порядка q.

Ниже дан пример такого максимального кода для q = 4; n = 5; d = 4 (qn – d + 1 = q2). Полному множеству в. о.л. к. порядка 4 соответствует код, представленный в табл. 9. Из него можно получить коды с другими параметрами.

Рассмотрим еще один класс л. к. порядка n – полные. В них для любой упорядоченной пары элементов (a, b), a ¹ b существует строка и столбец, в которых a и b являются соседними. Такие квадраты существуют для любого четного, а также некоторых нечетных порядков. Правило построения кода по полному л. к. дает теорема: пусть A = ||aij||, – полный л. к. порядка q, заданный на множестве {1, 2, …, q}. Тогда совокупность слов (i,; j; a1,j; ai, j+1), где ; , образует

q-арный код, состоящий из q×(q–1) кодовых слов длиной 4 с кодовым расстоянием d = 3 [10]. Полный л. к. порядка 4 и код, соответствующий ему, приведены в табл. 10 [2].

НЕ нашли? Не то? Что вы ищете?

Кроме полных л. к. в теории кодирования нашли применение и составные. Они существуют для любого четного порядка и могут быть использованы для задания проверочных разрядов бинарного кода постоянного веса, все кодовые слова которого имеют одинаковое число единиц.

Во всех рассмотренных выше примерах л. к. использовались для построения небинарных кодов. Однако их можно применить и для бинарных. В этих примерах отражены далеко не все возможности применения л. к. Новые задачи в разнообразных областях научной и практической деятельности постоянно расширяют эти возможности.

Список литературы

1.  Доказательства из Книги. Лучшие доказательства со времен Евклида до наших дней. Гл.27. Дополнения до полных латинских квадратов / пер. с англ. М.: Мир, 2006. 256 с.

2.  Автоматы с квазигруппой входных сигналов // Сообщения АН ГССР, 1985. Т. 117, № 1. С.17–20.

3.  Формирование комбинаторного анализа. М., 1989. 245 с. / Деп. в ВИНИТИ 01.12.89. № 000–В89.

4.  О создании Эйлером комбинаторной теории латинских квадратов // Историко-математические исследования / под ред. . М.: Наука, 1982. Вып. XXVII. С.102–123.

5.  Руководство по применению латинских планов при планировании эксперимента с качественными факторами. Челябинск: Южно-Урал. кн. изд-во, 1971. 156 с.

6.  , Планирование эксперимента в условиях неоднородностей. М.: Наука, 1973. 218 с.

7.  , Математика и спорт. М.: Наука, 1985. Вып. 44. 192 с.

8.  Bose R. S. On the applications of the properties of Galois fields to the problems of construction of Hyper-Graeco-Latin squares // Indian J. Stat. 1938. № 3. Part. 4. P.323–338.

9.  Cayley A. On latin squares // Mess. Math. 1890. Vol.19. P.135–137.

10.  Dénes J., Keedwell A. D. Latin squares and their applications. Budapest: Académiai Kiаdó, 1974. 547 p.

11.  Euler L. Recherches sur une nouvelle espece de carrés magiques // Opera Omnia. 1923. Vol. 1. P.291–392.

12.  Fisher R. A., Yates J. Statistical tables per biological, agricultural and medical research. Edinburgh, 1936.

13.  Günter S. Mathematisch-historische Miscellen. II. Die magischen Quadrate dei Gauss // Z. Math. Phys. 1876. Bd.21. S.61–64.

14.  Lucas E. Théorie des nombres. Paris, 1891. P.481–495.

15.  MacMahon P. A. A new method in combinatory analysis with application to latin squares and associated questions // Trans. Amer. Phil. Soc. 1898. Vol.16. P.262–290.

16.  Mann H. B. Analysis and Design of Experiments. N.–Y., 1949.

17.  Norton H. W. The 7´7 squares // Ann. Eugenics. 1939. Vol.9. P.269–307.

18.  Sade A. An omission in Norton's list of 7´7 squares // Ann. Math. Stat. 1951. Vol.22. P.306–307.

19.  Safford F. H. Solution of a problem proposed by O. Veblen // Amer. Math. Monthly. 1907. Vol. 14. P. 84–86.

20.  Tarry G. Le problème des 36 officiers // C. R. Assoc. France Av. Sci. 1900. Vol.29, №2. P.170–203.

21.  Touchard J. Permutations, discordant with two given permutations // Scripta Math., 1953. №19. P.109–111.

About historical process of development

the latins squares theory and some their

A. E. Malykh, V. I. Danilova

Perm State Pedagogical University, Russia, 614000, Perm, Sibirskaja st., 24

*****@***ru; (342) 280-37-55

The main direction of development the theory of latin squares – private kind of block-design constructions – was described. Their applications in experimental designs, an error detecting and correcting codes were showed.

Key words: combinatorial analysis; history of mathematics; latin squares; the concept of orthogonality; experimental designs; noise combating codes.

© , , 2010

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5