Основное свойство циклических кодов, определившее их название, состоит в следующем: любое кодовое слово А = аn аn-1 ... а1 а0 будучи циклически сдвинутым на один разряд создаёт новое слово А1= аn-1 ... а1 а0 аn, принадлежащее этому же циклическому коду.
Применение циклических кодов позволяет при небольшой избыточности и простой аппаратурной реализации получить высокую вероятность обнаружения ошибок.
Особенно удобны циклические коды в тех случаях, когда кодовые слова выдаются или принимаются последовательно, разряд за разрядом, начиная со старшего разряда, который в изображении слова располагается слева.
Каждому двоично-кодированному n-разрядному слову ставится в соответствие полином (n-1)-степени (говорят также, что слово представляется полиномом) переменной х, причём коэффициентами полинома являются значения соответствующих разрядов слова.
Например, слово А = 110101 представляется полиномом пятой степени
Циклический сдвиг слова А даёт новое слово А1 = = 101011, которое представляется полиномом
РА1(х) = х5 + х3 + х + 1.
Между кодовыми словами и представляющими их полиномами существует однозначное соответствие. Поэтому построение и исследование любого циклического кода можно свести к операциям над полиномами.
Принцип обнаружения ошибок с применением циклического кода состоит в том, что в качестве разрешенных слов используются только такие слова, полиномы которых F(x) делятся без остатка на некоторый заранее выбранный полином Р(х). Часто говорят, что полином Р(х) образует или порождает циклический код. Если после искажения отдельных разрядов слова представляющий это слово полином F'(x) не будет делиться без остатка на Р(х), то фиксируется факт наличия ошибки.
Кодирование информационной части слова, представленной полиномом G(x), происходит в соответствии с соотношением
F'(x) = G(x)×хk + R(x) ,
где R(x) - остаток от деления G(x)×хkна порождающий полином Р(х) степени k.
Существо кодирования состоит в следующем. Информационная часть слова за счёт умножения G(x) на хk сдвигается на k разрядов влево. В освободившиеся k младших (контрольных) разрядов записывается остаток R(x) от деления G(x)×хkна Р(х), который и представляет контрольную часть слова.
Максимально возможная длина выходной последовательности, которую можно получить с помощью порождающего полинома, определяется степенью порождающего полинома:
L = 2k-1 .
Так, для порождающего полинома Р(х) = х8+х6+х5+х3+1 максимально возможная длина выходной последовательности равна 255 [16].
Таким образом, после выбора порождающего полинома процесс формирования полного выходного кодового слова состоит в сдвиге влево на k разрядов информационной части слова, определении остатка R(x) и записи его в освободившиеся младшие разряды. Получение контрольной части выходного слова, соответствующей полиному R(x), практически осуществляется путём последовательного сложения по модулю 2 сдвинутой информационной части слова и другого слова, соответствующего порождающему полиному Р(х). Процесс нахождения контрольной части слова А = 1010001 при помощи порождающего полинома третьей степени Р(х) = х3 + х + 1 показан в табл.16.5.
Здесь 1011 - слово, соответствующее порождающему полиному, обведено пунктиром. Жирными цифрами выделена сформированная контрольная часть. Признак окончания операции кодирования - отсутствие единиц в информационной части слова. В табл.16.6 представлены исходный полином G(x) и полученные полиномы G(x)×хk, R(x) и F(x).
Таблица 16.6
G(x)
G(x)×хk
1010001 000
R(x)
0000000 110
F(x)
1010001 110
Все свойства циклического кода, в частности его избыточность и корректирующая способность, полностью определяются степенью и видом порождающего полинома Р(х). Можно подобрать такие порождающие полиномы Р(х) , которые позволяют обнаруживать ошибки второй, третьей и большей кратности. Существуют также полиномы Р(х), с помощью которых строятся коды, обнаруживающие не только факт, но и место (разряд) возникновения ошибки [16]. Это становится возможным потому, что для некоторых Р(х) можно установить однозначное соответствие между ошибками отдельных разрядов и величиной остатка, полученного от деления искажённого слова F(x) на Р(х).
Кодеры-декодеры циклических кодов строятся на основе регистров сдвига (триггеров) и схем сложения по модулю 2. На рис.16.12 приведены функциональные схемы кодеров-декодеров для кодов, порождаемых полиномами Р(х) = х3 + х + 1 (рис.16.12,а) и Р(х) = х8+х6+х5+х3+1 (рис.16.12,б).
Рис.16.12. Функциональные схемы кодеров-декодеров для полиномов
Р(х) = х3 + х + 1 (а) и Р(х)=х8+х6+х5+х3+1 (б)
Принцип построения кодеров-декодеров циклических кодов достаточно прост. Для этого необходимо представить порождающий полином в виде двоичного слова и отбросить старшую единицу. Например, для полинома Р(х) = х8+х6+х5+х3+1 двоичное слово будет выглядеть следующим образом А = 101101001. Отбросив старшую единицу, получим А' = 01101001. Затем полученное двоичное слово надо записать, начиная с младших разрядов (А'' =10010110). Заменив каждый нуль на триггер, а каждую единицу - на триггер с двухвходовым сумматором по модулю 2 на входе и соединив их последовательно, получим схему кодера-декодера циклических кодов, порождаемых заданным полиномом (рис.16.12,б).
Работает схема кодера-декодера следующим образом.
При кодировании на вход кодера подаются один за другим m информационных разрядов кодируемого слова, начиная со старших разрядов. Через m тактов в триггерах кодера будет сформирована k-разрядная контрольная характеристика. Переключив выходной ключ и подав на вход кодера последовательность из k нулей, выдадим в линию контрольную характеристику. Время кодирования составляет m+k тактов.
При декодировании (m+k)-разрядное слово поступает на вход декодера. По прошествии m+k тактов в триггерах декодера будет сформирован синдром ошибки. Если синдром равен нулю, кодовое слово не содержит ошибок. Если синдром не равен нулю, в закодированном слове имеется ошибка.
Наиболее эффективными из циклических кодов считаются коды Боуза-Чоудхури-Хоквингема (БЧХ-коды) [14, 16].
§ 2.7. Схемы контроля Сложность ЭВМ и других ЦУ определяет важность операций контроля и диагностики их функционирования. В некоторых случаях контроль жизненно важен (авиационные приборы, управление мощными энергетическими установками, мониторинг пациентов ·в клиниках и др.). Причинами нарушения нормальной работы ЦУ могут быть отказы (т. е. нарушения из-за возникших неисправностей, имеющих постоянный характер) и сбои (т. е. нарушения из-за проявлений неблагаприятных факторов, в частности, помех, которые в дальнейшем могут и не проявиться). Независимо от этого дальше будем говорить об ошибках функционирования, поскольку для рассматриваемых далее вопросов- конкретный характер ошибок несущественен.
Цели и задачи контроля, диагностики и исправления ошибок в UY могут быть разными. Можно ставить задачу предотвращения ошибок в работе ЦУ. Для этого необходимы такие меры, как применение высококачественных элементов схем, стабилизация условий окружающей среды и т. п. Но даже при всех стараниях вряд ли возможно полностью избавиться от ошибок. Имея в виду неизбежность возникновения ошибок, следует позаботиться об их выявлении. Задачи выявления ошибок решаются разными методами. Можно, например, воспользоваться дублированием UY и сравнением результатов работы двух идентичных устройств. Несовпадение ·результатов в этом случае рассматривается как признак ошибки (хотя вероятность того, что ошибка появилась в контролируемом устройстве, а не в контролирующем равна всего 50%). Для выявления ошибок используются специальные коды, более сложные, чем двоичные. И, наконец, можно ставить задачи маскирования (исправления) ошибок. В этом случае наличие ошибок определенного типа и количества не нарушает работу устройства, поскольку их влияние устраняется автоматически. В этой области используется, например, троекратное резервирование устройств с выработкой результата путем "голосования" с помощью мажоритарных элементов. Эти элементы вырабатывают выходные данные "по большинству" входных. Если из трех устройств одно стало работать неправильно, это не скажется на результате. Только ошибка в двух из трех каналов проявляется в результате. Отметим, что добавление к функциям устройств функций контроля всегда связано с избыточностью - платой за новые возможности будут дополнительные аппаратные или временные затраты. Вводимая избыточность - это цена контроля. В частности, метод дублирования ценен своей универсальностью, но дорог, для него избыточность составляет около 100%. В этом параграфе рассмотрены очень ограниченные вопросы контроля ЦУ, которому посвящаются специальные труды. Здесь затронуты темы, связанные с пониманием работы ИС, выпускаемых для использования в системах контроля. К таким схемам относятся мажоритарные элементы, схемы контроля по модулю 2 и схемы кодирования-декодирования для кодов Хемминга.
Мажоритарные элементы Задача мажоритарного элемента - произвести "голосование" и передать на выход величину, соответствующую большинству из входных. Ясно, что мажоритарный элемент может иметь только нечетное число входов. Практически
выпускаемые элементы имеют по три входа или по пять входов. Функционирование мажоритарного элемента, на входы которого поступают величины F1, F2, и Fз и по результатам голосования вырабатывается выходная величина F, представлено я табл. 2.8. Если имеется в виду контроль многоразрядных слов, то в каждом разряде ставится элемент рассматриваемого типа. Кроме выхода F, в таблице даны и выходы а 1 , а0 - старший и младший разряды двухразрядного кода, указывающего номер отказавшего канала (рис. 2.20). Из таблицы легко получить функции, которые после несложных преобразований приводятся к следующим:
В схемах типа рис. 2.20 от мажоритарного элемента требуется особенно высокая надежность, т. к. его отказ делает бесполезной всю схему резервирования.
Контроль по модулю 2 Контроль правильиости передач и хранения данных - важное условие нормальной работы ЦУ. В этой области простейшим и широко применяемым методом является контроль по модулю 2. Приступая к ознакомлению
c этим методом, следует остановиться на некоторых понятиях из теории построе~ия помехоустойчивых кодов. Кодовая комбинация- набор из с.имволов nринятого алфавита. Код- совокупность кодовых комбинаций, используемых для отображения информации. Кодовое расстояние между двумя кодовыми комбинациями - число разрядов, в которых эти комбинации отличаются друг от друга. Минимальное кодовое paccffiOянue - минимальное кодовое расстояние для любой·пары комбинаций, входящих в данный код. Кратностью ошибки называют' число ошибок в данном слове (число неверных разрядов). Из теории кодирования известны условия обн!lружения и· исправления ошибок при использовании кодов:
dmin = fобн + 1; dmin = 2rиcnp + 1; dmin = 2t·иcnp + fобн + 1, где dmin - минимальное кодовое расстояние кода; r06н и fиcnp- кратность обнаруживаемых и исправляемых ошибок соответственно. Существует также понятие вес комбинации, обозначающее число единиц в данной комбинации. Для двоичного кода минимальное кодовое расстояние dn1in = 1, поэтому он не обладает возможностями какого-либо контроля производимых над ним действий. Чтобы получить возможность обнаруживать хотя бы ошибки единичной кратности, нужно увеличить минимальное кодовое расстояние на 1. Это и сделано для кода контроля по модулю 2 (контроля по четности/ нечетности). При этом способе контроля каждое слово дополняется контрольным. разрядом, значение которого подбирается так, чтобы сделать четным (нечетным.) вес каждой кодовой комбииации. При одиночной ошибке в кодовой комбинации четность (нечетность) ее веса меняется, а такая комбинация не принадлежит к данному коду, что и обнаруживается схемами контроля. При двойной ошибке четность (нечетность) комбинации не нарушается - такая ошибка не обнаруживается. Легко видеть, что у кода с контрольным разрядом dmin = 2. Хотя обнаруживаются ошибки не только единичной, но вообще нечетной кратности, на величину dmin это не влияет. При контроле по четности вес кодовых комбинаций делают четным, при контроле по нечетности - нечетным. Логические возможности обоих вариантов абсолютно идентичны. В зависимости от технической реализации каналов передачи данных, может проявиться предпочтительность того или иного варианта, поскольку один из вариантов может позволить отличать обрыв всех линий связи от передачи нулевого слова, а другой - нет.
Значения:контрольного разряда р при контроле ПО· ;•четности (Рч) и нечетности ·(Рн) приведены для четырехразрядного информационного слова в табл. 2.9. Как видно из таблицы, Рч = aзe>a2ffia1ffiao; Рн = а3ЕБа2ЕБа 1 ЕБао. После передачи слова или считывания его из памяти вновь производится сложение разрядов кодовой комбинации по модулю 2 (свертка по ·модулю 2) и проверяется, сохранилась ли четность (нечетность) веса принятой комбинации. Если четность (нечетность) веса комбинации изменилась, фиксируется ошибка операции. 107 Из приведеиного материала следует, что контроль по модулю 2 эффективен там, где вероятность единичной ошибки много больше, чем вероятность двойной (или вообще групповой). В частности, для полупроводниковой основной памяти компьютеров такая ситуация справедЛива, т. к. каждый бит слова хранится в своей собственной ячейке, и наиболее вероятны единичные ошибки. А мя памяти на магнитных носителях информации (диски, ленты) дефекты таковы, что обычно затрагивают площадь, на которой размещено несколько бит данных, поэтому для этой nамяти контроль по модулю 2 неэффективен.
Схемы свертки Контроль по модулю 2 реализуется с помощью схем свертки. Типична многоярусная схема свертки пирамидального типа. На рис. 2.21, а по казана схема свертки байта. Для оценки аппаратной сложности и быстродействия подобных схем при разрядности свертываемого слова 2" (n - Произвольное целое число) легко получить соотношения: Nлэ = п/2 + n/4 + ... + n/n = n(l/2 + 1/4 + ... + 1/п) = п- 1; L = log2n, где Nлэ - число логических элементов в схеме; L - ее логическая глубина. Схематехника сейчас сориентирована главным образом на работу с параллельными данными, однако не исЮiючены ситуации обработки последовательных данных, когда слова передаются по одной линии последовательно разряд за разрядом. Для таких случаев целесообразно применять схему свертки (рис. 2.21, б), которая вьшает результат всего лишь через одну задержку после поступления последнего разряда а 7 .
Примерам ИС свертки по модулю 2 может служить микросхема ИП5 серии КР1533 (рис. 2.22, а). Схема имеет 9 входов, что допускает свертку байта с девятым контрольным разрядом. Двумя выходами схемы являются Е (Even) и О (Odd). Если вес входной комбинации четный, то Е = 1 и О = О, и на- оборот, если вес нечетный. Схематехнически ИС КР153ЗИП5 предстамнет собою пирамидальную структуру из трехвходовьrх элементов типа четность/нечетность (рис. 2.22, б).
Передача данных с контролем по модулю 2 Передача данных или их запись/считывание (если речь идет о памяти) с контролем показаны на рис. 2.22, в. Входные данные обозначены через D, на выходе из канала связи или памяти данные обозначены через D', поскольку вследствие ошибок они могут измениться. Контроль по модулю 2 применим не только для операций передачи и хранения слов, но и для некоторых более сложных операций. В этих случаях недостаточно просто добавить к информационному слову контрольный разряд, а требуются более развитые операции. Контроль логического преобразователя На рис. 2.23 показан пример контроля логического преобразователя ЛП, воспроизводящего систему переключательных функций от n1 переменных. Для осуществления контроля к системе добавляется еше одна функция Fдon = F 1®F2® ... ®Fn, которая воспроизводится на инд~видуальных элементах (во избежание маскирования контролируемых ошибок). Затем выработанные функции F1-Fn свертываются по модулю 2, и результат сравнивается с дополнительной функцией Fдon· Ясно, что при отсутствии ошибок должны сравниваться одинаковые величины. Если они различны, то на выходе элемента сложения по модулю 2 возникнет сигнал ошибки.
Ряд операций контролируется в условиях, когда контрольный разряд не постоянен, а изменяется по определенному закону. Это возможно, если установлена закономерность изменения контрольного разряда при выполнении операции. Например, при работе счетчика его содержимое меняется по известному закону. Если к слову, содержащемуся в счетчике, добавлять контрольный разряд, также изменяющийся по известному закону, то свертка содержимого счетчика вместе с контрольным разрядом покажет единичную ошибку в работе счетчика. Такой же подход возможен для контроля сумматоров.
Контроль с использованием кодов Хемминга } : i !<' ' Применеине кодов Хемминга позволяет исправлять единичные ошибки. Добавление к коду Хемминга контрольного разряда, обеспечивающего четность/ нечетность всей кодовой комбинации в целом, приводит к модифийированному коду Хемминга, с помощью которого можно исправлять единичные ошибки и обнаруживать двойные. Метод~I контро~я с помощью кодов Хемминга основаны на тех же идеях, что и контроль по модулю 2. Отсюда и область эффективного применения кодов Хемминга - устройства, в которых вероятность единичных ошибок м·ного больше, чем вероятность групповых. Для получения кодовой комбинации кода Хемминга к информационному слову добавляется несколько контрольных разрядов. Для простоты просмотра кодовых комбинаций с целью определения значений контрольных разрядов примем, что ~онтрольные разряды занимают позиции с номерами 2i (i = О, 1, 2, ... ). Каждый контрольный разряд ассоциируется с некоторой группой разрядов кодовой комбинации и выводит вес группы, в которую он входит, на четность/ нечетность. Первый контрольный разряд входит в группу разрядов с номерам.". хх ... хх1, где х означает Произвольное значение. Иными словами, в первую группу входят разрядыснечетными номерами: 1, 3, 5, 7, 9, ... Второй контрольный разряд входит в группу разрядов с номерами, имеющими единицу во втором справа разряде, т. е. номерами хх ... х1х. Это номера 2, 3, 6, 7, 10, 11, ... - Третий контрольный разряд входит в группу, у которой номера разрядов имеют единицу в третьем справа разряде: хх ... 1хх, т. е. с номерами 4, 5, 6, 7, 12, 13, 14, 15, ... Контрольные разряды выводят веса своих групп на четность/нечетность. Далее для определенности примем, что ведется контроль по четности. После
выполнения операции (например·~ с~итываJ-JИЯ кодовой ~омбинации из памяти) производится столько проверок. по модулю 2, сколько контрольных разрядов в кодовой комбинации, т. е. проверяется сохранение четности весов групп. Если в кодовой комбинацИи произошла ошибка, то в одних проверках она скажется, а в других - нет. Это и позвоJ!яет определить разряд, в котором произошла ошибка. Для восстановленИя правильного значения слова теперь остается только проинвертировать ошибочный разряд. Такова идея построения и использования кода Хемминга . . ; Пример составления кода Хемминга для четырехразрядного информационного слова А= а3а2а 1 ао приведен в табл. 2.10.· Через р в таблице обозначе~ общий контрольный разряд для всей кодовой комби~-:~ации, через р 1 , р2 , р1 - первый, второй и третий групповые контрольные разряды.
Для коротких слов избыточность кода Хемминга получилась значительной (здесь на четыре информационных разряда приходится четыре контрольных), но это нетипично, поскольку реально контролируются слова большей разрядности, ЩIЯ которых избыточность (относительная) быстро уменьшается с ростом разрядности слов. Короткое слово взято, чтобы пример не был громоздким. Рассмотрим теперь процесс исправления и выявления ошибок. Пусть, например, передавалось информационное слово 0110 = 610• Не учитывая прка . ' 1 разряд р, получим, что правильная кодовая комбинация имеет вид:
Первая проверка (по группе разрядов с нечетными -номерами) показывает сохранение четности, т. е. в этой группе ошибок нет, результат этой проверки отмечается нулем. Вторая проверка (по разрядам 2, 3, 6, 7) обнаруживает нарушение четности веса комбинации, ее результат отмечается единиц~й. Третья проверка (по разрядам 4, 5, 6, 7) также обнаруживает нарушение четности, ее результат отмечается единицей. Результаты проверок образуют слово, называеА1Ое синдромом. Синдром указывает номер разряда, в котором произошла outuбкa. Во взятом примере результаты проверок дают слово 110 = 610. Проинвертировав разряд номер 6, возвращаемся к правильной кодовой комбинации - ошибка исправлена. Минимальное кодовое расстояние обычного кода Хемминга равно трем. Добавление разряда проверки общей четности веса комбинации приводит к модифицированному коду Хемминга с минимальным кодовым расстоянием, равным 4 и, соответственно, добавляет возможность обнаружения двойной ошибки. Обнаружение двойной ошибки основано на сопоставлении наличия или отсутствия признаков ошибки в синдроме и общей четности. Если обозначить через S любое иенулевое значение синдрома, то возможные ситуации, используемые для обнаружения двойной ошибки, окажутся следующими (табл. 2.11).
Схемы кодера и декодера для кода Хемминга На рис. 2.24 показана схема кодирования и декодирования для кодов Хемминга. Верхняя часть схемы показывает выработку контрольных разрядов
для составления кода Хемминга. Нижняя часть содержит три четырехразрядных схемы свертки для проведения групповых проверок (разрядов синдрома). Синдром поступает на дешифратор, который вырабатывает единичный сигнал на линии, соответствующей номеру ошибочного разряда. Эта единица выполняет инвертирование ошибочного разряда слова А, поступая на второй вход элемента сложения по модулю 2, ~ерез который данный разряд передается на выход схемы. Таким образом, нИжняя часть схемы представляет собой декодирующее устройство для кода Хемминга.
Двойная ошибка обнаруживается элементом 2k согласно логике ситуаций, указанной ранее.
Кодирование-декодирование для 16-разря:ztных слов с формированием шести контрольных разрядов модифицированного кода Хемминга реализуется микросхемой ВЖI серий К555, 533. Время кодирования-декодирования составляет для этой ИС 50-60 не. Код Хемминга относится к числу простых. Есть много более сложных кодов с большими корректирующими возможностями (БЧХ, код Файра, код РидаСоломона и др.).
= 101011, которое представляется полиномом
