Алгоритм Чейза

Пролог

Друзья, всем привет! Недавно начал изучать помехоустойчивые коды и моделировать процесс их работы, и понял что по-человечески написанных топиков по этой теме совсем немного, а точнее мало. Мудрёные книги есть, но на то они и мудрёные, что на их изучение нужно время, а порой нужно получить какие-то базовые знания и представления по теме, за совсем сжатый промежуток времени. Как пример, могу привести статью по кодам Хэмминга, она мне здорово помогла, когда я только начинал возиться с кодами. Так же доступно подобные коды описаны здесь.

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

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

Немного теории

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

Декодирование блокового кода может быть осуществлено посредством жёсткого или мягкого принятия решения. В декодировании с жёстким принятием решения, каждому принимаемому биту в демодуляторе приписывается значение
0 или 1. Декодер с мягким принятием решения принимает не только бинарную величину 1 или 0, но также доверительную величину, связанную с заданным битом. Декодер будет использовать эту мягкую информацию, и на выходе мы получим такое же жёсткое решение.
Если кратко, то на вход жесткого декодера, из канала, поступает вектор из значение 0 или 1. На вход мягкого декодера поступает вектор из значений (-∞; +∞). Использование мягких решений даёт больше возможностей, так как предоставляет более широкий маневр по исправлению возникающих помех.
Алгоритм Чейза — блоковый код с мягким решением.

Алгоритм Чейза

Алгоритм Чейза — это понятный и относительно эффективный алгоритм исправления ошибок(помех) в передаваемом сообщение. Главной идеей алгоритма является генерирование массива кодовых слов, которые будет содержать слово, ближайшее к принятой последовательности. Алгоритм основан на том, что если слово, декодированное обычным жёстким решением содержит ошибку, то одно из «ближайших» к нему кодовых слов скорее всего совпадает с переданным.

Пример работы

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

1. Пусть у нас есть исходный вектор u = [1, 0, 0, 1];
2. Кодируем его по алгоритму Хэмминга и получим с = [1, 0, 0, 1, 1, 0, 0];
3. Добавляем проверку чётности — с[8] = ∑с mod 2. Стоит отметить, что для данных целей удобно использовать расширенный код Хэмминга. Но о нём лучше отдельно.
В итоге получаем с = [1, 0, 0, 1, 1, 0, 0, 1].
4. Вносим некоторые помехи и получаем вектор r = [-1.02, -1.1, -2, 1.95, 0.98, -2.34, -0.73, 1.97].
5. Мы используем второй алгоритм Чейза. Он характеризуется следующим методом генерирования массива проверочных кодовых слов:

• Выбрать из принятого вектора r p наименее надёжных бит, то есть p бит наименьших по модулю. Последний бит в векторе в расчёт не принимается, так как он проверяет чётность и может быть вычислен на основание прочих бит;
• Выбрать число v =< p;
• Сгенерировать массив вспомогательных векторов h. Состоящий из векторов длинной p, со всевозможной комбинаций битов со значением 1, количество которых в одном векторе должно быть не больше v, и битов со значением 0 на остальных позициях (см. пример ниже);
• Сгенерировать массив проверочных векторов e. По следующим правилам:
  
  • Каждый вектор должен быть на один бит короче вектора r;
  • Массив векторов должен быть такой же длины, как и массив вспомогательных векторов, сгенерированный, на предыдущем шаге;
  • Каждый вектор должен состоять из нулевых бит, кроме позиций наименее надежных бит, выбранных на первом шаге. На данных позициях должны располагаться биты из массива вспомогательных векторов h.

Теперь сгенерируем проверочные вектора на примере нашего вектора r = [-1.02, -1.1, -2, 1.95, 0.98, -2.34, 0.73, 1.97].

• Пусть p = 3, тогда позиции наименее надежных бит — [1, 5, 7] (нумеруем начиная с индекса 1), [-1.02, -1.1, -2, 1.95, 0.98, -2.34, 0.73, 1.97];
• Пусть v = 2;
• Сгенерируем массив вспомогательных векторов h:
  h[1] = [0, 0, 0],
  h[2] = [0, 0, 1],
  h[3] = [0, 1, 0],
  h[4] = [0, 1, 0],
  h[5] = [1, 0, 0],
  h[6] = [1, 0, 1],
  h[7] = [1, 1, 0];
• Сгенерируем массив проверочных символов e:
  e[1] = [0, 0, 0, 0, 0, 0, 0], используем на позициях 1, 5 и 7 элементы из вектора h[1] на позициях 0, 1 и 2 соответственно,
  e[2] = [0, 0, 0, 0, 0, 0, 1], используем на позициях 1, 5 и 7 элементы из вектора h[2] на позициях 0, 1 и 2 соответственно,
  e[3] = [0, 0, 0, 0, 1, 0, 0], используем на позициях 1, 5 и 7 элементы из вектора h[3] на позициях 0, 1 и 2 соответственно,
  e[4] = [0, 0, 0, 0, 1, 0, 0], используем на позициях 1, 5 и 7 элементы из вектора h[4] на позициях 0, 1 и 2 соответственно,
  e[5] = [1, 0, 0, 0, 0, 0, 0], используем на позициях 1, 5 и 7 элементы из вектора h[5] на позициях 0, 1 и 2 соответственно,
  e[6] = [1, 0, 0, 0, 0, 0, 1], используем на позициях 1, 5 и 7 элементы из вектора h[6] на позициях 0, 1 и 2 соответственно,
  e[7] = [1, 0, 0, 0, 1, 0, 0], используем на позициях 1, 5 и 7 элементы из вектора h[7] на позициях 0, 1 и 2 соответственно;

