Построить групповой линейный код длиной n 8 способный исправлять одиночные ошибки

Линейными называются коды, в которых проверочные символы представляют собой линейные комбинации информационных символов.

Последовательность нулей и единиц, принадлежащих данному коду, будем называть кодовым вектором.

сумма (разность) кодовых векторов линейного кода дает вектор, принадлежащий данному коду.

Линейные коды образуют алгебраическую группу по отношению к операции сложения по модулю 2. В этом смысле они являются групповыми кодами.

минимальное кодовое расстояние между кодовыми векторами группового кода равно минимальному весу ненулевых кодовых векторов.

Вес кодового вектора (кодовой комбинации) равен числу его ненулевых компонент.

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

Групповые коды удобно задавать матрицами, размерность которых определяется параметрами кода k и r. Число строк матрицы равно k, число столбцов равно

Коды, порождаемые этими матрицами, известны как (n,k)-коды, соответствующие им матрицы называют порождающими (производящими, образующими).

Порождающая матрица P может быть представлена двумя матрицами Uk и Hr (информационной и проверочной). Число столбцов матрицы Hr равно r, число столбцов матрицы Uk равно k

Теорией и практикой установлено, что в качестве матрицы Uk удобно брать единичную матрицу в канонической форме

Для кодов с d0­ = 2 производящая матрица P имеет вид

Во всех комбинациях кода построенного при помощи такой матрицы, четное число единиц.

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

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

Для кодов d0 = 3 соотношения n и k следующие: (3; 1), (7; 4), (15; 11), (31; 26), (63; 57) и так далее.

Строчки образующей матрицы P представляют собой k комбинаций искомого кода. Остальные комбинации кода строятся при помощи образующей матрицы по следующему правилу: корректирующие символы, предназначенные для обнаружения и исправления ошибки в информационной части кода, находятся путем суммирования по модулю 2 тех строк матрицы Hr, номера которых совпадают с номерами разрядов, содержащих единицы в кодовом векторе, представляющем информационную часть кода. Полученную комбинацию приписывают справа к информационной части кода и получают полный вектор корректирующего кода. Аналогичную процедуру проделывают со второй, третьей и последующими информационными кодовыми комбинациями, пока не будет построен корректирующий код для передачи всех символов первичного алфавита.

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

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

Для каждой конкретной матрицы существует своя, одна-единственная система проверок. Проверки производятся по следующему правилу : в первую проверку вместе с проверочным рядом b1 входят информационные разряды, которые соответствуют единицам первого столбца проверочной матрицы Hr; во вторую проверку входит второй проверочный разряд b2 и информационные разряды, и т. д. Число проверок равно числу проверочных разрядов корректирующего кода r.

Вид синдрома для каждой конкретной матрицы может быть определен при помощи проверочной матрицы Н’, которая представляет собой транспонированную матрицу Hr, дополненной единичной матрицей Ir, число столбцов которой равно число проверочных разрядов кода

Н’ = úçHrТIrúç.

Столбцы такой матрицы представляют собой значение синдрома для разряда, соответствующего номеру столбца матрицы Н’.

Процедура исправления ошибок в процессе декодирования групповых кодов сводится к следующему.

Строится кодовая таблица. В первой строке таблицы располагаются все кодовые векторы Ai. В первом столбце второй строки размещается вектор a1, вес которого равен 1.

Остальные позиции второй строки заполняются векторами, полученными в результате суммирования по модулю 2 вектора a1 с Аi, расположенным в соответствующем столбце первой строки. В первом столбце третьей строки записывается вектор a2, вес которого также равен 1, однако , если вектор a1 содержит единицу в первом разряде, то a2 – во втором. В остальные позиции третьей строки записывают суммы Аi и a2 .

Аналогично поступают до тех пор, пока не будут просуммированы с векторами Аi все векторы aj весом 1, с единицей в каждом из n разрядов. Затем суммируются по модулю 2 векторы aj, весом 2, с последовательным перекрытием всех возможных разрядов. Вес вектора aj определяет число исправляемых ошибок. Число векторов aj определяется возможным числом неповторяющихся синдромов и равно 2r-1 (нулевая комбинация говорит об отсутствии ошибки). Условие неповторяемости синдрома позволяет по его виду определять один-единственный соответствующий ему вектор aj. Векторы aj есть векторы ошибок, которые могут быть исправлены данным групповым кодом.

По виду синдрома принятая комбинация может быть отнесена к тому или иному смежному классу, образованному сложением по модулю 2 кодовой комбинации Аi с вектором ошибки aj, т. е. к определенной строке кодовой таблицы 5.8.

Таблица 5.8 – Кодовая таблица групповых кодов

Принятая кодовая комбинация Axn сравнивается с векторами, записанными в строке, соответствующей полученному в результате проверок синдрому. Истинный код будет расположен в строке той же колонки таблицы. Процесс исправления ошибки заключается в замене на обратное значение разрядов.

