Информатика — курс лекций. Курс лекций для студентов по направлениям 230100. 62 Информатика и вычислительная техника
 Скачать 2.08 Mb.
|
|
Тема 5. Логические функции Основу любого дискретного вычислительного устройства составляют элементарные логиче- ские схемы. Работа этих схем основана на законах и правилах алгебры логики, которая оперирует двумя понятиями: истинности и ложности высказывания. Алгебра логики — раздел математики, изучающий высказывания, рассматриваемые со сто- роны их логических значений (истинности или ложности) и логических операций над ними. Высказывание — некоторое предложение, в отношении которого можно однозначно сказать, истинно оно или ложно. Аппарат алгебры логики (булевой алгебры) создан в 1854 г. Дж. Булем как попытка изучения логики мышления математическими методами. Впервые практическое применение булевой алгебры было сделано К. Шенноном в 1938 г. для анализа и разработки релейных переключательных сетей, результатом чего явилась разработка метода представления любой сети, состоящей из совокупности переключателей и реле, математическими выражениями и принципов их преобразования на основе правил булевой алгебры. Ввиду наличия аналогий между релейными и современными электронны- ми схемами аппарат булевой алгебры нашёл широкое применение для их структурно- функционального описания, анализа и проектирования. Использование булевой алгебры позволяет не только более удобно оперировать с булевыми выражениями (описывающими те или иные элек- тронные узлы), чем со схемами или логическими диаграммами, но и на формальном уровне путём эквивалентных преобразований и базовых теорем упрощать их, давая возможность создавать эко- номически и технически более совершенные электронные устройства любого назначения. Операции булевой алгебры часто встречаются и в программном обеспечении вычислительных устройств, где они используются для замены аппаратной логики на программную. Аппарат булевой алгебры, как и любая другая формальная математическая система состоит из трёх множеств: элементов, операций над ними и аксиом. Элементы . Схемы вычислительных устройств можно условно разделить на три группы: ис- полнительные, информационные и управляющие. Первые производят обработку информации, пред- ставленной в бинарной форме; вторые служат для передачи бинарной формы информации; третьи выполняют управляющие функции, генерируя соответствующие сигналы. Во всех случаях в тех или иных точках логических схем сигналы двух различных уровней могут представляться бинарными символами { } или логическими значениями {Истина (True), Ложь (False)}. Поэтому множество элементов булевой алгебры выбирается бинарным { }, а сама алгебра называется бинарной, или переключательной. Её элементы называются константами, или логическими 0 и 1, которым в ря- де случаев соответствуют бинарные цифры, в других случаях — логические значения, соответственно ложь (False) и истина (True). В дальнейшем для обозначения булевых переменных будем использо- вать буквы латинского алфавита — , , , …. Набор переменных , , , … может рассматриваться как -разрядный двоичный код, разрядами которого являются эти переменные. Операции . Основными, или базовыми, операциями булевой алгебры служат: И (AND), ИЛИ (OR) и НЕ (NOT). Операция И называется логическим умножением или конъюнкцией и обозначается знаком «&». Операция ИЛИ называется логическим сложением или дизъюнкцией и обозначается знаком «˅». Операция НЕ называется логическим отрицанием или инверсией (дополнением) и обо- значается знаком «‾». 100 При выполнении операций применяются отношение эквивалентности «=» и скобки «()», кото- рые определяют порядок выполнения операций. Если скобок нет, то операции выполняются в сле- дующей последовательности: логическое отрицание, логическое умножение и логическое сложение. На письме знак операции конъюнкции часто опускают. Основные законы и постулаты алгебры логики Аксиомы (постулаты) алгебры логики 1. Дизъюнкция двух переменных равна 1, если хотя бы одна из них равна 1. 2. Конъюнкция двух переменных равна 0, если хотя бы одна переменная равна 0. 3. Инверсия одного значения переменной совпадает с её другим значением. Законы алгебры логики 1. Законы однопарных элементов: а) универсального множества: б) нулевого множества: 2. Законы отрицания: а) двойного отрицания: ̿ б) дополнительности: ̅ ̅ в) двойственности (де Моргана): ̅̅̅̅̅ ̅ ̅ ̅̅̅ ̅ ̅ 3. Комбинационные законы: а) тавтологии: б) коммутативные: в) ассоциативные (сочетательные): ( ) ( ) ( ) ( ) г) дистрибутивные (распределительные): ( ) ( )( ) д) закон абсорбции (поглощения): ( ) е) склеивания: ̅ ( )( ̅) Законы двойственности де Моргана были обобщены Шенноном на произвольное количество двоичных переменных: инвертирование произвольной комбинации двоичных переменных, связан- ных знаками дизъюнкции и конъюнкции, эквивалентно инвертированию комбинаций переменных с одновременной заменой конъюнкции на дизъюнкцию, и наоборот: ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅ ̅̅̅ ̅̅̅ ̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅ ̅̅̅ ̅̅̅ ̅̅̅ 101 Представление функций алгебры логики Булевой (переключательной, двоичной) функцией называется двоичная переменная , значе- ние которой зависит от значений других двоичных переменных ( , , …, ), именуемых аргумен- тами: ( ). Задание булевой функции означает, что каждому из возможных сочетаний аргументов по- ставлено в соответствие определённое значение . При аргументах общее число сочетаний . Так как каждому сочетанию аргументов со- ответствует два значения функции (0, 1), то общее число функций Булевая функция может быть задана на словах, таблично, алгебраически или числовым спо- собом. Для алгебры логики установлено, что если ( ), где и — двоичные функции, т.е. ( ), ( ), то ( ). Операцию замены одной функции другими функциями называют суперпозицией . Эта опера- ция даёт возможность с помощью функций малых аргументов получить функции большего числа ар- гументов. Так, при помощи суперпозиции можно получить функцию с требуемым числом аргумен- тов, используя только функцию двух аргументов. При помощи набора булевых функций двух аргументов можно описать любую цифровую си- стему. На практике используют не все функции, а лишь те из них, которые методом суперпозиции обеспечивают представление любой другой функции. Набор таких функций называют функциональ- но полным набором (ФПН). Существует несколько ФПН. В качестве ФПН применяются дизъюнкция, конъюнкция и инвер- сия. Этот набор называют основным ФПН (ОФПН). Кроме ОФПН, широкое применение получили: функционально-полная система, включающая в себя только одну функцию — функцию Пирса (ИЛИ-НЕ); функционально-полная система, включающая в себя только одну функцию — функцию Шеф- фера (И-НЕ). При помощи этих функций можно построить любую цифровую систему. Синтез логических устройств в базисе ОФПН состоит из представления этих функций в нор- мальных формах и минимизации Нормальной формой считают представление этих функций посредством суперпозиций вспо- могательных функций — минтермов и макстермов. Минтермом называют функцию, которая принимает 1 только при одном значении аргумен- тов и 0 — при других (иногда в литературе используется термин «конституэнта единицы»). 102 Макстермом называют функцию, которая принимает 0 только при одном значении аргумен- тов и 1 — при другом (иногда в литературе используется термин «конституэнта нуля»). Форму представления функций посредством суперпозиции их минтермов называют формой представления посредством совершенных дизъюнктивных нормальных форм (СДНФ), а посредством суперпозиции макстермов — посредством совершенных конъюнктивных нормальных форм (СКНФ). Любую функцию можно представить путем суперпозиции их минтермов (СДНФ) или макс- термов (СКНФ). Тема 6. Помехоустойчивое кодирование Бурное развитие вычислительной техники, а также быстрый рост важности и актуальности за- дач, решаемых её средствами, заставили искать пути повышения надёжности переработки информа- ции в вычислительных устройствах и системах. Использование результатов теории помехоустойчиво- го кодирования для этих целей оказалось плодотворным и успешным. Для контроля правильности функционирования цифровых автоматов применяются различные помехоустойчивые коды, позво- ляющие в сочетании со специальными схемами обнаружения ошибок оперативно сигнализировать о правильности функционирования цифрового автомата. Основные определения теории помехоустойчивого кодирования Двоичным вектором длины называется -компонентный вектор ( ), каж- дая компонента которого может принимать значение 0 либо 1. Двоичным кодом называется множество двоичных векторов. Двоичный код называется равномерным , если он содержит только векторы одинаковой дли- ны. В противном случае код называется неравномерным В дальнейшем будем рассматривать только равномерные коды, так как они находят широкое распространение при проектировании надёжных вычислительных средств. Все приводимые ниже определения даются применительно к равномерным двоичным кодам. Двоичный код называется натуральным , если он содержит все возможные векторы задан- ной длины. Длина двоичного кода равна длине его двоичного вектора. Мощность двоичного кода — число всех различных векторов кода. Мощность кода обо- значается | |. Натуральный двоичный код длины имеет мощность, определяемую по формуле | | Расстоянием в смысле Хэмминга между двумя двоичными векторами и (обозначается ( )) называется число двоичных компонент, в которых эти векторы отличны друг от друга. Весом в смысле Хэмминга двоичного вектора (обозначается ( )) называется число еди- ниц в векторе Минимальным расстоянием в смысле Хэмминга кода (обозначается ) называется наименьшее из всех возможных расстояний Хэмминга для векторов кода . Ошибкой называется искажение вектора кода. Кратностью ошибки (обозначается ) называ- ется число компонент вектора, искажаемых ошибкой. 104 Общий подход к обнаружению ошибок Общий подход к обнаружению ошибок, возникающих в векторах некоторого кода , основан на следующем простом допущении: векторе ошибкой не принадлежит коду . Если это выполняется, то, построив схему, анализирующую принадлежность векторов коду , ошибку можно обнаружить. Очевидно, натуральный двоичный код не обладает обнаруживающей способностью к ошибкам, так как произвольное искажение любого вектора этого кода переводит его в вектор, также принадлежа- щий натуральному коду. Для получения кода с обнаружением ошибки (например, -кратной) из натурального кода необходимо удалить некоторые векторы, руководствуясь следующим соображе- нием. В натуральном коде выбирается любой вектор. Выбранный вектор относят к коду с обнаруже- нием -кратной ошибки. Все векторы, отстоящие от выбранного на расстоянии Хэмминга из натурального кода, вычёркиваются. Из оставшихся векторов натурального кода снова выбирается один вектор. Выбранный вектор относят к коду с обнаружением -кратной ошибки, а все векторы, отстоящие от выбранного на расстоянии Хэмминга из натурального кода, вычёркивают. Опи- санную процедуру повторяют до тех пор, пока все векторы натурального кода не будут исчерпаны. В результате получаем код с обнаружением -кратной ошибки Очевидно, все векторы такого кода должны отстоять на расстоянии Хэмминга , так как векторы с меньшим кодовым расстояни- ем удалены из натурального кода. Таким образом, для кода с обнаружением -кратной ошибки должно соответствовать условию . Полученное условие относится к одному из основных положений теории помехоустойчивого кодирования. Общий подход к исправлению ошибок Если при обнаружении ошибок достаточно знать, принадлежит ли вектор коду, то для ис- правления ошибок необходимо знать номера разрядов вектора, искажаемых ошибкой. Очевидно, если два вектора кода при искажении некоторых разрядов дают один и тот же вектор с ошибкой, то по виду вектора с ошибкой восстановить правильный вектор не удаётся. Поэтому, общий подход к исправлению ошибок в векторе кода базируется на следующих допущениях: вектор с ошибкой коду не принадлежит; если код корректирует ошибку кратности , то любые два вектора кода при искажении ошибкой кратности не должны давать один и тот же вектор с ошибкой. Выполнение второго условия приводит к необходимости разнесения любых двух векторов , кода с коррекцией -кратной ошибки на расстояние Хэмминга ( ) . Действительно, если расстояние меньше, найдутся такие ошибки кратности , которые могут перевести векторы и в один и тот же вектор с ошибкой. Таким образом, для коррекции -кратной ошибки в векторах кода необходимо, чтобы вы- полнялось соотношение . Полученное условие — основополагающее в теории помехо- устойчивого кодирования. Для получения кода с коррекцией -кратной ошибки из натурального кода необходимо удалить некоторые векторы, руководствуясь следующими соображениями. В натураль- ном коде выбирается любой вектор. Выбранный вектор относят к коду с коррекцией -кратной ошибки. Все векторы, отстоящие от выбранного на расстоянии Хэмминга , вычёркивают из натурального кода. Среди оставшихся векторов натурального кода выбирают следующий вектор, от- нося его к коду с коррекцией -кратной ошибки и т.д. Процедуру повторяют до тех пор, пока все век- торы кода не будут исчерпаны. 105 Информационная избыточность помехоустойчивых кодов Для обнаружения (исправления) ошибок натуральные коды не могут быть использованы. Для получения какой-то обнаруживающей способности из натурального кода необходимо удалить неко- торые векторы. Иными словами, натуральный двоичный код разбивается на два множества векто- ров: запрещённых и рабочих. Последнее эквивалентно тому, что передаваемые по каналам связи сообщения кодируются с избыточностью, т.е. в натуральный код вводятся дополнительные (избы- точные) разряды, необходимые для обнаружения или исправления ошибок в коде. Такие разряды обычно называют проверочными. Коды, у которых проверочные разряды всегда расположены в од- них и тех же позициях, называются систематическими. В общем случае, неизвестно, какое мини- мальное число проверочных разрядов нужно добавить к натуральному коду, чтобы образовавшийся систематический код обладал заданной обнаруживающей (корректирующей) способностью. Это свя- зано с поиском минимума функции ( ) ( ), где — длина систематического кода; — число информационных разрядов, а — минимальное расстояние систематического кода в смысле Хэмминга. Точно определить минимум функции не удаётся. Существуют только верхние и нижние оценки, которые делают это приближённо. К нижней оценке можно отнести так называемую границу Хэмминга: min 2 1 0 2 d i i n k C где — число сочетаний из по , а к верхней оценке — границу Варшамова—Гильберта: 1 2 0 min 2 d i i i n k n C где ( ) — число проверочных разрядов систематического кода. Существуют и другие оценки: граница Плоткина, Элайса и т.д. Для кодов с различными параметрами ( ) имеются специаль- ные таблицы, полученные конкретным просчётом и определяющие минимальное число добавляе- мых проверочных разрядов. Код Хэмминга Современные запоминающие устройства состоят из огромного количества запоминающих элементов, каждый из которых хранит бинарное значение — 0 или 1. При работе подобных устройств могут возникать ошибки, обусловленные воздействием различных факторов. В этом случае для по- вышения надёжности работы запоминающих устройств используют специальные коды. Различают коды, обнаруживающие ошибки, и корректирующие коды, позволяющие обнару- живать место, где произошла ошибка, и исправлять её. Простейшим способом обнаружения ошибок является проверка на чётность. В этом случае к битам передаваемого или хранимого -разрядного слова добавляется ещё один бит — бит чётности, значение которого подбирается таким образом, чтобы среди получившихся разрядов ( ) обязательно было чётное число единиц. Такой избыточный код позволяет лишь констатировать факт наличия ошибки в слове даже без указания места, где она произошла. Для повышения надёжности работы запоминающих устройств используют корректирующие коды. Принцип построения корректирующих кодов заключается в том, что к каждому хранимому или 106 передаваемому -разрядному слову добавляют битов с соответствующим их расположением сре- ди битов -разрядного слова. Подобные -разрядные коды ( ) были впервые рассмотре- ны в 1948 г. Р. Хэммингом и с тех пор обычно называются кодами Хэмминга. Рассмотрим принцип построения кода Хэмминга для 16-разрядного слова данных ( ), исправляющего все одиночные ошибки. Сначала определим необходимое число проверочных разрядов ( ) из соотноше- ния: , откуда для находим и . Далее все биты -разрядного слова нумеруются слева направо начиная с 1, при этом все би- ты, номера которых равны степени числа 2, являются битами чётности, а остальные — информаци- онными. В 1, 2, 4, 8 и 16 разрядах данного кода располагаются биты чётности, а в разрядах 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20 и 21 биты данных слова 16-разрядного исходного слова. Каждый бит чётности используется для контроля лишь определенных разрядов -разрядного слова. Номера контролируемых разрядов для каждого бита чётности приведены в таблице 2. Таблица 2 — Номера битов чётности и контролируемых ими разрядов слов в коде Хэмминга Контрольный разряд/номер бита кода Хемминга Контролируемые разряды 1/1 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33… 2/2 2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31 34… 3/4 4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31 36… 4/8 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31 40… 5/16 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 48… 6/32 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48… Как видно из таблицы, в число контролируемых разрядов включается и тот разряд, где распо- ложен сам бит чётности. При этом содержимое бита чётности устанавливается так, чтобы суммарное число единиц в контролируемых им разрядах было чётным. Код, образованный значениями контрольных разрядов, называют дополнительным кодом. Дополнительный код можно также получить путём инвертирования результата поразрядного сложе- ния (т.е. сложения по модулю 2) номеров тех разрядов кода данных, значения которых равны 1. Предположим теперь, что из-за воздействия каких-либо возмущающих факторов обнулится одна из единиц в коде Хэмминга. В этом случае номер искажённого разряда определяется суммой номеров неправильных битов чётности. Определить номер искажённого разряда можно также следующим способом. После считывания информационного кода данных с искажённым разрядом для него вновь рассчитывается дополнительный код и сравнивается с исходным. Фиксируется код сравнения (по- 107 разрядная операция отрицания равнозначности), и если он отличен от нуля, то его значение и есть номер искажённого информационного разряда. Применение корректирующего кода Хэмминга означает, что каждое слово памяти содержит не 16 бит, а 21 бит. Пять лишних битов в каждом слове — это биты чётности. Они недоступны пользо- вателю, так как зарезервированы для образования корректирующего кода. Линейные групповые коды В практике построения надёжных средств вычислительной техники широкое распростране- ние находят линейные групповые коды, отличающиеся достаточно просто реализуемыми функциями декодирования и несложным способом задания. Линейным групповым кодом называется конечная аддитивная коммутативная группа , элементами которой являются двоичные векторы, в качестве операции группы выбрана операция суммы по модулю 2. Линейные групповые коды могут быть заданы двумя способами: перечислением векторов; матричным представлением. Матричное представление позволяет компактно описывать линейные коды большой мощно- сти и однозначно задавать процедуру их декодирования. Линейно-независимыми двоичными векторами , , …, называются векторы, для кото- рых выполняется соотношение , где { } — скаляры, а — знак операции суммы по модулю 2. Максимальный набор линейно-независимых двоичных векторов образует порождающую матрицу некоторого кода. Любой вектор кода, не принадлежащий матрице, может быть получен как сумма некоторого числа векторов порождающей матрицы. Линейные групповые коды обычно задаются порождающей матрицей, представленной в так называемой левой канонической форме: ‖ ‖ ‖ ‖ , где — единичная матрица информационных разрядов линейного кода формата (как было по- казано выше, такая матрица порождает натуральный двоичный код длины ); — матрица прове- рочных разрядов линейного кода, содержащая ( ) столбцов и строк. Так как единичная матрица ( ) порождает натуральный двоичный код длины , мощность которого равна , то её формат в матрице определяет мощность линейного группового кода, определяемую по формуле . Структура матрицы влияет на обнаруживающую и корректиру- ющую способность линейного кода. 108 Минимальное расстояние линейного группового кода может быть определено в соот- ветствии со следующим простым алгоритмом: 1. Выписать все векторы линейного группового кода. 2. Для каждого ненулевого вектора найти его вес в смысле Хэмминга. Минимальный вес нену- левого вектора и равен Справедливость алгоритма вытекает из принадлежности нулевого вектора линейному груп- повому коду. Действительно, расстояние в смысле Хэмминга между нулевым вектором и вектором с минимальным числом единиц определяет рассматриваемого кода. Так как минимальный вес в смысле Хэмминга , то код имеет и позволяет об- наруживать ошибки кратностью , корректировать ошибки кратностью . Действительно, для обнаружения -кратных ошибок должно выполняться условие или . Для коррекции -кратных ошибок должно выполняться условие или Порождающую матрицу группового линейного кода длины с информационными разря- дами можно построить, руководствуясь следующими правилами: 1. Все векторы порождающей матрицы должны быть различны и линейно-независимы. 2. Нулевой вектор не должен входить в число векторов порождающей матрицы. 3. Каждый вектор порождающей матрицы должен иметь вес в смысле Хэмминга 4. Расстояние в смысле Хэмминга между любыми двумя векторами и порождающей мат- рицы должно удовлетворять соотношению ( ) Проверочная часть порождающей матрицы (матрица ) строится в соответствии со следую- щими правилами: 1. Вес в смысле Хэмминга каждого проверочного вектора должен удовлетворять соотношению 2. Вес проверочного вектора , являющегося суммой по модулю 2 двух любых проверочных векторов, должен удовлетворять соотношению Порождающая матрица линейного кода, построенная в соответствии с приведёнными реко- мендациями, должна быть проверена на соответствие полученного кода требуемой обнаруживаю- щей и корректирующей способности. Для этого по полученной матрице выписываются все векторы линейного кода и находится . Отметим, что любой проверочный столбец порождающей матри- цы линейного кода представляет собой сумму по модулю 2 некоторого числа информационных столбцов порождающей матрицы. Приведём рекомендации по построению линейного группового кода заданной мощности с заданной обнаруживающей (корректирующей) способностью (без ограничения на общую длину ко- да). Такая задача достаточно часто возникает при разработке средств вычислительной техники по- вышенной надёжности. 1. Если — требуемая мощность линейного кода , то формат информационной части его по- рождающей матрицы равен ( ), где ] [. 109 2. Любой проверочный столбец порождающей матрицы формируется как сумма по модулю 2 некоторого числа её информационных столбцов. При этом любой информационный столбец должен присутствовать в качестве компоненты суммы хотя бы для организации одного про- верочного столбца. 3. Каждый вектор порождающей матрицы должен иметь вес в смысле Хэмминга 4. Кодовое расстояние в смысле Хэмминга между двумя любыми векторами и порождаю- щей матрицы должно быть ( ) , а между любыми двумя проверочными векто- рами и — ( ) 5. Для проверки правильности получения кода по построенной порождающей матрице следует выписать все векторы и определить полученного кода. Для декодирования линейных кодов, т.е. для обнаружения ошибок заданной кратности, воз- никающих в векторе линейного кода, необходимо построить аналитическое соотношение, устанав- ливающее связь между информационными и проверочными разрядами линейного кода. При отсут- ствии ошибок в векторе это соотношение, очевидно, должно обращаться в тождество. Имея такое соотношение, легко построить схему, сигнализирующую о появлении ошибок в векторах кода. Задача вывода такого соотношения может быть поставлена так: задана порождающая матрица линейного группового кода, представленная в левой канонической форме; для любого вектора линейного кода необходимо записать аналитическое выражение любого проверочного разряда этого вектора через известные информационные. Решение задачи можно произвести следующим образом. Как известно, любой вектор линей- ного кода образуется в результате суммирования некоторых векторов его порождающей матрицы. Для упрощения объяснения в порождающей матрице произвольного линейного кода информаци- онные разряды любого вектора обозначим буквами с соответствующими индексами, а провероч- ные разряды — буквами с одномерными индексами. Очевидно, любой проверочный разряд не- которого вектора линейного кода удовлетворяет соотношению k i ij j p p 1 , где ∑ — знак операции «сумма mod 2»; — значение соответствующих проверочных разрядов векторов порождающей матрицы из проверочного столбца, соответствующего символу , при условии, что пробегает толь- ко те значения из ̅̅̅̅̅, которые соответствуют складываемым векторам порождающей матрицы. Так как каждый проверочный столбец порождающей матрицы образуется как сумма некоторых инфор- мационных её столбцов, а каждый информационный столбец содержит только одну единицу, то справедливо соотношение k i i k i ij a p 1 1 , или k i i j a p 1 , ̅̅̅̅̅̅̅̅̅̅, где принимает только те значения, которые соответствуют единицам рассматриваемого проверочного столбца. Полученные уравнения определяют операцию декодирования линейных кодов и для каждой порождающей мат- рицы линейного кода имеют конкретный вид. Формальная процедура их построения по конкретной порождающей матрице заданного линейного кода следующая. Выбрать проверочный столбец порождающей матрицы. Записать уравнение для , заме- няя все значения этого проверочного столбца (в правой части уравнения) через информационные разряды . Замену осуществить следующим образом: каждую единицу проверочного столбца за- менить на информационный разряд , единица которого расположена на пересечении информаци- онного столбца и строки со значением , равным единице. Указанную процедуру проделать для каждого 110 В ходе вычислений находят вектор ( ), который в общем случае называется синдромом и его вид характеризует наличие или отсутствие ошибок в векторе кода. Если синдром нулевой, то ошибок нет, если синдром ненулевой, то ошибки есть. Исправление ошибок осуществляется по виду ненулевого вектора синдрома. Для линейных кодов, исправляющих -кратную ошибку, каждому вектору ошибки кратности соответствует свой век- тор синдрома. Для установления однозначного соответствия между номером ошибочного разряда и видом вектора синдрома достаточно построить матрицу ошибок, которая получается из проверочной части матрицы и приписанной снизу единичной матрицы соответствующего размера. Значение синдрома совпадает с одной из строк проверочной матрицы. Номер этой строки и является номером искажённого разряда. Исправление ошибок кратности большей, чем , связано со значительными расчётами, требующими построения матриц ошибок всех кратностей и сопоставления каждому вектору ошибки своего вектора синдрома. Циклические коды Циклические коды являются разновидностью линейных групповых кодов и относятся к систе- матическим кодам. Первоначально были созданы для упрощения процедуры декодирования. Одна- ко высокая эффективность к обнаружению ошибок таких кодов обеспечила их широкое применение на практике. Двоичный вектор циклического кода удобно рассматривать не как комбинацию нулей и единиц, а в виде полинома некоторой степени ( ) , где — основание системы счисления, а — коэффициенты, принадлежащие множеству { } в случае двоичной системы счисления. Представление двоичных векторов в виде полиномов позволяет свести действие над векто- рами к действиям над многочленами. При этом: сложение многочленов сводится к сумме по модулю 2 коэффициентов при равных степенях переменной ; умножение производится по обычному правилу умножения степенных функций, однако по- лученные коэффициенты при данной степени складываются по модулю 2; деление осуществляется по правилам деления степенных функций, при этом операция вычи- тания заменяется суммированием по модулю 2. Основным свойством циклических кодов является следующее: если вектор принадлежит цик- лическому коду, то любой вектор, полученный из рассматриваемого с помощью циклических сдви- гов, также принадлежит циклическому коду. Идея построения циклических кодов базируется на понятии неприводимого многочлена. Многочлен называется неприводимым, если он делится только на самого себя и на единицу, и не делится ни на какой другой многочлен. Иными словами, неприводимый многочлен нельзя предста- вить в виде произведения многочленов низших степеней. На неприводимый многочлен без остатка делится многочлен . Неприводимые многочлены играют в теории циклических кодов роль образующих полиномов. 111 Векторы циклического кода строятся в соответствии со следующими правилами. Пусть ( ) — любой двоичный вектор некоторого натурального кода; — одночлен степени ; ( ) неприво- димый полином степени . Тогда любой вектор ( ) циклического кода образуется с помощью соот- ношения: ( ) ( ) ( ), где ( ) — остаток от деления ( ) ( ) Таким образом, любой вектор циклического кода может быть образован умножением неко- торого вектора натурального двоичного кода на одночлен степени с добавлением к полученному произведению остатка от деления ( ) ( ) . При построении циклических кодов указанным способом расположение информационных разрядов в каждом векторе кода строго упорядочено — они зани- мают старших разрядов вектора кода, а остальные разрядов являются проверочными. Циклический код, как и всякий систематический код, удобно задавать в матричном виде с помощью порождающей матрицы , имеющей вид: ( ) ‖ ( ) ( ) ‖, где ( ) — транспонированная единичная матрица формата ( ); ( ) — матрица прове- рочных разрядов, образованная остатком от деления ( ) ( ) Любой вектор циклического кода получается как сумма по модулю 2 векторов его порожда- ющей матрицы. Так как циклический код является групповым, то нулевой вектор всегда приписыва- ется циклическому коду как единичный элемент группы. Необходимо отметить, что каждый циклический код, заданный некоторой порождающей матрицей, можно представить в нескольких вариантах, отличающихся друг от друга длиной и коли- чеством информационных разрядов (при одинаковых обнаруживающих способностях). Эти вариан- ты так называемых укороченных циклических кодов получаются вычёркиванием последних строк и такого же количества столбцов слева в порождающей матрице ( ) циклического кода. При этом число проверочных разрядов остаётся неизменным, а длина кода и число его информационных раз- рядов уменьшаются соответственно на величину, равную числу вычеркнутых строк и столбцов по- рождающей матрицы. Построение циклических кодов с заданными параметрами связано с выбором образующего неприводимого полинома. Образующий полином выбирается исходя из следующего условия: сте- пень полинома должна быть равна числу проверочных разрядов циклического кода. На практике часто возникает задача построения циклического кода заданной мощности и за- данной обнаруживающей и корректирующей способностей. Рекомендации для построения кода следующие: 1. Так как мощность циклического кода задана, то число его информационных разрядов определяется в соответствии с формулой 2. Оптимальное число проверочных разрядов циклического кода определяется по специальным таблицам. 112 3. По справочникам находятся все неприводимые полиномы степени . 4. Для одного из неприводимых многочленов (следует выбирать многочлен с максимальным числом членов) степени строится порождающая матрица циклического кода. Каждый век- тор ( ) кода вычисляется по формуле ( ) ( ) ( ( ) ( ) ) где ( ) — полином информационного вектора порождающей матрицы; — одночлен степени ; — остаток от деления ( ) ( ) 5. Построенная порождающая матрица проверяется на выполнение следующих условий: а) вес в смысле Хэмминга любого вектора порождающей матрицы должен удовлетворять соотношению , где — минимальное расстояние в смысле Хэмминга рас- сматриваемого циклического кода; б) вес в смысле Хэмминга проверочного вектора, являющегося суммой по модулю 2 любых двух проверочных векторов и порождающей матрицы, должен удовлетворять соот- ношению 6. Если порождающая матрица циклического кода удовлетворяет всем приведённым условиям, то выписываются все векторы циклического кода и определяется в соответствии с из- вестными правилами для линейных групповых кодов. Если код не соответствует требовани- ям, то выбирается другой порождающий полином той же степени , и процедура образова- ния циклического кода повторяется для нового полинома. Обнаружение ошибок с помощью циклических кодов производится следующим образом. Любой вектор циклического кода делится на образующий полином без остатка. Поэтому критерием наличия ошибки в векторе циклического кода является появление ненулевого остатка от деления вектора циклического кода на образующий полином. Ненулевой остаток является опознавателем ошибки в векторе циклического кода, однако его вид не указывает на место расположения ошибки в кодовом векторе. Исправление ошибок базируется на следующем алгоритме: 1. Принятый кодовый вектор разделить на образующий полином. 2. Подсчитать число единиц в полученном остатке. Если число единиц не превышает корректи- рующей способности кода, то принятый вектор сложить по модулю 2 с полученным остатком. Результат суммирования даст исправленный кодовый вектор. Если число единиц остатка больше корректирующей способности кода, то осуществить циклический сдвиг искажённого вектора влево на один разряд, а затем произвести деление на образующий полином. Если полученный остаток содержит единиц не больше корректирующей способности циклическо- го кода, то произвести суммирование сдвинутого циклически вектора с остатком. Результат суммирования сдвинуть циклически на один разряд вправо. Полученный вектор уже не со- держит ошибок и является вектором циклического кода. 3. Если после первого циклического сдвига и последующего деления остаток содержит единиц больше, чем корректирующая способность кода, то повторять процедуру п. 2 алгоритма до тех пор, пока не будет получен остаток с числом единиц, не превышающим корректирующей способности кода. В этом случае результат последнего циклического сдвига суммируется с остатком, и полученный вектор циклически сдвигается на столько разрядов вправо, на сколь- 113 ко был сдвинут влево исходный принятый вектор с ошибкой. В итоге получается исправлен- ный кодовый вектор. |