Декодирование на основе таблицы декодирования.

Декодирование (реализация вышеупомянутого преобразования ψ) может производиться различными способами. Простейшим и самым наглядным является его реализация с помощью таблицы декодирования. Рассмотрим две ситуации.

1. Пусть нам удалось так построить алгоритм кодирования, что каждую кодовую точку можно было окружить шаром радиуса t так, чтобы эти шары не пересекались.Тогда Таблица декодирования строится следующим образом. Первая строка таблицы – все кодовые вектора. В столбце под кодовым вектором лежат все вектора Bⁿ, расположенные в шаре радиуса tс центром в этом кодовом векторе.Все оставшиеся вектора Bⁿ размещаются по столбцамтаблицы согласно какому-то эвристическому правилу. (Например: a) все в первый столбец; b) все случайным образом; c) в столбец с ближайшим кодовым словом, а, если их несколько, то в с ближайшему кодовому вектору, а в случае равноудаленности от нескольких кодовых векторов – к тому, номер столбца которого наименьший. И т.п.)Декодирование осуществляется следующим образом: полученный вектор преобразуется в первый вектор столбца, в котором он расположен.

2. Пусть нам не удалось так построить алгоритм кодирования, что каждую кодовую точку можно было окружить шаром радиуса t так, чтобы эти шары не пересекались. Тогда Таблица декодирования строится следующим образом. Первая строка таблицы – все кодовые вектора. Все вектора Bⁿ размещаются по столбцамтаблицы согласно какому-то эвристическому правилу. (Например: a) все в первый столбец; b) все случайным образом; c) в столбец с ближайшим кодовым словом, а, если их несколько, то в с ближайшему кодовому вектору, а в случае равноудаленности от нескольких кодовых векторов – к тому, номер столбца которого наименьший. И т.п.) Декодирование осуществляется следующим образом: полученный вектор преобразуется в первый вектор столбца, в котором он расположен.

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

Пример:

C: a = 11 → x ¹ = 11 000

b = 00 → x ² = 00 110

c = 10 → x ³ = 10 011

d = 01 → x ⁴ = 01 101

Таблица декодирования.

11001	00111	10010	01100
11010	00100	10001	01111
11100	00010	10111	01001
10000	01110	11011	00101
01000	10110	00011	11101

Источник Кодер B ⁵

a x ¹

b x ² → канал

c x ³ C –(5,4,3)-код

d x ⁴

Всего в таблице декодирования |B ⁵| = 32 вектора. В каждом столбце находятся все пять векторов, которые расположены на расстоянии ρ=1 от кодового вектора (это первый вектор данного столбца). Кроме того, в каждом столбце находится по два вектора, которые расположены на расстоянии ρ=2 от двух кодовых векторов.

Получается, что в нашей схеме декодирования кодовые вектора окружены шарами единичного радиуса.

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