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

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

В некоторых работах говорится о специфике борьбы с ошибками в управляющей и числовой информации к делается вывод о том, что кодовую избыточность целе­ сообразно использовать только для защиты числовой ин­ формации [Л. 28]. С нашей точки зрения не следует про­ тивопоставлять числовую и управляющую информацию, так как ЦВМ различает тип информации не по ее каким-

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

Г л а в а в т о р а я

НЕКОТОРЫЕ КЛАССЫ КОРРЕКТИРУЮЩИХ КОДОВ И ИХ РЕАЛИЗАЦИЯ

2-1. АЛГЕБРАИЧЕСКИЕ МЕТОДЫ ОПИСАНИЯ КОДОВ

Множество л-разрядных двоичных слов, для которых

где Xi+yi — сумма по модулю 2, образует абелеву (ком­ мутативную) группу (см. приложение 1). Если кроме операции суммирования ввести операцию умножения на скаляр а из поля 5- (в нашем случае поле & состоит из двух элементов: 0 и 1)

аХ = (ахи а х 2 , . . . , ахп),

то получим векторное (линейное) пространство Vn, эле­ менты которого называются векторами.

28

В теории линейных пространств важную роль играет понятие линейной зависимости. Совокупность векторов

когда все aj = 0, то совокупность векторов называется ли­ нейно независимой.

Обратимся теперь к описанию векторных простраистн с помощью матриц. Базисные векторы могут рассматри­ ваться как строки ма грицы

Уг

0 =

29

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

Например, в качестве порождающей матрицы векторного пространства V„, образованного выше введением операций сложения по модулю 2 и умножения на скаляр над множеством я-разрядиых двоичных слов, может быть выбрана единичная матрица порядка п

слов, являющееся подпространством пространства Vn размерности п.

Для получения корректирующего кода длиной а раз­ рядов с заданным минимальным расстоянием d необхо­ димо выбрать некоторое подмножество Vk из Vn та.кпм образом, чтобы V), являлось векторным подпространст­ вом пространства У,,, а расстояние между любыми дву­ мя векторами из Vk должно быть не меньше требуемого значения d. Индекс k в обозначении векторного подпро­

равенства следует вывод: минимальное расстояние d линейного группового .кода равно минимальному весу его •ненулевых элементов.

Выбрав в Vk k базисных векторов, получим порож­ дающую матрицу G линейного кода. Перестановка столб­ цов и элементарные преобразования над строками ма­ трицы G (в алгебре под элементарными преобразования­ ми понимаются: перестановка любых двух строк матри­ цы, прибавление к одной строке другой, умноженной но

зО

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

прямоугольная матрица размером (1Х/г). Произведение1 этой матрицы на матрицу G' равно:

равенства следует, что первые k .компонент выбираются

торых связаны условием: число столбцов первой матрицы равно числу

У=1

31