Построить кодовую таблицу, при помощи которой обнаруживаются и исправляются все одиночные ошибки и некоторые ошибки кратностью r + 1, в информационной части кода (11,7), построенного по матрице

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

Определяем систему проверок исходя из матрицы Hr

Находим вид синдрома для каждой строки таблицы. Для этого достаточно произвести проверки для кодовых комбинаций любого столбца кодовой таблицы.

Для нашего примера возьмем столбец A3 .

Таблица 5.9 – Пример таблицы для столбца А3

1) 0 1 0 0 1 0 0

2) 1 0 0 0 1 0 0

3) 1 1 1 0 1 0 0

4) 1 1 0 1 1 0 0

5) 0 0 0 0 1 0 0

6) 0 1 0 1 1 0 0

7) 0 1 1 0 1 0 0

Таким образом вектору ошибки a1 соответствует синдром 1 1 1

__________ “____________ a2________ “_________ 0 1 1

__________ “____________ a3________ “_________ 1 1 0

__________ “____________ a4________ “_________ 1 0 1

__________ “____________ a5________ “_________ 1 0 0

__________ “____________ a6________ “_________ 0 1 0

__________ “____________ a7________ “_________ 0 0 1

Предположим, приняты комбинации 1011001, 1000101, 0001100, 0000001 и 1010001. Производим проверки

Синдром первой принятой комбинации – 101, значит вектор ошибки а4 = 0001000, исправление ошибки производится заменой символа в четвертом разряде принятой комбинации на обратный. Истинная комбинация – А5, так как принятая комбинация находится в шестом столбце таблицы в строке, соответствующей синдрому 101.

Синдром второй принятой комбинации – 010, находим ее в шестой строке (010 соответствует а6) и в девятом столбце. Истинная комбинация А8 = 0001101, т.е. исправлена двойная ошибка.

Синдром третьей принятой комбинации – 001 соответствует а7, истинная комбинация А13.

Синдром четвертой из принятых комбинаций – 001 также соответствует а7, но принятую комбинацию мы находим в шестом столбце таблицы , следовательно, истинная комбинация – А5.

Синдром шестой принятой комбинации – 000. Ошибки нет.

Согласно теореме Шеннона для дискретных каналов с шумами скорость передачи информации может быть сколь угодно близкойк пропускной способности канала при сколь угодно малой вероятности ошибки. При этом не накладывается каких-либо ограничений на способ кодирования передаваемой информации и длину используемого кода.

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

Групповым () кодом называется такой код, кодовые слова которого содержат символов; причем символов, расположенных в определенных местах каждого кодового слова, являются информационными, а остальные ( ) являются проверочными (избыточными). Кодовые слова группового кода образуют группу относительно некоторой математической операции (оператора группы). Если оператор группы является линейным, то групповой код также является линейным; проверочные символы такого кода образуются в результате линейных операций с информационными символами. В случае двоичных кодов эти линейные операции сводятся к операции сложения по модулю два. Кроме того, линейный код является систематическим, если последовательность информационных символов кода не изменяется в процессе кодирования.

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

Порядок группы равен, то есть равен числу кодовых слов в группе (числу элементов множества). Если для передачи информации используется k разрядов из общего числа, то количество кодовых слов в таком коде равно (подмножество группы порядка 2 n ). При этом подмножество группы называется подгруппой, если оно само по себе образует группу относительно операции сложения по модулю 2. В подгруппу обязательно входит нулевое слово, все кодовые символы которого равны нулю (нулевой член множества ).Например, группа, имеющая порядок содержит в себе всё подгруппы всех других порядков от до.Подгруппа состоит только из одного кодового слова вида 0000, а подгруппа есть сама группа, состоящая из 16 кодовых слов.

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

Читайте также:  Почему случаются ошибки при подборе деталей по VIN-коду?

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

Для построения группового кода удобно пользоваться понятиями: производящая матрица и проверочная матрица. Производящая матрица -разрядного кода, имеющего k информационных разрядов, имеет n столбцов и k строк. Чаще всего информационными разрядами являются первые k разрядов (слева). Производящая матрица в канонической форме образуется путем дополнения столбцов к квадратной единичной матрице, содержащей k строк и k столбцов

Код, определяемый этой матрицей, содержит ненулевых разрешенных комбинаций. Благодаря тому, что первые k столбцов канонической производящей матрицы строго определены, для сравнения эквивалентности двух групповых ( )кодов достаточно сравнить только их дополнения. Коды будут эквивалентны, если их дополнения могут быть приведены к одному и тому же виду. При этом коды будут иметь одинаковые распределения кодовых расстояний и корректирующую способность.

