Об историческом процессе развития теории латинских квадратов и некоторых их приложениях

Размещено на http://www.allbest.ru/

Об историческом процессе развития теории латинских квадратов и некоторых их приложениях

А.Е. Малых,

В.И. Данилова

Аннотация

Описано основное направление развития теории латинских квадратов - частного вида конструкций блочно-схемного типа, показаны их приложения в планировании экспериментов и создании помехоустойчивых кодов.

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

 А.Е. Малых, В.И. Данилова, 2010В переведенной на русский язык (2006) с третьего издания книги известных ученых М. Айгнера и Г. Циглера "Доказательства из Книги. Лучшие доказательства со времен Евклида до наших дней" [1] в гл. 27 "Дополнения до полных латинских квадратов" указано, что латинские квадраты (ниже - л.к.) являются одними из старейших комбинаторных объектов. Их изучение началось еще в античные времена. В действительности это не так. Такими структурами являются магические квадраты. Их истоки уходят к IV в. до н.э.

В отличие от магических, л.к. имеют сформированную теорию и определенную область приложений. Наиболее полная и конкретная информация по этому вопросу содержится в монографии [10], а исторический процесс развития отражен нами в работах [3, 4].

У истоков теории латинских квадратов стоял Леонард Эйлер (1707-1783). Его обширный мемуар "Исследование магического квадрата нового типа" [11] начинается словами: "Весьма любопытный вопрос, который привлекал в течение некоторого времени внимание лучших умов мира, заставил меня выполнить исследования, которые, кажется, открыли новое направление в анализе и, в частности, комбинаторике. Этот вопрос касается совокупности 36 офицеров шести разных званий, взятых из шести разных полков, которых выстраивают в каре таким образом, чтобы в каждом ряду, как по горизонтали, так и по вертикали, находилось шесть офицеров различных званий и из разных полков. Однако после всех трудов, затраченных на решение этой задачи, я вынужден был признать, что такое размещение абсолютно невозможно, хотя и не удалось дать строгого доказательства этому" [11, с.291].

Для поиска решения задачи Эйлер "перевел" ее на математический язык. По условию следует построить две квадратные таблицы размером 66, сходные с магическими квадратами, но отличающиеся от них рядом свойств. Одну из них Эйлер назвал латинским квадратом, а другую - греческим, причем первый составлялся произвольным образом. Исходя из него он подбирал шесть буквенных последовательностей из шести элементов каждая. Их автор назвал "formules directrices" (трансверсалями) и строил из них греческий квадрат. Затем он накладывал их друг на друга, получая "полный", или греко-латинский квадрат.

Обобщив далее латинские (греческие) квадраты на случай n2 клеток, Эйлер обнаружил, что их внутренняя структура чрезвычайно различна. Они распадаются на многочисленные частные виды, исследование которых носит специфический характер. Число возможных способов построения квадратов огромно. Поэтому ученый ограничился четырьмя видами, являющимися, как принято теперь называть их, квадратами q-шагового типа (). Например, л.к. 4-шагового типа - это квадраты порядка n = 4q, где q - число блоков - циклических л.к. порядка 4. Л.к. 2- и 3-шагового типов определяются аналогичным образом. В л.к. одношагового типа строки и столбцы являются циклическими подстановками элементов. В современной математической литературе их называют циклическими. Примеры указанных видов л.к. для представлены на рис. 1, а-г.

Рис. 1

В процессе исследования Эйлер пришел к выводу о том, что для решения, казалось бы простой на первый взгляд, задачи о 36 офицерах нужно создать специальный математический аппарат. Наиболее важной и трудоемкой его частью является выработка правил нахождения трансверсалей для конкретного значения n. В связи с этим он доказал ряд теорем, позволяющих судить о возможности их построения, а также оценил (приблизительно) их число в зависимости от n и структуры квадратов.

