Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

аппаратурная реализация кода методами, которые рас­ смотрены в данном параграфе.

Структура миоготактных кодирующих и декодирую­

национные) сумматоры с запоминанием переноса. Пусть двоичное представление модуля А имеет вид:

A = a o + a i - 2 + . . . + ar-2r.

Тогда для кодирования, т. е. умножения числа N на модуль А, можно использовать схемы, показанные на рис. 5-2. Разряды множимого N поступают иа вход схемы

141

Будем предполагать, что число А делит число L , т. е.

L(x) =A(x)<N(x) =

где N(x) —частное. Так как арифметические коды по­ рождаются модулями А, ко­ торые являются нечетными числами, то ао=1 и из по­ следнего равенства полу­ чаем:

жение (5-17), показана на рис. 5-3. Оператору х* соот­ ветствует задержка на i так­ тов, при этом вес двоичных символов на входе и выходе

шаемого с дополнительным кодом вычитаемого. Получе­ ние дополнительного кода осуществляется с помощью схемы, обведенной пункти­ ром на рис. 5-3. Входная пе­ ременная у и выходная пе­ ременная z данной схемы связаны соотношением

z=y + 2z,

где с помощью коэффициен­

та 2 учитывается з а д е р ж к а

на один такт в цепи обратной связи. Из последнего ра­ венства следует, что

z=—y.

Рассматриваемая схема деления имеет два устойчи­ вых эквивалентных состояния: 1) содержимое всех за­

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

Делимое L=(ln-t, • •., к, к) поступает на вход устрой­ ства деления последовательно, начиная с младших раз­ рядов. Устройство вычисляет разряды частного также последовательно, начиная с младших разрядов. Если де­ лимое L делится без остатка на число А, то после п так­ тов работы устройство будет находиться в одном из ну­ левых состояний.

Например, модуль Л = 19 порождает арифметический код длиной /1=9 двоичных разрядов (см. табл. 5-3). Число А в двоичной системе счисления имеет вид:

Непосредственным вычислением последовательных состояний устрой­

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

Прежде чем рассматривать более общий случай пред­ положим, что ошибка Е=1, т. е. ошибка возникла в млад-

143

Рис. 5-4. Схема деления на порождающий модуль Л = 19.

шем разряде. Пусть е — порядок класса вычетов 2 по нечетному модулю А, тогда имеет место равенство

где С — целое нечетное число; отсюда 1/Л = С/(2е —1).

Правую часть данного равенства можно рассматри­ вать как сумму бесконечной убывающей геометрической прогрессии, первый член которой равен С/2е, а знамена­ тель прогрессии 1/2е, т. е.

Из правой части 'последнего равенства следует из­ вестный из теории чисел результат, что двоичное пред­ ставление частного 1/Л, где Л — нечетное число, имеет вид бесконечной периодической последовательности с пе­ риодом, равным порядку класса вычетов 2 по модулю А.

Первые е двоичные разряды после запятой двоично­ го представления частного 1/Л называются основным пе­ риодом. Этот период равен:

ность из г нулей, так как предположение о наличии г нулей подряд в двоичном представлении числа С = = (ce _r _i, .. . , сь с0 ) противоречит условию, что е равно порядку 2.

144

Если е — нечешие число, то рассмотренным исчерпы­ ваются характеристики структуры каждого периода дво­ ичного .представления числа 1/Л.

основной период

Непосредственным делением можно проверить полученный ре­ зультат.

Если же модуль А — простое нечетное число, а е — четное число, то основной период имеет дополнительные свойства, которые заключаются в следующем. Запишем выражение (5-18) в виде

С=(2 е — 1)/Л

ном случае основной период состоит из двух частей дли­ ной е/2 разрядов каждая. Первая часть, которой соот­ ветствует число F, занимает е/2 старших разрядов пе­ риода (потому что перед числом F стоит коэффициент 2е / 2 ). Вторая часть, которой соответствует число F, зани­ мает е/2 младших разрядов периода; причем двоичное представление числа F равно обратному коду двоичного