Проверочная матрица строится для определения алгоритма кодирования и декодирования данного группового кода. Каноническая форма проверочной матрицы записывается путем дополнения k столбцов к единичной матрице r´r (дополнение приписывается слева от единичной матрицы)

ПРИМЕР. Построить линейный код n = 7, обеспечивающий исправление одиночных ошибок.

Для исправления одиночной ошибки необходимо кодовое расстояние

d ³ 2 tи + 1 = 3.

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

2 r ³ 1+ C 1 7 = 8, то есть r ³ 3.

Строим производящую матрицу, для чего берём квадратную единичную матрицу из k = ( n– r ) строк и столбцов и путём перебора добавляем проверочные разряды так, чтобы расстояние между кодовыми словами было не меньше d. Четыре строки матрицы образуют 4 кодовых слова искомого кода.

Остальные 11 кодовых слов из общего числа 2 k – 1 находятся суммированием по модулю 2 всевозможных сочетаний строк матрицы. Нулевое слово 0000 000 обычно не используется, хотя и принадлежит данному коду (принадлежит к выбранной подгруппе группы G 7).

Составим таблицу расстояний dij между кодовыми словами полученного кода.

Таблица 16 – Расстояния dij

Как видно из таблицы, кодовое расстояние данного кода равно трём ( d =3), то есть такой код способен исправить любые одиночные ошибки.

Используя вычисленные кодовые слова, запишем проверочную матрицу:

1 2 3 4 5 6 7

Для проверочной матрицы выбраны такие кодовые слова из (1.30 ), проверочные символы которых образуют единичную матрицу, а число единиц является чётным; следовательно, все строки проверочной матрицы удовлетворяют проверкам на чётность

a 2 Å a 3 Å a 4 Å a 5 = 0,

a 1 Å a 2 Å a 4 Å a 6 = 0,

a 1Å a 3 Å a 4 Å a 7 = 0. (1.31)

Полученное уравнение определяет правило проверки всех комбинаций данного кода в процессе их декодирования в приёмнике. Операция кодирования в передатчике, т.е. вычисление проверочных кодовых элементов определяется алгоритмом

a 5 = a 2 Å a 3 Å a 4,

a 6 = a 1 Å a 2 Å a 4,

a 7 = a 1 Å a 3 Å a 4. (1.32)

Если от источника сообщений в кодирующее устройство поступает последовательность вида 0110, то кодирующее устройство выдаёт комбинацию вида 0110011 в соответствии с записанным выше алгоритмом.

Допустим, что в канале связи комбинация была искажена и приняла вид 0100011. Декодирующее устройство осуществляет проверки на чётность в соответствии с уравнениями

a 2 Å a 3 Å a 4 Å a 5 = 1 Å 0 Å 0 Å 0 = 1,

a 1 Å a 2 Å a 4 Å a 6 = 0Å 1 Å 0 Å 1 = 0,

a 1 Å a 3 Å a 4 Å a 7 = 0Å 0 Å 0 Å 1 = 1. (1.33)

Наличие единиц в процессе проверок указывает на искажение кодового слова, а результаты проверок являются элементами синдрома ошибки S (1,0,1).

Синдромом последовательности кодовых символов (синдромом ошибки) называется последовательность S, определяемая матричным равенством

S = z× H T, (1.34 )

где H T- транспонированная проверочная матрица кода.

S = z× H T=( a + e ) H T = e× H T. (1.35)

Если необходимо исправить ошибку, анализ элементов синдрома продолжается. На основании второй проверки делается заключение, что символы a 1, a 2, a 4, a 6 не искажены. Следовательно, искажённым является один из символов: a 3, a 5, a 7 (код позволяет исправить только одиночную ошибку). Так как символ a 3 входит и в первое, и во второе уравнения, то искажён именно он. Этот символ в принятом кодовом слове заменяется на противоположный. Получается кодовое слово 0110011, совпадающее с переданным.

Наиболее сложным устройством декодера, определяющим возможность его реализации, является анализатор синдрома. Синдромы ошибок используемых на практике корректирующих кодов могут содержать десятки и сотни элементов, что затрудняет реализацию устройств логического анализа системы проверочных уравнений (1.33). Число логических операций, необходимое для декодирования кодового слова длиной n (сложность декодера ), обычно экспоненциально увеличивается с ростом n. Поэтому усилия разработчиков, в основном, направлены на поиск таких корректирующих кодов и таких методов декодирования, которые упрощали бы процедуру анализа синдрома ошибки.

Существенное упрощение процедуры декодирования достигается при использовании кодов Хэмминга и циклических кодов.

1) 1100011 2) 1100011

0101100 d0 =W=3 0110110 d0 =W=4

3) 1001111 4) 1001111

0011010 d0 =W=3 0101100 d0 =W=3

Задача 6.45. Определить корректирующие способности следующего кода: 001; 010; 111.