Другой важной задачей Эйлер считал нахождение квадратов конкретного порядка n. Он дал для этого правило и применил его для случая n =2-5, однако не имел успеха в перечислении всех 66 квадратов, необходимых для решения задачи о 36 офицерах. Получив большое число таких квадратов, автор, тем не менее, ни для одного не смог составить полного набора трансверсалей.

На протяжении всего мемуара [11] Эйлер исследовал и более общую задачу об n2 офицерах, доказав существование решений для нечетных и "четно-четных", т.е. кратных 4, значений n. При "нечетно-четных", т.е. кратных 2 значениям, задача не поддавалась решению. Этот факт автор сформулировал в заключительной главе мемуара в виде гипотезы: ни для какого нечетно-четного числа n не существует полного квадрата из n2 клеток. латинский квадрат помехоустойчивый

Обобщая формулировку задачи, Эйлер предложил взять n различных латинских букв и n греческих, после чего разместить n2 их различных упорядоченных пар в ячейках полного nn квадрата так, чтобы в каждой строке, а также столбце были n латинских и n греческих букв, причем никакая из пар букв не повторялась.

Для облегчения дальнейших рассуждений Эйлер заменил n латинских и греческих букв первыми n числами натурального ряда. Некоторые виды таких квадратов уже представлены на рис. 1. Полный квадрат, получающийся при наложении латинского и греческого квадратов, ученый назвал греко-латинским. В современной терминологии его называют ортогональной парой. Пример последней приведен на рис. 2.

Рис. 2

Эйлер пытался найти универсальный способ составления согласованных между собой трансверсалей, выполняя эту операцию путем систематического и исчерпывающего перебора.

Изучая структуру циклических л.к., Эйлер показал, как можно получить из них магические. Для таких квадратов он установил ряд соотношений между элементами, сформулировал правила, доказал важные теоремы, нашедшие применения, указал нерешенные вопросы. Столь же исчерпывающе были исследованы латинские квадраты 2-, 3- и 4-шагового типов. Интересно отметить, что при анализе квадратов q-шагового типа и ныне используются методы, предложенные Эйлером. Однако такие квадраты составляют лишь незначительную часть всего их множества, а ряд проблем остается нерешенным и до наших дней.

В теории л.к. важными являются вопросы их построения, перечисления и отождествления. Исследования этого плана помещены в заключительной главе мемуара [11]. Кроме того, Эйлер пришел к мысли о том, что если полные л.к. существуют, то они должны строиться из нерегулярных л.к. Он указал метод их получения и в итоге сделал заключение не только о невозможности составления полного квадрата из 36 клеток, но и для всех случаев, когда n имеет вид n =2k+1, k N. Это и есть знаменитая гипотеза Эйлера.

В своих исследованиях ученый вплотную подошел к понятию группы подстановок латинских квадратов и общего преобразования, с помощью которого каждый квадрат может быть преобразован в большое число других с теми же свойствами, что и исходный. Поэтому достаточно изучить любой из них. Частным случаем общего преобразования является композиция трех подстановок: элементов, строк, столбцов, а также транспозиция греческого и латинского квадратов. Для последних он указал комбинаторные инварианты. По сути Эйлер предвосхитил возможность разбиения полных квадратов на классы сетевого изоморфизма.

Полное множество л.к. порядка n ученый получил, начав построение латинских прямоугольников с последующим расширением их до квадратов. Заметим, что его метод стал общеупотребительным и был единственным вплоть до 1936 г. [12].

Наряду с построением греко-латинских квадратов Эйлер исследовал полу-диагональные, диагональные и пандиагональные их виды. Ученый указал метод построения из них соответственно полумагических, магических и панмагических квадратов того же порядка. Он доказал, в частности, несуществование греко-латинского пандиагонального квадрата для n, кратного 2 и 3; отметил, что из всякого греко-латинского квадрата можно получить магический квадрат того же порядка, доказал справедливость и обратного построения.

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

