Стандартное расположение группового кода представляет разложение множества всех возможных n-элементных слов, представляющих собой группу, на смежные классы по подгруппе из 2k кодовых слов, составляющих (n,k)-код (см. таблицу 2).
| Таблица 2 | |||||
| 
| | 
| | 
|
| 
|
| 
| ||
| |||||
| 
|
| 
| ||
|
| |||||
| 
|
| 
|
Образующие или лидеры смежных классов выбираются таким образом, чтобы в их состав вошли наиболее вероятные образцы ошибок в кодовом слове, т.е. образцы ошибок с наименьшим весом.
Пример. Код (5,3) имеет матрицы
и 
а стандартное расположение имеет вид,
Этот код имеет d0=3. Он гарантирует исправление одиночных ошибок, конфигурация которых дана в первом столбце.
Процедура исправления ошибок следующая. Принятое кодовое слово анализируют и определяют, в каком столбце оно находится, а затем в качестве исправленного кодового слова берут слово, находящееся в верхней строке.
Однако, если длина кода большая и таблица стандартного расположения также значительная, пользоваться таким алгоритмом неудобно. Поэтому при декодировании используют таблицу синдромов (декодирования), представляющую собой список образцов ошибок (см. первый столбец стандартного расположения) и список соответствующих синдромов, которые однозначно характеризуют каждый смежный класс.
Коды Хэмминга
Кодом Хэмминга называется (n,k)-код, проверочная матрица которого имеет r = n-k строк и 2r-1 столбцов, причем столбцами являются все различные ненулевые последовательности.
|
|
Пример. Для (7,4)-кода Хэмминга
или 
Проверочная матрица любого кода Хэмминга всегда содержит минимум три линейно зависимых столбца, поэтому кодовое расстояние кода равно трем.
Если столбцы проверочной матрицы представляют упорядоченную запись десятичных чисел, т.е. 1,2,3... в двоичной форме, то вычисленный синдром
однозначно указывает на номер позиции искаженного символа.
Пример. Для (7,4)-кода Хэмминга проверочная матрица в упорядоченном виде имеет вид
Пусть переданное кодовое слово 
,а принятое слово - 
.
Синдром, соответствующий принятому слову будет равен
Вычисленный синдром указывает на ошибку в пятой позиции.
Проверочная матрица в упорядоченном виде представляет совокупность проверочных уравнений, в которых проверочные символы занимают позиции с номерами 2i (i=0,1,2...).
Для (7,4)-кода Хэмминга проверочными уравнениями будут
где 
- проверочные символы.
Элементы синдрома определяются из выражений
Корректирующая способность кода Хэмминга может быть увеличена введением дополнительной проверки на четность. В этом случае проверочная матрица для рассмотренного (7,4)-кода будет иметь вид
а кодовое расстояние кода d0=4.
Проверочные уравнения используются для построения кодера, а синдромные - декодера кода Хэмминга.
ЛИТЕРАТУРА
1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.
2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. – М.: Высшая школа, 2001 г. – 383с.
|
|
3. Цапенко М.П. Измерительные информационные системы. -. – М.: Энергоатом издат, 2005. - 440с.
4. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.
5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.