- PVSM.RU - https://www.pvsm.ru -
Друзья, всем привет! Недавно начал изучать помехоустойчивые коды и моделировать процесс их работы, и понял что по-человечески написанных топиков по этой теме совсем немного, а точнее мало. Мудрёные книги есть, но на то они и мудрёные, что на их изучение нужно время, а порой нужно получить какие-то базовые знания и представления по теме, за совсем сжатый промежуток времени. Как пример, могу привести статью по кодам Хэмминга [1], она мне здорово помогла, когда я только начинал возиться с кодами. Так же доступно подобные коды описаны здесь [2].
Мой топик нацелен в первую очередь на практиков. Тех кому интересно применить подобные алгоритмы и получить небольшое работающее приложение за приемлемый промежуток времени.
Так же хотелось бы уточнить, что алгоритм Чейза является классическим примером помехоустойчивого кодирования, и в одиночку мало где сейчас используется. Но для понимания вопросов кодирования и обучения, он подходит на все сто, а может и двести процентов.
На сегодня известно много различных классов помехоустойчивых кодов, отличающихся друг от друга структурой, назначением, эффективностью, алгоритмом кодирования/декодирования и прочим.
При одном подходе, коды можно разбить на две группы: блоковые, в которых кодирование и декодирование производится в пределах единого блока битов и древовидные, в которых обработка происходит непрерывно, без разделения сообщения на блоки.
Декодирование блокового кода может быть осуществлено посредством жёсткого или мягкого принятия решения. В декодировании с жёстким принятием решения, каждому принимаемому биту в демодуляторе приписывается значение
0 или 1. Декодер с мягким принятием решения принимает не только бинарную величину 1 или 0, но также доверительную величину, связанную с заданным битом. Декодер будет использовать эту мягкую информацию, и на выходе мы получим такое же жёсткое решение.
Если кратко, то на вход жесткого декодера, из канала, поступает вектор из значение 0 или 1. На вход мягкого декодера поступает вектор из значений (-∞; +∞). Использование мягких решений даёт больше возможностей, так как предоставляет более широкий маневр по исправлению возникающих помех.
Алгоритм Чейза — блоковый код с мягким решением.
Алгоритм Чейза — это понятный и относительно эффективный алгоритм исправления ошибок(помех) в передаваемом сообщение. Главной идеей алгоритма является генерирование массива кодовых слов, которые будет содержать слово, ближайшее к принятой последовательности. Алгоритм основан на том, что если слово, декодированное обычным жёстким решением содержит ошибку, то одно из «ближайших» к нему кодовых слов скорее всего совпадает с переданным.
Декодер Чейза в своей работе использует жесткий декодер. Давайте использовать уже упомянутый декодер Хэмминга. Ещё раз напоминаю, что его описание можно найти здесь [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 = [-1.02, -1.1, -2, 1.95, 0.98, -2.34, 0.73, 1.97].
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], который и требовалось передать.
Друзья, хотел бы отметить, что процесс внесения(и моделирование этого процесса) помех в сообщения (описанный в начале топика) заслуживает отдельного поста. И я не хотел раздувать топик данной полезной, но в данном контексте лишней информацией.
Писал, на Хабре в первый раз. Если кому то будет интересно, то в будущем хотел бы освятить алгоритм Витерби, пороговые декодеры, возможно, турбо-коды. Буду благодарен за конструктивные замечания.
По данной теме советую — «Кодирование с исправлением ошибок в системах цифровой связи. Дж. Кларк, Дж. Кейн».
Автор: rznELVIS
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/52686
Ссылки в тексте:
[1] кодам Хэмминга: http://habrahabr.ru/post/140611/
[2] здесь: http://habrahabr.ru/post/111336/
[3] Источник: http://habrahabr.ru/post/208876/
Нажмите здесь для печати.