Кодирование факсимильных изображений. Коды кдс-1, кдс-2, кдс-3

Факсимильная связь – это вид электросвязи, обеспечивающий передачу и воспроизведение неподвижных изображений. Средствами факсимильной связи одинаково удобно передавать текст, черно-белые и цветные фотографии, чертежи. Для кодирования подобных сообщений могут использоваться неравномерные коды. Однако, техническая сложность алгоритмов обработки сигнала, связанная с применением неравномерных кодов, ограничивает возможности этих кодов. В существующих устройствах сжатия сообщений чаще используются методы, реализующие неравномерные коды. К таким методам относятся коды КДС-1, КДС-2, КДС-3, модифицированный код Хаффмана. Термин КДС (кодирование длин серий) является общим названием ряда алгоритмов сжатого описания цифрового видеосигнала двухградационных изображений, представленного в виде последовательности из нулей и единиц.

Рассмотрим метод КДС-1. Отличительной особенностью метода является разбиение последовательности элементов строки изображения на блоки по 4 элемента в каждом. Кодирование начинается с отрезка любого цвета, причем кодируются изображения не отдельных элементов, а их группы, состоящие из 4 элементов.

Для представления длины отрезка используются шестиразрядные слова.

Разряды В6, В5 определяют, какая это группа: 00 – группа белого, 01 – группы черного, 10 – некодируемые группы (содержат и белый, и черный цвета), 11 – сигналы управления.

Если группа некодируемая, то биты В1-В4 указывают, какие цвета входят в группу: 0 – белый цвет, 1 – черный.

Если группа белая или черная, то биты В1-В4 указывают количество подряд идущих групп в двоичной системе счисления.

Пример: Первая группа является некодируемой, следовательно, биты В6В5 имеют значение 10. В группу входят 3 белых элемента и один черный, следовательно, биты В4-В1 принимают значение 0001.

Вторая группа также является некодируемой, следовательно, В6В5=10. В группу входят черный, белый, черный и белый элементы, следовательно, биты В4-В1 принимают значение 1010.

Третья группа чисто белого цвета, следовательно, В6В5=00, а биты В4-В1 принимают значение 0001, т.к. белая группа одна и т.д.

Основные параметры помехоустойчивых кодов

Помехоустойчивое кодирование– процесс введения избыточной информации в передаваемое информационное сообщение. В сформированной кодовой последовательности должны быть информационные символы и некоторые дополнительные (проверочные) символы, т.е. помехоустойчивое кодирование является избыточным.

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

Помехоустойчивый код характеризуют следующими параметрами:

1. Основание кода q – число элементарных символов, выбранных для пе­редачи сообщений. Например, для двоичного и троичного кода q₂={0;1}, q₃={-1;0;1}.

2. Длина кода n – число символов, выбранных для передачи сообщений.

3. Число информационных позиций в коде, выбранных для передачи дан­ных – k.

4. Число проверочных (контрольных) позиций в коде – l=n-k.

5. К_общ=2ⁿ – общее количество кодовых последовательностей,

К_раз=2^к – количество разрешенных кодовых последовательностей,

К_запр=2¹ – количество запрещенных кодовых последовательностей.

6. Скорость передачи кода R=k/n характеризует качество кода.

7. Относительная избыточность кода r=(n-k)/n*100%=(1-R)*100%

Абсолютная избыточность кода l=n-k

8. Вес кодовой последовательности w – количество ненулевых значений позиций кодовой комбинации F(x). Например, F(x)=011101101  w=6 двоичных символов.

9. Кодовое расстояние кода d характеризует возможности кода по контролю ошибок, равно количеству несовпадений в кодовых последовательностях.

F₁(x)=0111011101

 F₂(x)=1011010010

d =11 1111=6

Хэмминг доказал, что не максимальное, а минимальное кодовое расстояние характеризует корректирующие свойства помехоустойчивого кода. Минимальное кодовое расстояние обозначается как d₀ илиd_x (хэмминговое расстояние) и равно наименьшему значениюd из всей их совокупности.C позиции теории кодирования d_xпоказывает, сколько символов в кодовой последовательности надо исказить, чтобы перевести ее в другую кодовую последовательность.

Определены как нижние, так и верхние границы значений d_x:

- нижние границы устанавливают факт существования помехоустойчивых кодов с таким значениемd_x;

- верхние границы определяют максимальное теоретическое значение d_x.

Нижняя граница Хэммингаопределяется по формуле:

l ≥log₂(1+n+C_n²+…+C_n^tиспр) 2^l ≥ 1+n+C_n²+…+C_n^tиспр

10. Кратность контролируемой ошибки t (t_обн или t_испр).

d₀=2t_испр+1  t_испр=(d₀-1)/2 – количество ошибочных символов, которое может исправить помехоустойчивый код,

d₀=t_обн+1  t_обн=d₀-1 – количество ошибочных символов, которое может обнаружить помехоустойчивый код.

Для того, чтобы помехоустойчивый код исправлял tиспр ошибок и обнаруживал to6н ошибок необходимо, чтобы d0≥tиспр + tобн +1

11. Вероятность ошибки декодирования

n

Р_ош.дек.=С_nⁱP_kⁱ(1-P_k)^n-I,

i=t_испр.

– число сочетаний,P_k – вероятность ошибки в канале связи.

На практике коды, как правило, обозначают (n;k) или (n;k;d). Например, обозначение (7;4) или (7;4;3) характеризует блоковый код Хэмминга длиной n=7, числом информационных позиций k=4, кодовым расстоянием d=3.