Задача 6.46. Способен ли код исправлять ошибки, если его комбинации имеют вид: 1001010; 0101110; 1101001; 0011011; 1011100?

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

Задача 6.48. Построить матрицу для группового кода, способного исправлять одиночную ошибку при передаче 16 символов первичного алфавита.

Решение. Так как число информационных разрядов кода

Число столбцов матрицы С равно длине кода n:

где nИ– число корректирующих разрядов. Для кодов с d0 = 3 (d0= 2r + 1 = 3)

Поскольку для исправления одиночной ошибки d0 = 3, то число столбцов, содержащих контрольные разряды, равно 3.

Учитывая то, что вес каждой строки проверочной матрицы П должен быть

в качестве строк проверочной матрицы можно взять трехзначные двоичные комбинации с числом единиц, большим или равным 2 ( d0 = 3 ), а W П = 1, потому что матрицу информационных разрядов лучше брать единичную: 111; 110; 101; 011.

Окончательный вид производящей матрицы таков:

Задача 6.49. Источник передает сообщения при помощи 15 двоичных комбинаций. Составить информационную

матрицы таким образом, чтобы полная производящая матрица

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

Задача 6.50. Построить образующую матрицу группового кода с расстоянием между кодами d0 = 3, способного передавать 100 различных сообщений и обладающего потенциальной способностью коррекции возможно большего числа ошибок.

Решение. Для передачи 100 сообщений необходимо соблюдение неравенства

Таким образом, число строк образующей матрицы nИ= 7, число столбцов равно

. Поскольку число корректирующих разрядов равно 4 и порождаемый код должен исправлять возможно большее число ошибок, то в качестве строк проверочной матрицы П последовательно выписываем четырехзначные двоичные комбинации весом WП = 4, 3, 2 (1111, 1110, 1101, 1011, 0111, 1100, 1010, 1001, 0110, 0101, 0011) и используем из них те комбинации, в которых большее число единиц.

Так как n И = 7, выбираем 7 комбинаций. Проверочную матрицу следует строить таким образом, чтобы число единиц в колонках матрицы П было по возможности одинаковым, так как от числа единиц в колонке матрицы П зависит число проверок, производимых при исправлении ошибок (см. задачу 6.65).

Матрица плотно упакованного кода (11; 7) имеет вид:

Задача 6.51. Построить производящую матрицу группового линейного кода, исправляющего максимально возможное число вариантов ошибок кратностью r + 1, r + 2 и т. д. при передаче пятнадцатиразрядных двоичных информационных комбинаций.

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

Проверяем условиеоптимальности кода

условие оптимальности принимает вид:

Вес каждой комбинации проверочной матрицы П

Поскольку число строк производящей матрицы С равно nИ, в качестве проверочных используются все четырехзначные двоичные комбинации весом

Окончательный вид матрицы С:

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

Задача 6.53. Построить порождающую матрицу группового кода (31; 26). Проанализировать, оптимален ли полученный код с точки зрения соотношения информационных и корректирующих разрядов.

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

Задача 6.55. Источник сообщений рассчитан на передачу 120 различных одиннадцатиразрядных комбинаций. Одним из главных требований технического задания (ТЗ) на разработку приемного устройства является максимальная простота дешифратора и возможность коррекции одиночных ошибок в каждой передаваемой комбинации. Построить образующую матрицу группового кода, удовлетворяющую требованиям ТЗ.

Решение. Задана длина кода n = 11 и минимальное расстояние между кодами d0 = 3. Согласно (62)

Минимальная простота дешифратора достигается при минимальном количестве сумматоров по модулю 2 в декодере, что возможно при минимальном весе комбинаций проверочной матрицы П. Для этого в качестве векторов, составляющих строки матрицы П, выбираем четырехзначные двоичные комбинации весом WП = 2, 3, 4 (см. задачу 6.50) и используем те комбинации, в которых содержится меньшее число единиц, а именно: 0011; 0101; 1010; 1100; 0111.

Искомая матрица имеет вид:

Задача 6.56. Построить производящую матрицу группового кода с d0 = 3, удовлетворяющего условию максимальной простоты кодера и декодера при передаче 1000 сообщений.

Задача 6.57. Построить групповой код по заданной производящей матрице:

Решение. Число строк матрицы n И = 4. Следовательно, число возможных информационных комбинаций

1) 0000 5) 0010 9) 0001 13) 0011

2) 1000 6) 1010 10) 1001 14) 1011

3) 0100 7) 0110 11) 0101 15) 0111

4) 1100 8) 1110 12) 1101 16) 1111

Находим последовательно корректирующие разряды всех информационных комбинаций путем суммирования по модулю 2 тех

Читайте также:  Целостность системных файлов была проверена, и результат составил 0x490

строк матрицы П, номера которых совпадают с номерами разрядов содержащих единицы в информационной части кода:

1) 000 2) 111 3) 110 4) 111

5) 101 6) 111 7) 110 8) 111

9) 011 10) 111 11) 110 12) 111

13) 101 14) 111 15) 110 16) 111

110 011011 101

001 000 011

Окончательно комбинации корректирующего кода имеют такой вид:

1) 0 0 0 0 0 0 0 9) 0 0 0 1 0 1 1

2) 1 0 0 0 1 1 1 10) 1 0 0 1 1 0 0

3) 0 1 0 0 1 1 0 11) 0 0 0 1 1 1 0

4) 1 1 0 0 0 0 1 12) 1 0 0 1 1 0 0

5) 0 0 1 0 1 0 1 13) 0 0 1 1 1 1 0

6) 1 0 1 0 0 1 0 14) 1 0 1 1 0 0 1

7) 0 1 1 0 0 1 1 15) 0 1 1 1 0 0 0

8) 1 1 1 0 1 0 0 16) 1 1 1 1 1 1 1

Задача 6.58. Какой вид имеют комбинации группового кода с d0= 3, построенного для передачи четырехзначных двоичных комбинаций на все сочетания, если его порождающая матрица имеет вид:

Задача 6.59. Показать процесс построения кодовых векторов плотно упакованного группового кода, заданного матрицей, удовлетворяющей условиям задачи 6.52.

Задача 6.60. Групповой код построен по матрице

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

Решение. Производящая матрица С в виде информационной матрицы И и проверочной матрицы П может быть представлена следующим образом:

Согласно правилу построения системы проверки (см. с. 96), система проверок для кодов, построенных С, будет иметь вид:

Для того чтобы знать, какая комбинация значений разрядов синдрома

будет соответствовать ошибке в определенном разряде принятой комбинации, строим проверочную матрицу Н, строками которой являются столбцы матрицы П, дополненные единичной матрицей

Если разряды синдрома соответствуют первому столбцу матрицы Н, т. е.

Полные комбинации кода имеют вид соответственно: 1100110; 0010110; 1010101.

Предположим, сбои произошли в первом разряде первой комбинации, в четвертом разряде второй и в последнем разряде третьей, т. е. приняты они в таком виде:

0100110, 0011110 и 1010100.

Находим проверочные векторы согласно системе проверок.

Для первой комбинации:

Синдром 011 показывает, что в первом разряде символ следует заменить на обратный.

Для второй комбинации:

синдром – 1 1 1, ошибка в четвертом разряде.

Для третьей комбинации:

синдром – 0 0 1, ошибка в седьмом разряде.

Задача 6.61. Какими способами можно проверить корректирующие способности кодов, построенных по заданным производящим матрицам?

Задача 6.62. Убедиться в том, что в кодовых векторах 1000111, 0110101, 1101001, 0000000 группового кода, построенного по следующей матрице:

может быть исправлена ошибка в любом из информационных разрядов.

Решение. Проверочная матрица П имеет вид:

соответствующая ей система проверок

Последовательно изменяем в исследуемых векторах по одному информационному разряду и по данной системе, проверок находим вид синдрома.

синдром –111. синдром –011

синдром – 110. синдром – 101.

синдром –111. синдром –011.

синдром – 110. синдром –101.

синдром – 111. синдром –011.

синдром –110. синдром –101.

Задача 6.101. Эквивалентны ли корректирующие способности кодов, построенных по следующим образующим матрицам С15;11=

Задача 6.102. Построить несколько комбинаций циклического кода с числом информационных разрядов nи=11 и образующим многочленом х4+ х3 +1.

Задача 6.103. Методом умножения образующего многочлена 1011 на многочлены четырехзначного двоичного кода на все сочетания построить циклический код.

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

Вырабатываемое источником информации единичное сообщение формируется в безызбыточную комбинацию, причем все комбинации должны иметь одинаковую длительность (разрядность n).

Рассмотрим пример кодирования и исправления однократных ошибок групповым кодом Хемминга для n = 4 разрядных информационных блоков. Из условия (3.3.) следует, что m = 7, код (7,4) имеет семь разрядов, из них 4 информационных.

Построим “матрицу ошибок”, т.е. переберем все возможные однократные ошибки (место ошибки определим вектором с одной единицей):

Указатель разряда, где есть ошибка, называют синдромом ошибки. При рассмотрении синдрома ошибки следует выделить первую, вторую и третью строки, которые указывают на возможные ошибки в первом, втором и четвертом разрядах. Синдромы этих разрядов в своем начертании имеют по одной единице, что позволяет выбрать эти разряды для размещения контрольных символов. Проверочные (кодовые) уравнения для них запишем по столбцам:

В выбранном 7 элементном блоке 1, 2, 4 разряды заняты под проверочные, а в 3, 5, 6, 7 разрядах запишем передаваемую информацию.

