Граница Варшамова – Гильберта:
Таким образом, граница Хемминга и Плоткина определяют необходимое количество проверочных символов, а граница Варшамова- Гильберта достаточное их количество.
Если количество проверочных символов выбрано так, что оно удовлетворяет эти границам, то код считается близким к оптимальному.
Коды, в которых число проверочных символов выбирается равным границам Хемминга или Плоткина называется совершенным или полноупакованным.
5.3.Линейные (систематические) коды.
5.3.1.Механизмы кодирования и синдромного декодирования.
В линейных систематических кодах информационные символы при кодировании не изменяются, а проверочные символы получаются в результате суммирования по модулю 2 определенного числа информационных символов.
Запишем некоторые разрешенные кодовые комбинации систематического кода (n, k) , где - информационные символы; - проверочные символы.
Тогда , где - некоторый коэффициент принимающий значение 0 или 1 в зависимости от того, участвует или нет данный информационный символ в формировании проверочного символа .
Обнаружение и исправление ошибок систематическим кодом сводится к определению и последующему анализу синдрома или вектора ошибок.
Под синдромом понимают некую совокупность символов сформированную, путем сложения по модулю 2 принятых проверочных символов и вычисленных проверочных символов. Вычисленные проверочные символы получаются из принятых информационных символов по тому же правилу, которое используется для формирования проверочных символов.
Если при приеме информационных и проверочных символов (принятое считается полная кодовая комбинация, состоящая из информационных и проверочных символов) не произошло ошибок, то принятые вычисленные проверочные символы будут совпадать. В этом случае все разряды синдрома будут равны нулю. Таким образом, нулевой синдром соответствует случаю отсутствия ошибок.
Если в принятых кодовых комбинациях есть ошибки, то в разрядах синдрома появятся 1. Это и есть способ обнаружения ошибок систематическим кодом, который лежит в основе синдромного декодирования.
Если код имеет минимальное кодовое расстояние , то такой код способен исправлять ошибки. Это значит, что по виду синдрома можно определить номер ошибочной позиции принятой кодовой комбинации.
Процедура построения систематического кода, способного обнаруживать ошибки, сводится к выбору весовых коэффициентов так, чтобы синдром, рассматриваемый как двоичное число, указывал на номер ошибочной позиции.
Пусть требуется построить систематический код длиной n=7, способный исправлять одиночные ошибки, т.е. =2t+1=3. Пользуясь условием границы Хемминга, найдем минимальное число проверочных символов:
Выберем r=3, следовательно, код (7,4)- совершенный и близкий к оптимальному. Тогда кодовая комбинация - это и есть кодовая комбинация (7,4). Для нашего случая получим:
,
,
.
Найдем весовые коэффициенты . Для этого запишем все возможные трехразрядные кодовые комбинации синдрома:
000, 001, 010, 100, 011, 101, 110, 111
Если ошибки отсутствуют, то синдром должен быть нулевым. Допустим, что появление одной 1 в синдроме будет связано с ошибками в проверочных символах кодовой комбинации. Тогда
100 → ошибка в b1,
010→ ошибка в b2,
001→ ошибка в b3.
Появление большего числа единиц в синдроме будет связано с ошибками в информационных символах.
Теперь присвоим информационным символам с ошибками оставшиеся синдромы, причем в порядке возрастания их двоичных символов:
011→ ошибка в ,
101→ ошибка в ,
110→ ошибка в ,
111→ ошибка в .
Для определения коэффициентов их надо подобрать таким образом, чтобы при возникновении ошибки в информационном символе аi появлялся бы соответствующий этой ошибке синдром.
Например, для ошибки в символе необходимо в уравнениях правила формирования проверочных символов коэффициенты при этом ошибочном символе взять соответствующими синдрому этого символа. Тогда
→ =0, = 1, =1,
→ =1, =0, =1,
→ =1, =1, =0,
→ =1, =1, =1.
Тогда по этим коэффициентам строятся уравнения формирования проверочных символов, которые будут иметь вид:
,
,
.
Достарыңызбен бөлісу: |