Таким образом, в мемуаре Эйлера заложены основы комбинаторной теории, содержащие доказательство теорем, формулировку и решение фундаментальных задач. Следует, однако, заметить, что на протяжении более полувека, прошедшего со времени появления мемуара, идеи и результаты Эйлера не получили сколь-нибудь заметного продвижения. По-видимому, этот факт можно объяснить чрезвычайно высоким авторитетом ученого, получением им настолько значимых результатов, что почти никто не пытался превзойти их. Кроме того, оказало влияние и его пессимистическое заключение относительно практической важности рассмотренной задачи.

Все же со второй половины XIX в. теория л.к. после длительного перерыва получила развитие. Взгляды и замечания математиков стали публиковаться с 90-х гг. главным образом в "Intermйdiare des Mathйmaticiens". Внезапный интерес к тематике можно, на наш взгляд, объяснить замечанием британского математика Р.А. МакМагона о возможности использования л.к. в дисперсионном анализе.

В конце XIX в. проблемой перечисления л.к. порядка 6 заинтересовался французский математик Г. Тэрри, посвятивший ей ряд работ. Целью их было нахождение общего числа нормализованных л.к. и множества неизоморфных между собой квадратов этого порядка. Исчерпывающим перебором он построил 9408 нормализованных л.к. порядка 6. Используя комбинаторные инварианты, он объединил их в 17 типов, назвав "базисными семействами"; 12 из них были классами изоморфизма, а оставшиеся 5 объединены в пары классов. Таким образом, более чем через 120 лет со времен Эйлера Тэрри впервые не только выполнил само перечисление нормализованных латинских квадратов порядка 6, но и осуществил их классификацию [20].

Справедливости ради следует заметить, что в статье Нортона [17] и Сейда [18] упоминается о перечислении л. к. порядка 6, выполненном намного раньше работ Тэрри и приводится ссылка на исследование С. Гюнтера [13]. Из него следует, что одним из тех, кто принимал участие в таком подсчете, был Клаузен, ассистент математика и астронома Шумахера. Он правильно нашел все квадраты этого порядка еще в 1842 г. и показал, что для них не существует ортогональной пары.

Почти одновременно с Тэрри полное алгебраическое решение проблемы перечисления латинских квадратов порядка n опубликовал П.А. МакМагон [15]. Используя созданный им алгебраический аппарат, можно найти различные условия для составления строк квадрата. При этом недопустимые строки отбрасывались, а остальные участвовали при дальнейшем построении. Так продолжалось до тех пор, пока не приходили к конечному результату.

Проблема перечисления л.к. порядка n тесно связана с методами их построения. Некоторые из них зависят от перечисления латинских прямоугольников. С каждым двустрочным нормализованным прямоугольником связано одно из решений широко известной "задачи о встречах", сформулированной еще в самом конце XVII в. Между всеми решениями ее и множеством (2n)-прямоугольников К(2, n) имеет место зависимость К(2, n)=, где означает число перестановок из n элементов, в которых ни один не занимает первоначальной позиции. Общее решение находится в небольшой статье А. Кэли "О латинских квадратах" 1890 г. [9]:

.

В этой же статье Кэли заметил, что нахождение числа трехстрочных латинских прямоугольников является задачей значительно более сложной. Независимая формула была получена лишь в 50-х гг. ХХ в. [21]. Отыскание К(3, n) тесно связано с решением ""задачи о встречах", предложенной Е. Люка в 1891 г. [14].

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

С 30-х гг. ХХ в. проблема ортогональности привлекла внимание ученых. Строгое доказательство несуществования пар ортогональных л.к. порядка n принадлежит Г. Манну [16]. Он же в 1942 г. получил важную теорему: число взаимно ортогональных латинских квадратов (в.о.л.к.) порядка n не превосходит n -1. В этой же статье получены некоторые необходимые и достаточные условия существования как пары, так и r в.о.л.к. Спустя два года Манн получил два необходимых условия для их существования. Попытка улучшить его неравенство не привела к успеху.

