Схема свертки для параллельной формы представления числа
Схема свертки по модулю 3 для последовательной формы передачи чисел
Схема может быть выполнена в виде двухразрядного счетчика с циклом 3, построенного таким образом, что единицы нечетных разрядов поступающего на вход числа вызывают увеличение содержимого счетчика на единицу, а единицы четных разрядов вызывают увеличение числа в счетчике на два. Функционирование такого счетчика описывается табл. 4.
Здесь b— код, определяющий четность номера очередного разряда числа, поступающего на вход счетчика; примем для четных разрядов b = 0, для нечетных разрядов b = 1.
Таблица 4
Таблица 5
По этой таблице и таблице переходов JK-триггера (табл. 5) построены приведенные на рис. 6 карты, по которым находят логические выражения для входов триггеров ТТ1 и ТТ2 счетчика:
Рис.6. Карты, по которым находят логические выражения для входов триггеров ТТ1 и ТТ2 счетчика.
Представив выражения для J и J в базисе И-НЕ:
получим схему межтриггерных связей на рис.7. Логическая переменная b формируется триггером 3.
Этот триггер переключается тактовыми импульсами (ТИ), следующими с частотой поступления разрядов числа на вход счетчика. Таким образом, в моменты поступления нечетных разрядов триггер 3 устанавливается в состояние 1 и b = 1, в моменты поступления четных разрядов b= 0.
Рис.7. Схема межтриггерных связей.
При параллельной форме представления числа обычно используется пирамидальный способ построения схемы свертки, показанный на рис. 8.
Элементы А первого яруса формируют остатки для пар разрядов числа, выдавая уровень лог. 1 на один из выходов А ,А ,А в зависимости от значения остатка (0,1,2). В последующих ярусах используются однотипные элементы В, которые формируют остатки по результатам, выдаваемым парой элементов предыдущего яруса. На выходе элемента последнего яруса образуется остаток для всего числа.
Выходы элементов определяются следующими логическими выражениями: для первого яруса
для остальных ярусов
Если число разрядов n = 2 , то число ярусов в схеме свертки равно k, а число элементов составляет (n – 1).
Одной из основных характеристик корректирующего кода является избыточность кода, указывающая степень удлинения кодовой комбинации для достижения определенной корректирующей способности.
Если на каждые m символов выходной последовательности кодера канала приходится k информационных и (m-k) проверочных, то относительная избыточность кода может быть выражена одним из соотношений: Rm = (m-k)/m или Rk = (m-k)/k.
Величина Rk, изменяющаяся от 0 до ¥, предпочтительнее, так как лучше отвечает смыслу понятия избыточности. Коды, обеспечивающие заданную корректирующую способность при минимально возможной избыточности, называют оптимальными.
В связи с нахождением оптимальных кодов оценим, например, возможное наибольшее число Q разрешенных комбинаций m-значного двоичного кода, обладающего способностью исправлять взаимно независимые ошибки кратности до s включительно. Это равносильно отысканию числа комбинаций, кодовое расстояние между которыми не менее d=2s+1.
Общее число различных исправляемых ошибок для каждой разрешающей комбинации составляет
,
где Cmi – число ошибок кратности i.
Каждая из таких ошибок должна приводить к запрещенной комбинации, относящейся к подмножеству данной разрешенной комбинации. Совместно с этой комбинацией подмножество включает комбинаций.
1+
Однозначное декодирование возможно только в том случае, когда названные подмножества не пересекаются. Так как общее число различных комбинаций m-значного двоичного кода составляет 2m, число разрешенных комбинаций не может превышать
Или .
Эта верхняя оценка найдена Хэммингом. Для некоторых конкретных значений кодового расстояния d, соответствующие Q укажем в таблице:
Таблица 4.3.
d
Q
d
Q
…
...
…
...
...
Коды, для которых в приведенном соотношении достигается равенство, называют также плотноупакованными.
Однако не всегда целесообразно стремиться к использованию кодов, близких к оптимальным. Необходимо учитывать другой, не менее важный показатель качества корректирующего кода – сложность технической реализации процессов кодирования и декодирования.
Если информация должна передаваться по медленно действующей и дорогостоящей линии связи, а кодирующее и декодирующее устройства предполагается выполнить на высоконадежных и быстродействующих элементах, то сложность этих устройств не играет существенной роли. Решающим фактором в этом случае является повышение эффективности пользования линией связи, поэтому желательно применение корректирующих кодов с минимальной избыточностью.
Если же корректирующий код должен быть применен в системе, выполненной на элементах, надежность и быстродействие которых равны или близки надежности и быстродействию элементов кодирующей и декодирующей аппаратуры. Это возможно, например, для повышения достоверности воспроизведения информации с запоминающего устройства ЭВМ. Тогда критерием качества корректирующего кода является надежность системы в целом, то есть с учетом возможных искажений и отказов в устройствах кодирования и декодирования. В этом случае часто более целесообразны коды с большей избыточностью, но простые в технической реализации.
4.5 Линейные коды
Самый большой класс разделимых кодов составляют линейные коды, у которых значения проверочных символов определяются в результате проведения линейных операций над определенными информационными символами. Для случая двоичных кодов каждый проверочный символ выбирают таким образом, чтобы его сумма с определенными информационными символами была равна 0. Символ проверочной позиции имеет значение 1, если число единиц информационных разрядов, входящих в данное проверочное равенство, нечетно, и 0, если оно четно. Число проверочных равенств (а следовательно, и число проверочных символов) и номера конкретных информационных разрядов, входящих в каждое из равенств, определяется тем, какие и сколько ошибок должен исправлять или обнаруживать данный код. Проверочные символы могут располагаться на любом месте кодовой комбинации. При декодировании определяется справедливость проверочных равенств. В случае двоичных кодов такое определение сводится к проверкам на четность числа единиц среди символов, входящих в каждое из равенств (включая проверочные). Совокупность проверок дает информацию о том, имеется ли ошибка, а в случае необходимости и о том, на каких позициях символы искажены.
Любой двоичный линейный код является групповым, так как совокупность входящих в него кодовых комбинаций образует группу. Уточнение понятий линейного и группового кода требует ознакомления с основами линейной алгебры.
4.6 Математическое введение к линейным кодам
Основой математического описания линейных кодов является линейная алгебра (теория векторных пространств, теория матриц, теория групп). Кодовые комбинации рассматривают как элементы множества, например, кодовые комбинации двоичного кода принадлежат множеству положительных двоичных чисел.
Множества, для которых определены некоторые алгебраические операции, называют алгебраическими системами. Под алгебраической операцией понимают однозначные сопоставление двум элементам некоторого третьего элемента по определенным правилам. Обычно основную операцию называют сложением (обозначают a+b=c) или умножением (обозначают a*b=c), а обратную ей – вычитаниемили делением, даже, если эти операции проводятся не над числами и не идентичны соответствующим арифметическим операциям.
Рассмотрим кратко основные алгебраические системы, которые широко используют в теории корректирующих кодов.
Группой множество элементов, в котором определена одна основная операция и выполняются следующие аксиомы:
1. В результате применения операции к любым двум элементам группы образуется элемент этой же группы (требование замкнутости).
2. Для любых трех элементов группы a,b,c удовлетворяется равенство (a+b)+c=a+(b+c), если основная операция – сложение, и равенство a(bc)=(ab)c, если основная операция – умножение.
3. В любой группе Gn существует однозначно определенный элемент, удовлетворяющий при всех значениях a из Gn условию а+0=0+а, если основная операция – сложение, или условию а*1=1*а=а, если основная операция – умножение. В первом случае этот элемент называют нулем и обозначают символом 0, а во втором – единицей и обозначают символом 1.
4. Всякий элемент а группы обладает элементом, однозначно определенным уравнением а+(-а)=-а+а=0, если основная операция – сложение, или уравнением а*а-1= а-1*а=1, если основная операция – умножение.
В первом случае этот элемент называют противоположным и обозначают (-а), а во втором – обратным и обозначают а-1.
Если операция, определенная в группе, коммутативна, то есть справедливо равенство a+b=b+a (для группы по сложению) или равенство a*b=b*a (для группы по умножению), то группу называют коммутативной или абелевой.
Группу, состоящую из конечного числа элементов, называют порядком группы.
Чтобы рассматриваемое нами множество n-разрядных кодовых комбинаций было конечной группой, при выполнении основной операции число разрядов в результирующей кодовой комбинации не должно увеличиваться. Этому условию удовлетворяет операция символического поразрядного сложения по заданному модулю q (q – простое число), при которой цифры одинаковых разрядов элементов группы складываются обычным порядком, а результатом сложения считается остаток от деления полученного числа по модулю q.
При рассмотрении двоичных кодов используется операция сложения по модулю 2. Результатом сложения цифр данного разряда является0, если сумма единиц в нем четная, и 1, если сумма единиц в нем нечетная, например,
Å
Выбранная нами операция коммутативна, поэтому рассматриваемые группы будут абелевыми.
Нулевым элементом является комбинация, состоящая из одних нулей. Противоположным элементом при сложении по модулю 2 будет сам заданный элемент. Следовательно, операция вычитания по модулю 2 тождественна операции сложения.
Подмножества группы, являющиеся сами по себе группами относительно операции, определенной в группе, называют подгруппами. Например, подмножество трехразрядных кодовых комбинаций: 000, 001, 010, 011 образуют подгруппу указанной в примере группы трехразрядных кодовых комбинаций.
Пусть в абелевой группе Gn задана определенная подгруппа А. Если В – любой, не входящий в А элемент из Gn, то суммы (по модулю 2) элементов В с каждым из элементов подгруппы А образуют определенный класс группы Gn по подгруппе А, порождаемый элементом В.
Элемент В, естественно, содержится в этом смежном классе, так как любая подгруппа содержит нулевой элемент. Взяв последовательно некоторые элементы Bj группы, не вошедшие в уже образованные смежные классы, можно разложить всю группу на смежные классы по подгруппе А.
Элементы Bj называют образующими элементами смежных классов по подгруппам.
В таблице разложения, иногда называемой групповой таблицей, образующие элементы обычно располагают в крайнем левом столбце, причем крайним левым элементом подгруппы является нулевой элемент.
4.7 Линейный код как пространство линейного векторного пространства
В рассмотренных алгебраических системах (группа, кольцо, поле) операции относились к единому классу математических объектов (элементов). Такие операции называют внутренними законами композиции элементов.
В теории кодирования широко используются модели, охватывающие два класса математических объектов (например, L и W). Помимо внутренних законов композиции в них задаются внешние законы композиции элементов, по которым любым двум элементам wÎW и аÎL ставится в соответствие элемент сÎL.
Линейным векторным пространством над полем элементов F (скаляров) называют множество элементов V (векторов), если для него выполняются следующие аксиомы:
1) множество V является коммутативной группой относительно операции сложения;
2) для любого вектора v изV и любого скаляра с из F определено произведение cv, которое содержится в V (замкнутость по отношению умножения на скаляр);
3) если u и v из V векторы, а с и d из F скаляры, то справедливо с(с+v)=cu+cv; (c+d)v=cv+dv (дистрибутивные законы);
4) если v-вектор, а с и d-скаляры, то (cd)v=c(dv) и 1*v=v
(ассоциативный закон для умножения на скаляр).
Выше было определено правило поразрядного сложения кодовых комбинаций, при котором вся их совокупность образует абелеву группу. Определим теперь операцию умножения последовательности из n элементов поля GF(P) (кодовой комбинации) на элемент поля ai GF(P)аналогично правилу умножения вектора на скаляр: ai(a1, a2, … , an)= (ai a1, ai a2, … , ai an)
(умножение элементов производится по правилам поля GF(P)).
Поскольку при выбранных операциях дистрибутивные законы и ассоциативный закон (п.п.3.4) выполняются, все множество n-разрядных кодовых комбинаций можно рассматривать как векторное линейное пространство над полем GF(2) (т.е. 0 и 1). Сложение производят поразрядно по модулю 2. При умножении вектора на один элемент поля (1) он не изменяется, а умножение на другой (0) превращает его в единичный элемент векторного пространства, обозначаемый символом 0=(0 0…0).
Если в линейном пространстве последовательностей из n элементов поля GF(P) дополнительно задать операцию умножения векторов, удовлетворяющую определенным условиям (ассоциативности, замкнутости, билинейности по отношению к умножению на скаляр), то вся совокупность n-разрядных кодовых комбинаций превращается в линейную коммутативную алгебру над полем коэффициентов GF(P).
Подмножество элементов векторного пространства, которое удовлетворяет аксиомам векторного пространства, называют подпространством.
Линейным кодом называют множество векторов, образующих подпространства векторного пространства всех n-разрядных кодовых комбинаций над полем GF(P).
В случае двоичного кодирования такого подпространства комбинаций над полем GF(2) образует любая совокупность двоичных кодовых комбинаций, являющаяся подгруппой группы всех n-разрядных двоичных кодовых комбинаций. Поэтому любой двоичный линейный код является групповым.
