|
|
расстоянием между всевозможными словами X''=(x'i ,
. . ,,'xi) и Х"= (xi, . . ., xi) кода. Для того чтобы код обнаруживал все комбинации из s ошибок и исправлял все комбинации из t ошибок, необходимо и достаточно, чтобы кодовое расстояние было равно s-H+1.
Широкий класс кодов для симметричного канала составляют линейные (групповые) коды [3], напр. коды Хэммйнга, широко применяющиеся для защиты информации в основной памяти ЭВМ, Код Хэмминга обладает кодовым расстоянием rf=3, исправляет однократные ошибки и обнаруживает двукратные. Он имеет проверочные разряды, расположенные в позициях с номерами 2°, 2, 22, * . . Линейный код зада╦тся
парой матриц: порождающей: Gnxi~\\gj II. / = li n, и проверочной #ftxj. Строки gj порождающей мат-
рицы ≈ линейно независимые векторы, образующие базис пространства, содержащего 2" элементов ≈ кодовых слов. Каждая из строк проверочной матрицы ор-
≈ Q.
тогональна строкам gy, / ≈ !,«, и
Кодер линейного кода образует кодовые слова по
правилу XT≈UTG. Модель искажений предполагает, что в канале с X посимвольно суммируется шумовой вектор Z, образуя слово Y= X-\-Z. Идея декодирования заключается в образовании
произведения 5Г=У Яг, называемого синдромом. Равенство 5=0 означает, что Z≈ О, либо ошибка
ь
относится к необнаруживаемым. Синдром имеет 2≈1 ненулевых реализаций, каждая из к-рых может быть использована для указания на произошедшую ошибку.
Циклич. коды входят как подкласс в групповые коды. В них вместе со словом X входят и все его циклич. перестановки. Кодовые слова образуются как произведение двух полиномов: V (Е) степени п ≈ 1, коэф. к-рого составляют информационное слово £7, и порождающего g (Е) степени I≈ п, неприводимого и делящего без остатка двучлен (\-\-E1-). Декодирование заключается в делении принятого слова (полинома) на g(E), Наличие ненулевого остатка укажет на присутствие ошибки. Циклич. коды, как правило, несистематические.
Спец. циклич. коды предназначены для обнаружения и исправления пачек ошибок, напр, коды Файра, определяемые порождающими полиномами вида g (Е) = =р(Е)(Ес-\-\), где р(Е] ≈ неприводимый полином, а величина с определяется длиной исправляемых и обнаруживаемых пачек ошибок.
Пачки ошибок характерны для запоминающих устройств с магн. носителями, в частности для накопителей на магн. дисках (НМД) совр. ЭВМ (см. Памяти устройства). Для защиты данных в . НМД поэтому широко используется К. и. циклич. кодами, осуществляемое аппаратными средствами.
Арифметические коды предназначены для обнаружения ошибок, возникших при выполнении арифметпч. операций на ЭВМ. В теории арифметич. кодирования вводятся понятия веса, расстояния и ошибки, отличные от хэмминговых. Арифметич. вес числа определяется как мин. число слагаемых в представлении нисла в виде Лг = ^,о/2/|*1 а/£(1, ≈1), Ошибки, в ре-
зультате к-рых величина числа изменяется па ±=2!", 1=0, 1, 2, . . ., яаз, арифметическими. Арифметич. расстояние между Nt и ЛГ2 ≈ арифметич. вес разности j NI≈ Л" 2 |), равно кратности ошибки, переводящей .число NI в ЛГ2, и определяет корректирующую способность арифметич. кода подобно расстоянию Хэмминга. В распростран╦нных А TV-кодах кодирование числа N ≈ операнда ≈ осуществляется умножением его на специально подобранный множитель А. Так, 3,4 -код, имея кодовое расстояние 2, обнаруживает одиночные ошибки пут╦м деления суммы на 3. Ошибки обнаруживаются пои ненулевом остатке; величина арифметич. ошибки 2' не делится на 3 нацело. Кроме одиночных
при Л≈3 обнаруживается и часть двойных ошибок ≈ те, при к-рых правильный и ошибочный результат имеет несовпадающие остатки от деления на 3.
Криптография осуществляется пут╦м подстановки, когда каждой букве шифруемого сообщения ставится в соответствие «предел, символ (напр,, др. буква), либо пут╦м перестановки, когда буквы внутри искусственных блоков текста меняются местами, либо комбинацией этих методов. Шенноном показано, что возможны криптограммы, не поддающиеся расшифровке за приемлемое время [5].
Лит.: 1) Стахов А. П., Введение в алгоритмическую теорию измерения, М., 1977; его же. Коды золотой пропорции, М., 1984; 2) АкушскийИ., ЮдицкиЙ Д., Машинная арифметика в остаточных классах, М.г 1968; 3) Г а л-лагер Р., Теория информации и надежная связь, пер, с англ., М., 1974; 4) Д а д а е в Ю. Г., Теория арифметических кодов, М., I9S1; 5) АрШинОв М, Н., Садовский Л. Е., Коды и математика, М., 1983. Л. Н. Ефимов.
КОЛЕБАНИЯ ≈ движения или состояния, обладающие той или иной степенью повторяемости во времени. К. свойственны всем явлениям природы: пульсирует излучение зв╦зд, внутри к-рых происходят циклич. ядерные реакции; с высокой степенью периодичности вращаются планеты Солнечной системы (а всякое вращение можно представить себе как два одновременных. К. во взаимно перпендикулярных направлениях); движение Луны вызывает приливы и отливы на Земле; в земной ионосфере и атмосфере циркулируют потоки заряж, и нейтральных частиц; ветры возбуждают К. и волны на поверхностях водо╦мов и т. д. Внутри любого живого организма ≈ от одиночной клетки до высокоорганизованных их популяции ≈ непрерывно происходят разнообразные, ритмично повторяющиеся процессы (биение сердца, колебания психич. состояний и др.)* В виде сложнейшей совокупности К. частиц и полей (электронов, фотонов, протонов и др.) можно представить «устройство» микромира.
В технике К. выполняют либо определ. функциональные обязанности (колесо, маятник, колебат, кок-тур, генератор К. и т. д.), либо возникают как неизбежное проявление физ. свойств (вибрации машин и сооружений, неустойчивости и вихревые потоки при движении тел в газах и т. д.).
В физике особо выделяются колебания двух видов ≈ механич. и электромагнитные и их эл.-механич. комбинации. Это обусловлено той исключит, ролью, к-рун> играют гравитац, и эл.-магн. взаимодействия в мае-штабах, характерных для жизнедеятельности человека. С помощью распространяющихся механич. К. плотности и давления воздуха, воспринимаемых нами как звук, а также очень быстрых колебаний электрич. и магн. полей, воспринимаемых нами как свет, мы получаем большую часть прямой информации об окружающем мире.
К. любых физ. величин почти всегда сопровождаются попеременным превращением энергии одного вида в энергию другого вида. Так, оттягивая маятник (груз на нити) от положения равновесия, мы увеличиваем потенц. энергию груза, запас╦нную в поле тяжести; при отпускании он начинает падать, вращаясь около точки подвеса как около центра, и в крайнем ниж. положении вся потенц. энергия превращается в кинетическую, поэтому груз проскакивает это равновесное положение, и процесс перекачки энергия повторяется, пока рассеяние (диссипация) энергии, обусловленное, напр., трением, не привед╦т к иол-ному прекращению К. В случае К. электрич. зарядов и токов в колебательном контуре или электрич. и магн. полей в эл.-магн. волнах роль потенциальной обычко играет электрич. энергия, а кинетической ≈ магнитная. Иногда, когда речь ид╦т о К, тепловых, хим. и особенно информац. величин, такой энергетнч. подход несколько условен, но вполне плодотворен.
Теория колебаний и волн- Изучение К. на разных этапах играло стимулирующую роль в развитии науки. Так, исследования К. маятника
О
ас
399