В 1938 г., занимаясь вопросами планирования экспериментов, Р.Ч. Боуз показал, как осуществляется связь между множеством из n -1 в.о.л.к. порядка n и конечными проективными (аффинными) плоскостями (к.п.п.) того же порядка [8]. Такой способ описания является универсальным. Заметим, что связь между в.о.л.к. и к.п.п. могла быть установлена гораздо ранее (1906) из результатов Ф.Х. Сэффорда о несуществовании к.п.п. порядка 6 [19]. Однако тогда этот факт остался незамеченным.

Таким образом, вопросами изучения и построения к.п.п стали интересоваться не только геометры, алгебраисты, ученые в области комбинаторного анализа, но и специалисты по планированию экспериментов.

Л.к. и множества в.о.л.к. нашли в наше время многочисленные приложения при проведении экспериментальных работ в промышленности, сельском хозяйстве, педагогике, медицине, фармакологии, торговле, технологических исследованиях, социологии, спорте и т. д. Их используют всюду, где экспериментатору приходится изучать объекты, зависящие от многих факторов, желая выяснить их оптимальные комбинации. Выбор наилучшего плана эксперимента позволяет уменьшить его ошибку, сократить количество, а следовательно, и стоимость опытов. Задачей планирования экспериментов является составление такого плана, который давал бы возможность получить максимум информации при минимуме проведенных опытов.

Планирование экспериментов с использованием л.к. является одним из эффективных способов сокращения перебора комбинаций. Такие планы называются латинскими. Впервые их использовал Рональд Фишер, проводивший с 1919 г. серию работ на Рочемстедской агробиологической станции в Англии. В 30-е гг. он применил л.к. в сельскохозяйственных экспериментах для учета различий в плодородии почв. С тех пор они стали успешно использоваться в многочисленных сферах человеческой деятельности.

Покажем применение л.к. в планировании экспериментов. Пусть исследуемый объект зависит от трех факторов: A, B, C. Каждый изменяется на трех уровнях: строки соответствуют уровням a1, a2, a3 фактора A, столбцы - уровням b1, b2, b3 фактора B, а внутренняя часть л.к. - фактору C с уровнями c1, c2, c3 (табл. 1).

Имеется 33 возможных комбинаций значений A, B, C. Л.к. реализует лишь 32. При этом комбинации выбраны так, что каждое значение одного из трех факторов встречается с каждым из значений двух остальных точно по одному разу, так как расположение элементов квадрата оптимально.

Л.к. порядка n дают возможность планировать трехфакторные эксперименты, когда каждый фактор изменяется на одном и том же числе уровней n. Если же факторов больше, то используются греко-латинские, гипер-греко-латинские квадраты и другие структуры. При употреблении л.к. порядка n число опытов сокращается в n раз. Можно воспользоваться также различными обобщениями л.к. на случай многомерных моделей: латинскими кубами, гиперкубами и т. д. Такое расположение квадратов и их элементов оптимально.

Существует четыре основных типа задач планирования по схеме л.к.: исключение влияния источников неоднородностей, построение ряда предпочтительности, отсеивающий эксперимент, оптимизация. С каждым типом связаны соответствующие эксперименты: элиминирующий, сравнительный (включая экспертную оценку), отсеивающий и экстремальный [2].

Рассмотрим классическую задачу, которую решал еще Фишер: нужно провести эксперимент по сравнению урожайности n сортов пшеницы. Для этого отведен участок земли, но нет уверенности в том, что плодородие почвы на нем однородно. Для уменьшения ошибки поле разбивают на n2 одинаковых участков и засевают сорта пшеницы, занумерованные числами от 1 до n, в соответствии с наугад выбранным л.к. порядка n. Тогда каждый сорт будет выращиваться так, что попадает по одному разу в каждую строку и каждый столбец. Такое расположение устранит влияние на урожайность неоднородности плодородия почвы.

Использование в.о.л.к. дает возможность увеличить число факторов. Например, проводится эксперимент по проверке действия n видов удобрений на n сортов пшеницы. Выращивая пшеницу в соответствии с л.к. A и распределяя удобрения, используя ортогональную пару B, получают схему эксперимента, дающую возможность проверить влияние удобрений на урожайность сортов, исключив влияние плодородия почвы.