6. Проводим демодуляцию вектора r и получаем вектор y. y[i] = r[i] > 0, то 1, иначе 0; И отбрасываем последний бит.
y = [0, 0, 0, 1, 1, 0, 1].

7. Генерируем массив пробных последовательностей t. t[i] = y ⊕ e[i].
Получаем:
t[1] = [0, 0, 0, 1, 1, 0, 1] — y ⊕ e[1],
t[2] = [0, 0, 0, 1, 1, 0, 0] — y ⊕ e[2],
t[3] = [0, 0, 0, 1, 0, 0, 1] — y ⊕ e[3],
t[4] = [0, 0, 0, 1, 0, 0, 0] — y ⊕ e[4],
t[5] = [1, 0, 0, 1, 1, 0, 1] — y ⊕ e[5],
t[6] = [1, 0, 0, 1, 1, 0, 0] — y ⊕ e[6],
t[7] = [1, 0, 0, 1, 0, 0, 1] — y ⊕ e[7];

Это позволяет нам проверить наименее надежные биты. А именно, проинвертировать их, в зависимости от значений вектора e[i] и далее выбрать то значение, которое нам больше будет подходить(см. следующие шаги).
Надежные биты данными операциями затронуты не будут.
Если бы мы использовали только жесткие решения, то не могли бы сделать вывод о том какие биты наименее надежны и проверить их.

8. Применяем к t[i] жесткое решение (в данном случаем алгоритм Хэмминга), но оставляем проверочные символы, и получаем массив векторов s:
s[1] = [0, 0, 0, 1, 1, 1, 1], жесткое решение для t[1],
s[2] = [1, 0, 0, 1, 1, 0, 0], жесткое решение для t[2],
s[3] = [0, 0, 1, 1, 0, 0, 1], жесткое решение для t[3],
s[4] = [0, 0, 0, 0, 0, 0, 0], жесткое решение для t[4],
s[5] = [1, 0, 0, 1, 1, 0, 0], жесткое решение для t[5],
s[6] = [1, 0, 0, 1, 1, 0, 0], жесткое решение для t[6],
s[7] = [1, 1, 0, 1, 0, 0, 1], жесткое решение для t[7];

9. Добавляем векторам s[i] проверку на чётность:
s[1] = [0, 0, 0, 1, 1, 1, 1, 0],
s[2] = [1, 0, 0, 1, 1, 0, 0, 1],
s[3] = [0, 0, 1, 1, 0, 0, 1, 1],
s[4] = [0, 0, 0, 0, 0, 0, 0, 0],
s[5] = [1, 0, 0, 1, 1, 0, 0, 1],
s[6] = [1, 0, 0, 1, 1, 0, 0, 1],
s[7] = [1, 1, 0, 1, 0, 0, 1, 0];

10. Проведём модуляцию значений векторов из массива s. По формуле s[i][j] = 2 * s[i][j] — 1:
s[1] = [-1, -1, -1, 1, 1, 1, 1, -1],
s[2] = [1, -1, -1, 1, 1, -1, -1, 1],
s[3] = [-1, -1, 1, 1, -1, -1, 1, 1],
s[4] = [-1, -1, -1, -1, -1, -1, -1, -1],
s[5] = [1, -1, -1, 1, 1, -1, -1, 1],
s[6] = [1, -1, -1, 1, 1, -1, -1, 1],
s[7] = [1, 1, -1, 1, -1, -1, 1, -1];

11. Найдём ближайший к вектору r, вектор из массива s. Используя в качестве метрики евклидово расстояние.
evkl(s[1], r) = 17.03, для s[1]
evkl(s[1], r) = 14.66, для s[2]
evkl(s[1], r) = 19.58, для s[3]
evkl(s[1], r) = 22.30, для s[4]
evkl(s[1], r) = 14.66, для s[5]
evkl(s[1], r) = 14.66, для s[6]
evkl(s[1], r) = 20.06, для s[7]

У нас получилось несколько одинаковых метрик. Выбрать мы можем любой из векторов s. Давайте выберем первый их них, то есть s[2] = [1, -1, -1, 1, 1, -1, -1, 1].

12. Проведём демодуляцию s[2] и получим вектор res. res[i] = s[2][i] > 0, то 1, иначе 0.
res = [1, 0, 0, 1, 1, 0, 0, 1].

13. Отбросим у вектора res проверочные символы и получим оригинальный вектор u = [1, 0, 0, 1], который и требовалось передать.

О помехах

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

Эпилог

Писал, на Хабре в первый раз. Если кому то будет интересно, то в будущем хотел бы освятить алгоритм Витерби, пороговые декодеры, возможно, турбо-коды. Буду благодарен за конструктивные замечания.

Литература

По данной теме советую — «Кодирование с исправлением ошибок в системах цифровой связи. Дж. Кларк, Дж. Кейн».