Найдем проверочные символы из уравнения (3.5,б)

а1 = а3 Å а5 Å а7 = 0 Å 1 Å1 = 0 а1 = 0

а2 = а3 Å а6 Å а7 = 0 Å 0 Å 1 = 1 а2 = 1

а4 = а5 Å а6 Å а7 = 1 Å 0 Å 1 = 0 а4 = 0

Теперь запишем закодированный блок

Допустим, что при приеме этого блока произошла ошибка в третьем разряде (т.е. мы приняли блок вида 1010110), тогда проверочные равенства (3.5,а) в приемнике дадут синдром ошибки:

а1 Å а3 Å а5 Å а7 = 0 Å 1 Å 1 Å 1 = 1

а2 Å а3 Å а6 Å а7 = 1 Å 1 Å 0 Å 1 = 1

а4 Å а5 Å а6 Å а7 = 0 Å 1 Å 0 Å 1 = 0.

Полученный синдром 011 указывает, что ошибка произошла в третьем разряде, и, значит, третий разряд надо исправить (просто инвертировать на обратный знак). Так можно обнаружить и исправить любую однократную ошибку (в любом разряде).

Групповые коды, исправляющие кратные ошибки

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

Пример. Пусть синдром ошибки в 1-м разряде декодируемой комбинации имеет вид 0001, а в 4-м разряде – 1001. Это означает, что символ а1 входит в 1-е и 4-е равенства, а символ а4 – только в 1-е равенство. Если произойдут ошибки одновременно в 1-м и 4-м разрядах, то равенство, в которое входят символы а1 и а4 останется выполненным, так как

Построить групповой линейный код длиной n 8 способный исправлять одиночные ошибки

Построить групповой линейный код длиной n 8 способный исправлять одиночные ошибки

– противоположен символу аi, т.е. если аi=1, то

=0 и наоборот). В соответствии со структурой синдромов ни а1, ни а4 во 2-е и 4-е равенства не входят, и следовательно, на их выполнение не влияют. Поэтому при ошибках в 1-м и 4-м разрядах не будет выполняться только 4-е равенство, а значит, синдром такой парной ошибки имеет вид 1000, что соответствует сумме по модулю 2 синдромов в 1-м и 4-м разрядах: 1001Å0001=1000.

Итак, синдром двойной ошибки равен сумме (по модулю 2) синдромов соответствующих одиночных. Студенту рекомендуется самостоятельно убедиться, что для ошибок любой кратности справедлив тот же вывод. Для однозначности опознавания ошибок при суммировании синдромов одиночных ошибок должны формироваться не повторяющиеся синдромы, т.е. не используемые для опознавания других ошибок.

Для пояснения вернемся к рассмотренному ранее коду (7,4). Предположим, что произошли ошибки в 1-м и 4-м разрядах. Синдром такой двойной ошибки 001 + 011 = 010. Но он уже используется: соответствует ошибке во 2-м разряде, т.е. данный код не исправляет двойных ошибок. Из этого, в частности, следует еще и такой вывод: синдромы одиночных ошибок в информационных разрядах кодов, исправляющих двойные ошибки, должны содержать не менее четырех единиц. В самом деле, допустим, что синдром ошибки в одном из информационных разрядов имеет вид 00000111, синдром ошибки в 1-м разряде (проверочном) – 00000001, во 2-м – 00000010, в 3-м – 00000100. Тогда синдром ошибок в 1-м и 2-м разрядах совпал бы с синдромом ошибок в этом информационном и 3-м разрядах (00000011), что привело бы к невозможности однозначного декодирования. Кроме того, в синдромах ошибок в информационных разрядах единицы должны быть расположены так, чтобы сумма двух синдромов ошибок в информационных разрядах имела не менее трех единиц и не повторялась в виде одинаковых комбинаций.

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

2. Что называется основанием дискретного кода?

3. Какие коды называются систематическими, а какие – несистематическими?

4. Дайте определение конечной группы.

5. Почему некоторые виды корректирующих кодов называют групповыми?

6. В чем заключается свойство замкнутости подгруппы разрешенных комбинаций группового кода?

7. Что называется дистанцией Хэмминга в бинарных блочных кодах?

8. Каким должно быть минимальное расстояние Хэмминга в бинарных блочных кодах?

9. Каким должно быть минимальное расстояние Хэмминга в коде, исправляющем ошибки кратности К?

10. Каким должно быть минимальное расстояние Хэмминга в коде, обнаруживающем ошибки кратности К?

11. Как строится порождающая матрица группового кода?

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

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

14. Какое количество единиц должны иметь разрешенные комбинации группового кода, обнаруживающего двойные ошибки?

15. Что называется синдромом ошибки в групповых кодах?

16. Объясните принцип составления проверочной матрицы группового кода.

17. Поясните принцип составления системы проверочных равенств по заданной проверочной матрице группового кода.