Рассмотрим конкретные примеры составления плана эксперимента.

Пример 1. Нужно проверить на разрыв пять видов пряжи, причем намотка ее осуществляется на пяти станках пятью операторами. Строкам выбранного л.к. пятого порядка ставят в соответствие станки с 1, с 2, с 3, с 4, с 5, столбцам - операторов о 1, о 2, о 3, о 4, о 5, а элементам квадрата - виды пряжи x1, x2, x3, x4, x5. Проведение такого эксперимента дает возможность намотать каждый из пяти видов пряжи на каждом из пяти станков каждым из пяти операторов. При этом устраняются эффекты неоднородностей, вызванные различными станками и операторами. Если, кроме того, требуется учесть, что производительность последних зависит от дня пятидневной рабочей недели, то, взяв л.к., ортогональный первому, и сопоставив с ним рабочие дни, добиваются устранения источника неоднородностей, так как каждый станок, каждый оператор и каждый вид пряжи будет участвовать в эксперименте точно один раз каждый день [10].

Пример 2. Компания по производству лекарств хочет получить новое средство от простуды, комбинируя препараты от насморка, антигистаминный и болеутоляющий. Планируется проверить различные комбинации трех средств от насморка, трех антигистаминных препаратов и трех болеутоляющих на четырех группах пациентов в период с понедельника до четверга. Кроме того, каждая составная часть в комбинации должна быть сравнима с безвредным препаратом. Следует найти оптимальное сочетание составных частей. При составлении плана используют три в.о.л.к. порядка 4 (табл. 2).

Каждой из четырех групп пациентов A, B, C, D следует давать лекарства, используя таблицу 3 в соответствии с системой в.о.л.к. При этом буквы b, c, d в первой позиции каждой колонки, соответствующей некоторому дню, относятся к средству от насморка, во второй - к антигистаминному препарату, в третьей - болеутоляющему. Буква a обозначает безвредный препарат, а b, c, d - различные типы составных частей. В соответствии с этим планом группе пациентов B, например, в понедельник дают средство от насморка типа b, антигистаминный препарат типа c и болеутоляющее типа d. Группе A во вторник - средство от насморка типа b, антигистаминный препарат типа b и болеутоляющее типа b [5].

Для более точных исследований допускается проведение экспериментов с повторными опытами, проводя в каждой клетке k наблюдений. Пример такого эксперимента дан ниже.

Пример 3. Исследовалась эффективность трех видов лекарств b1, b2, b3 (фактор B) на трех категориях пациентов c1, c2, c3 (C), которые лечились в трех больницах a1, a2, a3 (A). Из каждой группы взяли по 12 пациентов: по четыре человека, представляющих соответственно три категории c1, c2, c3. Общее число пациентов каждой категории - 12, количество повторных наблюдений - 4 [2].

В задаче использовался л.к. порядка 3 (табл. 4 слева). Справа приведены экспериментальные данные. Строки a1, a2, a3 - больницы; столбцы b1, b2, b3 - виды лекарств; элементы л.к. c1, c2, c3 - категории пациентов. В первом опыте четыре пациента категории c3 из больницы a2 принимали лекарство b1, в опыте 2 - четыре пациента категории c2 из больницы a2 - лекарство b2, и т. д. Эффективность действия лекарств условно оценивалась по 12-балльной системе. Результаты наблюдений помещены справа. Полученные данные были подвергнуты статистическому анализу для выявления эффективных лекарств.

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

Пример 4. При проведении различных соревнований (теннисных, хоккейных, шахматных, футбольных и т. д.) используют определенные системы: олимпийскую, круговую, схевенингенскую и др. В частности, последняя применяется для проведения командных встреч в турнире двух команд, когда каждый участник одной из них встречается с каждым участником другой. Требуется составить расписание встреч. Если в каждой команде n участников, то в матче проводится n туров. Пример расписания игр для n = 4 приведен в табл. 5.

