Лабораторная работа 4
Работа с групповыми кодами
Цели работы:
построение группового кода и демонстрация процесса ис правления ошибки в произвольном разряде корректирующего кода;
приобретение практических навыков построения порождающей и проверочной матрицы для групповых кодов;
программная реализация соответствующих алгоритмов кодирования.
Теоретические сведения
Систематический код – групповой n-значный код, в котором из n сим волов, образующих кодовую комбинацию, nu символов информационные, а nk = n – nu – избыточные, предназначенные для проверки.
Систематические коды удобно задавать при помощи производящей мат рицы. Число строк матрицы равно пи, число столбцов равно n.
Производящая матрица С может быть представлена при помощи двух матриц И и П (информационной и проверочной). Число столбцов матрицы П равно nk, число столбцов матрицы И равно nu.
Теорией и практикой установлено, что в качестве матрицы И удобно брать единичную матрицу:
При выборе матрицы П исходят из следующих рассуждений: чем больше единиц в разрядах проверочной матрицы П, тем ближе соответствую щий порождаемый код к оптимальному.
Критерием оптимальности таких кодов является соблюдение условия:
где r – число ошибок.
С другой стороны, число единиц в матрице П определяет число сумма торов по модулю 2 в шифраторе и дешифраторе, т. е. чем больше единиц в матрице П, тем сложнее аппаратура. Но даже если основным требованием к аппаратуре будет ее простота, вес каждой строки матрицы П должен быть не менее WП d0 – WИ, где WИ – вес соответствующей строки матрицы И. Если матрица И – единичная, то WИ = 1 (при WИ > 1 усложнилось бы как построе ние кодов, так и их техническая реализация).
Производящая матрица позволяет получить все возможные комбина ции кода суммированием по модулю 2 всех возможных сочетаний строк мат рицы.
Пример. Построить матрицу для группового кода, способного исправ лять одиночную ошибку при передаче 16 символов первичного алфавита.
Кодовое расстояние d0 = 3. Так как число информационных разрядов кода nu = 4 (16 = 24 = ), то число строк производящей матрицы С должно быть равно 4. Число столбцов матрицы С равно n; n – длина кода, в свою очередь, равна nu + nk; nk – число корректирующих разрядов, равное
Следовательно, число столбцов, содержащих контрольные разряды, должно быть равно 3, а общее число столбцов матрицы С равно: nu + nk = 4 + 3 = 7.
Так как вес каждой строки проверочной матрицы П должен быть WП ≥ d0 – WИ, то в качестве ее строк могут быть выбраны трехзначные двоич ные комбинации с числом единиц 2: 111; 110; 101; 011.
Как видно из примера, основным требованиям могут удовлетворять несколько матриц. Выбор той или иной из матриц, возможных для данного nи, nk, и d0, определяется по дополнительным требованиям: минимум кор ректирующих разрядов или максимальная простота аппаратуры.
В процессе декодирования систематического кода осуществляются проверки, идея которых в общем виде может быть представлена следующим образом:
 , где j = 1, 2, ..., nk . (2)
Для каждой конкретной матрицы существует своя, одна-единствен ная система проверок. Проверки производятся по следующему правилу: в первую вместе с проверочным разрядом р1 входят информационные разря ды, соответствующие единицам первого столбца проверочной матрицы П, во вторую – второй проверочный разряд р2 и информационные разряды, соот ветствующие единицам второго столбца проверочной матрицы и т. д. Число проверок равно числу проверочных разрядов корректирующего кода nk. В результате проверок образуется проверочный вектор S1, S2,… , который называют синдромом. Если вес синдрома равен нулю, то принятая комбина ция считается безошибочной. Но если хотя бы один разряд проверочного вектора содержит единицу, принятая комбинация содержит ошибку. Исправ ление ошибки производится по виду синдрома, так как каждому ошибочному разряду соответствует один-единственный проверочный вектор.
Вид синдрома для каждой конкретной матрицы может быть определен при помощи контрольной матрицы Н, представляющей собой транспониро ванную матрицу П, дополненную единичной матрицей I, число столбцов ко торой равно числу проверочных разрядов кода:
 .
Столбцы такой матрицы – значение синдрома для разряда, соответству ющего номеру столбца матрицы Н.
Пример. Групповой код построен по матрице:
Показать процесс исправления ошибки в произвольном разряде коррек тирующего кода, информационная часть которого – четырехразрядные ком бинации натурального двоичного кода.
Решение. Кодовое расстояние d0 = 3. Число проверочных символов nк = 3; nи = 4.
Производящая матрица С в виде информационной матрицы И и прове рочной матрицы П может быть представлена следующим образом:
Согласно принципу построения системы проверки (2), система прове рок для кодов, построенных по матрице С, будет иметь вид:
Чтобы знать, какая комбинация значений разрядов синдрома S1, S2, S3 будет соответствовать ошибке в определенном разряде принятой комбина ции, строим контрольную матрицу Н, ее строками являются столбцы матри цы П, дополненные единичной транспонированной матрицей I, размерность которой определяется числом избыточных разрядов кода, т. е. в нашем случае равная 3. Таким образом:
Если разряды синдрома соответствуют первому столбцу матрицы Н, т. е. S1 = 0, S2 = 1, S3 = 1, то ошибка в первом разряде принятой комбинации; если синдром имеет вид 101, что соответствует второму столбцу матрицы Н, то ошибка во втором разряде; синдром 001 соответствует ошибке в третьем про верочном разряде кода.
В качестве примера проверки корректирующих свойств кода использу ем комбинации кода вида:
1 1 0 0 1 1 0 0 0 1 0 1 1 0
Пусть сбои произошли в первом разряде первой комбинации и в чет вертом разряде второй, т. е.:
0 1 0 0 1 1 0 0 0 1 1 1 1 0
Находим проверочные векторы согласно системе проверок. Для первой комбинации: Р1 = 1, Р2 = 1, Р3 = 0.
Синдром – 0 1 1 показывает, что в первом разряде символ следует заме нить на обратный.
Для второй комбинации:
Синдром – 1 1 1, ошибка в четвертом разряде.
Задание
Ознакомиться с теоретической частью, используя дополнительную литературу.
Исходя из полученных у преподавателя исходных данных (количества передаваемых сообщений N), рассчитать необходимое число информацион ных и контрольных разрядов для систематического кода, обнаруживающего и исправляющего одиночные ошибки.
Составить порождающую и проверочную матрицы, а также уравнения проверки по пункту 2, исходя из количества информационных разрядов.
Провести программный контроль выполнения 2 и 3 пунктов на примере некоторых случайных кодовых комбинаций рассчитанной ранее разрядности.
Составить отчет.
Контрольные вопросы
1. Приведите классификацию корректирующих кодов по способу введения и использования избыточности, по структуре кода.
2. Какие из систематических кодов имеют наибольшую практическую значимость и почему?
3. Что такое синдром ошибки?
4. Как получают проверочную матрицу при формировании систематических кодов и чем объясняется такое требование ее построения?
5. Какими выражениями удобно пользоваться для практических расчетов при определении числа контрольных разрядов с: d = 3? d = 4?
|