19. Основание кода источника информации L=32. Определите необходимую разрядность безызбыточных комбинаций после перехода на бинарный код.

20. Задана разрядность безызбыточной комбинации и кратность исправляемых кодом ошибок. Определите необходимое количество разрядов, отводимых под проверочные символы.

21. Что называется вектором ошибки?

22. Как соотносятся между собой векторы одиночных и кратных ошибок в групповых кодах?

23. Сколько единиц должен содержать синдром ошибки в проверочном разряде группового кода?

1. Записать проверочную матрицу группового кода 7,4, отводя под проверочные символы разряды: а) 1, 2 и 4-й; б) 1, 2 и 3-й, в) 5, 6 и 7-й. Закодировать безызбыточную комбинацию 0001.

2. Записать проверочную матрицу группового кода, 15,11, отводя под проверочные символы разряды: а) 1, 2, 4 и 8-й; б) 1, 2, 3 и 4-й; в) 12, 13, 14 и 15-й. Составить порождающую матрицу.

3. Составить проверочную матрицу группового кода 8,2, отводя под информационные символы разряды: а) 7-й и 8-й; б) 1-й и 2-й; в) 1-й и 5-й. Закодировать безызбыточную комбинацию 11.

Читайте также:  ЧТО ТАКОЕ КОД ОШИБКИ 100 ПРИ РЕГИСТРАЦИИ В КОНТАКТЕ

4. Для группового кода 7,4 (задача 1,a) составить систему проверочных равенств для декодирования мажоритарным методом.

5. Для группового кода 7,4 (задача 1,б) составить систему проверочных равенств для декодирования по синдромам.

6. Для группового кода 8,2 (задача 3,а) составить систему проверочных равенств для декодирования мажоритарным методом.

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

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

Ознакомимся с принципами построения циклических кодов на примере кода (7,4). Образуем порождающую матрицу этого кода из комбинаций, содержащих по три единицы. Учтем, что единицы в комбинациях не должны чередоваться с нулями через равные промежутки, так как при суммировании результирующая комбинация по условию замкнутости должна иметь не менее трех единиц. Этим требованиям отвечают только два варианта циклических комбинаций: 0001101 и 0001011. Таким образом, существуют только две матрицы циклического кода (7,4):

Построить групповой линейный код длиной n 8 способный исправлять одиночные ошибки

Построить групповой линейный код длиной n 8 способный исправлять одиночные ошибки

Рассмотрим первый вариант циклического кода (7,4). Кодовую комбинацию 0001101 удобно представлять в виде комбинации 1101 с приписанными в старших разрядах тремя нулями. Будем называть комбинацию 1101 порождающей (образующей). Циклический сдвиг кодовой комбинация на один разряд влево можно рассматривать как умножение порождающей комбинации на комбинации 10, 100 и 1000. Полученные таким образом комбинации, естественно, делятся на порождающую без остатка. Не вошедшие в порождающую матрицу разрешенные комбинации можно получить суммированием комбинаций, вошедших в матрицу. Один из возможных вариантов получения всех 15 разрешенных комбинаций сводится к следующему. В качестве 1-й разрешенной комбинации возьмем, например, первую комбинацию из порождающей матрицы: 0001101. Поочередно сдвигая эту комбинацию влево на один разряд, будем иметь еще шесть разрешенных комбинаций. Седьмая комбинация при этом будет такой: 1000110. Просуммировав 1-ю и 2-ю комбинации из порождающей матрицы, получим 8-ю разрешенную комбинацию. Циклическим сдвигом этой комбинации получаем еще шесть разрешенных комбинаций. Наконец. 15-ю комбинацию получаем путем суммирования (по модулю 2) всех комбинаций порождающей матрицы, за исключением 3-й.

Аналогично формируется и второй вариант циклического кода (7,4). Итак, все разрешенные комбинации циклического кода делятся без остатка на порождающую комбинацию, а все запрещенные – не делятся. Следовательно, наличие остатка при делении принятой комбинации на порождающую означает, что в принятой комбинации есть ошибка.

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

В литературе при рассмотрении теории циклических кодов для удобства кодовые комбинации обычно записываются условно в виде многочленов. С каждой комбинацией сопоставляется соответствующий степенной многочлен, сформированный по следующему правилу: единица в i-м разряде комбинации обозначается как xi-1, отсутствие в многочлене элемента xk-1 означает, что в k-м разряде комбинации стоит нуль. Например, порождающие многочлены рассмотренных вариантов циклического кода (7,4) 1101 и 1011 записываются условно так: х3+х2+1 и х3+х+1, кодовой комбинации 10000000 эквивалентен многочлен х7.