Строки (столбцы) квадрата соответствуют игрокам команды I или II. В клетках aij (i, j = ) указан номер тура, в котором встречаются соответствующие участники. По условиям соревнования таблице соответствует л.к. Пусть на правила проведения соревнования наложены дополнительные ограничения: а) все участники должны играть одинаковое число партий белыми и черными фигурами; б) каждая команда в каждом туре должна играть одинаковое число партий белыми и черными фигурами. В этом случае количество участников четное. Для выполнения условий а) и б) берут ортогональную пару в л.к. A и B. Накладывают квадрат B (табл. 5) на A и заштриховывают все клетки A, в которые попадали четные цифры из B. Заштрихованная клетка означает: игрок команды II играет черными. Нетрудно проверить, что условия а) и б) при этом выполняются [7].

Приведенные выше примеры показывают возможности использования л.к. при проведении самых разнообразных экспериментов, сфера которых непрерывно расширяется.

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

Передача данных в общем случае сводится к передаче по каналу связи знаков некоторого конечного алфавита. Как правило, такой канал не является идеальным в том смысле, что переданный символ не всегда будет принят правильно. Например, одна ЭВМ может быть связана с другой через спутник. В этом случае обычно используют двоичный алфавит {0, 1}, а канал связи реализуется электромагнитным полем между поверхностью Земли и спутником. При воздействии внешних помех электромагнитные сигналы могут исказиться до неузнаваемости. Они особенно чувствительны к атмосферным условиям, воздействию солнечных пятен. За ошибки приходится расплачиваться дорогой ценой.

Уменьшения (исключения) ошибок можно добиться, применяя коды. Процесс передачи (хранения) информации в общем случае можно представить моделью связи, изображенной на схеме, приведенной ниже.

На последнем уровне модулятор преобразует сообщение в сигналы, передающиеся по каналу. Они поступают в канал передачи, где искажаются шумом или подлежат хранению. Канал - физическая среда, используемая для передачи. Искаженный сигнал поступает в декодер (устройство, восстанавливающее посланное сообщение), а затем направляется его получателю.

Если в системе передачи предусмотрена обратная связь, то принятие непонятного сообщения приводит к его игнорированию и посылается запрос на повторение передачи. Если же возможности повторить сообщение нет, то отказ от сообщения столь же катастрофичен, как и ошибка при декодировании (например, при получении неверной команды на ракете или межпланетном корабле).

Для уменьшения нежелательного эффекта искажения за счет кодирования к k символам сообщения добавляется r проверочных и по каналу передается n = k + r символов. Дополнительные символы дают возможность обнаруживать и (или) исправлять ошибки. Для произвольно заданной последовательности из k символов сообщения передатчик должен иметь некоторое правило выбора r проверочных символов. Построение его и является задачей кодирования.

Введем основные понятия. В общем случае под кодовым словом понимается любая конкретная последовательность, которая может быть передана кодером. При блоковом коде последовательность символов сообщения разбивается на отрезки, содержащие по k символов. В дальнейшем при кодировании операции производятся над каждым отдельным блоком. Ему ставится в соответствие набор из n символов (n > k). Он и является кодовым словом. Величина n называется его длиной.

Таким образом, на вход кодера поступает последовательность информационных символов. На выходе появляется другая последовательность с бульшим числом символов. Удлиненное слово несет некоторую дополнительную информацию о сообщении. Анализируя ее, можно обнаружить и (или) исправить ошибки, допущенные при передаче (хранении).

Обычно кодовое слово - упорядоченная последовательность бинарных разрядов (такой код называется бинарным), но в общем случае кодовый алфавит может состоять из q символов. Он называется q-арным, т. е. набором кодовых слов длиной n, составленных из алфавита, содержащего q букв. Одной из основных целей удлинения слов является возможность увеличения расстояния Хэмминга d(a, b) между словами кода a = (a1, a2, …, an) и b = (b1, b2, …, bn) - числа мест, в которых отличаются эти два слова. Например, в кодовых словах a = (1, 2, 4, 3) и b = (2, 2, 1, 3) различными являются элементы, стоящие на первом и третьем местах. Поэтому d(a, b) = 2. Если же a = (1, 1, 0, 1, 0), а b = (0, 0, 1, 1, 0), то d(a, b) = 3.

Кодовым расстоянием Хэмминга называется минимальное расстояние Хэмминга между словами кода. Это - одно из главных понятий теории кодирования, дающее возможность обнаруживать и даже исправлять ошибки. Коды, способные находить ошибки в одном или более разрядах полученного кодового слова, называются устанавливающими, или обнаруживающими ошибки. Они чаще всего используются в двусторонних каналах передачи, т. е. когда имеется обратная связь. При обнаружении ошибки в этом случае можно послать запрос на повторение передачи. Если по полученному слову с одним или более ошибочными разрядами можно восстановить переданное слово, то такой код называется исправляющим, или корректирующим ошибки.

Принцип обнаружения (исправления) ошибок по кодовому расстоянию Хэмминга заключается в следующем: если код таков, что минимальное расстояние Хэмминга между любыми двумя словами равно 2, то он обнаружит одну ошибку, так как любое слово, переданное с единственной ошибкой, будет бессмысленным (оно не совпадает ни с одним из кодовых слов). В то же время двойная ошибка может не обнаружиться (кодовое слово, переданное с двумя ошибками, может совпасть с кодовым словом, отличающимся от переданного в двух разрядах). Код с кодовым расстоянием 3 может устанавливать две ошибки и исправлять одну: если полученное слово имеет не более одной ошибки, то оно будет ближе всего к истинному. Следовательно, такой код может исправлять одну ошибку, двойные же ошибки будут лишь обнаружены.

Например, двоичный код, приведенный в табл. 6, имеет длину кодового слова n = 5 и d = 3. Два левых символа в нем - символы сообщения, а остальные три - проверочные. Последние выбраны с учетом кодового расстояния, равного 3. Этот код обнаруживает две и исправляет одну ошибку. Поэтому схема декодирования будет исправлять одну однократную ошибку. Поясним: пусть принято слово 01010. Сравнивая его с кодовыми, замечаем, что оно ближе всего к кодовому слову 01011, которое воспринимаем как переданное. Тем самым устраняем одну ошибку. Если же принято слово 01111, то расстояние Хэмминга между ним и третьим, а также четвертым кодовыми словами равно 2, поэтому восстановить его нельзя. Доказанные теоремы для общего случая утверждают, что код с кодовым расстоянием Хэмминга d обнаруживает до d - 1 и исправляет до (d - 1)/2 ошибок [10].

Покажем, как с помощью латинского квадрата порядка q построить q-арный код с q2 кодовыми словами и кодовым расстоянием d = 2. Пусть L = ||aij|| - л.к. порядка q, тогда q2 упорядоченных троек (i, j, aij), рассматриваются как множество кодовых слов, определенных на алфавите L. Любые два элемента из тройки однозначно определяют третий, а потому расстояние между словами d = 2. Например, квадрату порядка 3 соответствует определенный код (табл. 7).

Таблица 7

Имеет место более общее утверждение: ортогональная система л.к. A(), = {A1, A2, …, At}, содержащая t л.к. порядка q, эквивалентна коду, состоящему из q2 слов длиной t + 2, взятых из q-буквенного алфавита L с кодовым расстоянием d = t + 1. В этом случае код состоит из слов вида (a, b, A1(a, b), A2(a, b), …, An(a, b)), где (a, b) L. Так, паре ортогональных л.к. порядка 4 соответствует код, приведенный в табл. 8.

Оказывается, что ортогональные системы, и только они, дают возможность построения 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. № 7166-В 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 77 squares // Ann. Eugenics. 1939. Vol.9. P.269-307.

18. Sade A. An omission in Norton's list of 77 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.

Размещено на Allbest.ru