Построение циклического кода должно начинаться с выбора необходимого порождающего многочлена. В литературе приведены таблицы возможных порождающих многочленов с указанием корректирующих возможностей кодов при использовании этих многочленов. Так, при трех проверочных разрядах порождающие (неприводимые) многочлены имеют два вида: х3+х+1 (1011) и х3+х2+1 (1101); для четырех проверочных разрядов имеется три неприводимых многочлена: х4+х+1 (10011), х4+х3+1 (11001), х4+х3+х2+х+1 (11111).

Безызбыточная комбинация при выбранном многочлене может кодироваться двумя способами.

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

Во втором варианте кодирование сводится к умножению (с суммированием по модулю 2) безызбыточной комбинации на порождающую. Например, при кодировании безызбыточной комбинации 1111 циклическим кодом с порождающей комбинацией 1011 получается следующая комбинация

Как видно из примера, такой код – несистематический, поскольку в нем нет в явном виде информационных и проверочных символов.

Декодирование систематических циклических кодов

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

Если циклический код используется только для обнаружения ошибок, достаточно поделить принятую комбинацию на порождающую. Остаток свидетельствует о наличии в принятой комбинации ошибки.

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

Алгоритм первый. Декодируемая комбинация делится на порождающую. Если остаток после деления соответствует синдрому ошибки в младшем разряде, символ исправляется в этом разряде. Если получается иной синдром ошибки, декодируемая комбинация сдвигается на один разряд влево и процедура деления и определения остатка повторяется. Этот цикл (сдвиг – деление) повторяется до тех пор, пока полученный остаток не совпадет с синдромом ошибки в младшем разряде. При совпадении исправляется ошибка в младшем разряде, после чего комбинации сдвигается в обратную сторону в исходное состояние (если было проведено m делений, то производится сдвиг вправо на m-1 разрядов).

Алгоритм второй. Возможность применения этого метода основана на следующем. При делении комбинации с ошибкой на порождающую комбинацию остаток от деления образуется за счет того, что вектор ошибки не делится на порождающую комбинацию. Кроме того, вектор хn+k-1, деленный на порождающий многочлен, дает остаток с единицей в k-м разряде и нулями в остальных разрядах. Например, в коде (7,4) многочлен х7 (комбинация 10000000) дает остаток 001, многочлен х8 – остаток 010 и т.д. С другой стороны, разрешенная комбинация, сдвинутая влево на любое число разрядов без перестановки старших разрядов (сдвиг при этом сводится к дописанию справа соответствующего количества нулей), также делится на порождающую без остатка. Указанные факторы позволяют применить следующую процедуру исправления ошибок.

1. Пришедшая комбинация делится на порождающую.

2. При отсутствии остатка комбинация считается безошибочной и передается потребителю информации.

3. Если остаток отличен от нуля, он сравнивается с синдромом, соответствующим ошибке в старшем разряде.

4. Если при сравнении происходит совпадение, принимается решение о наличии ошибки в старшем разряде и производится исправление.

5. Если остаток не равен нулю и не совпадает с синдромом ошибки в старшем разряде, к остатку приписывается оправа необходимое количество нулей и деление продолжается. Эта процедура повторяется до тех пор, пока остаток после деления не совпадет с синдромом ошибки в старшем разряде. После выполнения этого условия, если в процессе деления было приписано дополнительно в общей сложности m нулей, исправляется символ в (n-m) -м разряде декодируемой комбинации.

Пример. По каналу связи принята кодовая комбинация 1001000, закодированная циклическим кодом (7,4) с порождающей комбинацией 1011. Необходимо произвести декодирование, т.е. исправление возможной ошибки, применив первый алгоритм.

Решение. 1. Делим полученную комбинацию на порождающую:

1001000 / 1011

2. Поскольку синдром ошибки в младшем разряде равен 001, т.е. не совпадает в полученным, сдвигаем полученную комбинацию на 1 разряд влево в снова производим деление:

0010001 / 1011

3. Так как остаток снова не равен 001, сдвигаем принятую комбинацию еще на разряд влево и делим:

0100010 / 1011

4. Еще раз повторяем сдвиг и деление:

1000100 / 1011

5. Исправляем символ в младшем разряде сдвинутой комбинация:

6. Сдвигаем комбинацию в обратном направлении (вправо) на три разряда: 1011000.

7. Отсекаем три младших (проверочных) разряда и передаем потребителю информации комбинацию 1011.

Пример. Используется тот же код, что и в предыдущем примере. Получена комбинация 1001000. Необходимо произвести декодирование по 2-му алгоритму.

Решение. Предварительно в память декодера должен быть заложен синдром ошибки в старшем разряде. Найдем значение этого синдрома как остаток от деления вектора ошибки в 7-м разряде на порождающую комбинацию:

1000000 / 1011

Таким образом, синдром ошибки в 7-м разряде равен 101. Делим полученную комбинацию на порождающую:

=101 – синдром ошибки в 7-м разряде

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *