: архив : архив журнала "625" : 1997 : #8

Цифровая видеотехника: кодирование, обнаруживающее и исправляющее ошибки
Константин Гласман

Принципы обнаружения и исправления ошибок

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

Аналогичные выводы можно сделать и применительно к цифровой видеозаписи. Цифровой видеомагнитофон не должен иметь расход ленты, превышающий расход в аналоговом аппарате. Плотность записи, которую приходится при этом использовать, столь высока, что отношение сигнала к шуму невысоко и ошибок в канале записи-воспроизведения избежать просто невозможно. Надо также иметь в виду, что проявление ошибок в цифровой системе существенно отличается от заметности флуктуационного шума в аналоговой. Ошибка в одном двоичном разряде может изменить значение отсчета изображения многократно, если она произошла в старшем разряде кодового слова. Даже несколько белых или черных точек на изображении могут оказаться заметными (рис.1). Вероятность ошибки в одном разряде может составлять, например, 10-4..10-5. Это означает, что, при скоростях цифрового потока данных 150-200 Мбит/с, каждую секунду будут происходить тысячи ошибок. Качество такого изображения будет неудовлетворительным.

Все способы кодирования, позволяющие обнаруживать и исправлять ошибки, предполагают введение избыточности. Например, двоичный код с одним дополнительным проверочным разрядом четности, доводящим количество единиц в кодовом слове (включая проверочный разряд) до четного числа, позволяет обнаруживать одну ошибку (рис.2). Для этого надо на приемной стороне (или при воспроизведении сигнала) сосчитать число единиц в кодовом слове. Если оно не является четным, то в канале произошла ошибка (рис.3).

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

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

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

Коды Рида-Соломона

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

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

Если кодируемая информация i описывается набором (блоком) из k символов, то этому набору, или слову можно поставить в соответствие информационный многочлен

i(x)=ik-1xk-1+ik-2xk-2+...+i1x1+i0.

Так как цель кодирования - исправление ошибок, достигаемое благодаря введению избыточности, то каждому информационному слову должно соответствовать кодовое слово c=(cn-1, cn-2, ..., c1, c0) большей длины с добавленной избыточностью в виде дополнительных символов. Это кодовое слово также можно записать в виде многочлена

c(x)=cn-1xn-1+cn-2xn-2+...+c1x+c0.

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

g(x)=gn-kxn-k+gn-k-1xn-k-1+...+g1x+g0.

Процедура нахождения кодового слова заключается в умножении информационного многочлена на порождающий многочлен кода. Таким образом, отличительной особенностью всех кодовых слов является то, что они получены умножением разных информационных многочленов на один и тот же порождающий многочлен. Следовательно, они все делятся на порождающий многочлен без остатка. Это обстоятельство дает ключ к декодированию, позволяющему обнаруживать и исправлять ошибки, возникшие при передаче данных. Слова, которые не делятся без остатка на порождающий многочлен, не являются кодовыми и, следовательно, содержат ошибки. Теория кодов Рида-Соломона показывает, что если цель кодирования - исправить t ошибок в кодовом слове, то степень порождающего многочлена (n-k)=2t. Следовательно, кодовое слово должно содержать два дополнительных символа на одну исправляемую ошибку. Для создания нового кода с заданными свойствами надо образовать соответствующий порождающий многочлен.

Передаваемый по каналу связи или записываемый на магнитный носитель кодовый блок может претерпеть искажения, например, из-за шумов. Это можно в общем виде описать добавлением к кодовому блоку набора ошибок e, которому соответствует многочлен e(x)=en-1xn-1+en-2xn-2+...+e1x+e0. Принятому или воспроизведенному набору символов соответствует таким образом многочлен v(x)=c(x)+e(x). Найдя остаток от деления принятого многочлена v(x) на порождающий g(x), можно понять, были ли на самом деле ошибки. Если остаток равен нулю, значит принятое слово является кодовым и ошибок не было. Если остаток не равен нулю, то при передаче были ошибки. Остаток от деления дает многочлен, зависящий только от многочлена ошибки. Его называют синдромным многочленом. Cиндром - это совокупность симптомов, характеризующих заболевание. Синдромный многочлен s(x) зависит только от конфигурации ошибок, т.е. является синдромом, или описанием ошибок. Если число ошибок не превышает заданный предел t, то между e(x) и s(x) существует однозначное соответствие и с помощью определенных вычислений можно найти коэффициенты многочлена ошибок по синдромному многочлену. Таким образом можно восстановить переданный кодовый многочлен: c(x)=v(x)-e(x). Разделив c(x) на g(x), можно найти и информационный многочлен.

Помимо кодирования по правилу c(x)=i(x)g(x) существует так называемое систематическое правило кодирования, при котором k старших коэффициентов кодового слова устанавливаются равными коэффициентам информационного многочлена:

c(x)=ik-1xn-1+ik-2xn-2+...+i0 xn-k+

pn-k-1xn-k-1+...+p1x+p0.

(n-k) младших коэффициентов кодового слова p, часто называемых проверочными, подбираются такими, чтобы c(x) делился бы на g(x) без остатка. Это будет так, если соответствующий проверочный многочлен p(x)=pn-k-1xn-k-1+...+p1x+p0 рассчитывается как p(x)=-R[(xn-ki(x)):g(x)]. Систематическое правило кодирования дает кодовые слова, более удобные на практике, т.к. информационные слова в явном виде размещаются в k старших разрядах кодовых слов. Итак, если набор из символов образует блок информации i, кодируемой с целью обнаружения и исправления ошибок, то кодирование означает формирование блока c, который приобрел некоторую избыточность в виде дополнительных проверочных символов p. Эта избыточность имеет строго дозированную величину в соответствии с заданной степенью помехозащищенности (числом допустимых ошибок t). Промежуточные вычисления выполняются по правилам действий с многочленами.

Декодирование принятого или воспроизведенного набора предполагает следующие действия:

- нахождение синдромного многочлена;

- вычисление многочлена ошибок s(x) по найденному синдромному многочлену (ошибки нет, если s(x)=0);

- восстановление переданного кодового многочлена;

- определение переданного блока информации по старшим коэффициентам восстановленного кодового многочлена.

В описанных выше процедурах блоки символов передаваемой и принимаемой информации представляют собой наборы значений некоторых сигналов. В видеотехнических приложениях вычисления должны выполняться над символами, которыми являются отсчеты видеосигнала. При 8 разрядах на отсчет символы образованы числами в диапазоне от 0 до 255, при 10 разрядах на отсчет определены 1024 символа в виде чисел от 0 до 1023. Таким образом, информационные слова представляют собой блоки из числовых значений отсчетов видеосигнала. Кодирование предполагает вычисления по правилам действий над многочленами, с коэффициентами которых надо выполнять действия сложения, вычитания, умножения и деления, причем эти вычисления не должны сопровождаться какими-либо округлениями промежуточных результатов (даже при делении), чтобы не вносить неопределенность. Поскольку это невозможно, то все вычисления надо делать так, чтобы и промежуточные, и конечные результаты не выходили за пределы этих множеств из 256 или 1024 чисел. Для этого надо использовать особую алгебру, правила вычислений которой отличаются от общеизвестных. Множества символов, для которых существует такая алгебра, называют полями Галуа.

Простейшее поле Галуа содержит 2 символа, которые можно складывать, вычитать, умножать и делить по следующим правилам: 0+0=0, 0+1=1, 1+1=0, 0-0=0, 1-1=0, 1-0=1, 0-1=1, 0*1=0, 1*1=1, 0/1=0, 1/1=1. Множество символов образует поле Галуа только в том случае, если число элементов равно целой степени простого числа. Для множеств из 256 и 1024 символов поля Галуа существуют. Они и их арифметика могут быть построены из простого поля из 2 элементов с помощью специальных многочленов. Формулы многочленов, порождающих поля Галуа, являются важной составной частью стандартов, описывающих системы защиты от ошибок, например, в цифровых видеомагнитофонах. Разумеется, в стандартах приводятся также описания порождающих многочленов кода и другие данные, относящиеся к кодированию. Современная микроэлектроника позволяет создавать интегральные схемы, способные выполнять описанные выше достаточно сложные вычисления, что создает условия для широкого применения мощных алгоритмов кодирования, исправляющего ошибки, при передаче и записи сигналов в цифровых видеосистемах.

Кодирование в цифровой видеозаписи

Кодирование, позволяющее бороться с ошибками, достигло высшего для телевидения и видеотехники уровня в цифровой видеозаписи. Цифровая видеозапись предъявляет к системе кодирования специфические требования, связанные с наличием выпадений сигнала. Система кодирования должна исправлять как случайные ошибки, так и пакетные ошибки длиной до десятков тысяч символов, обусловленные выпадениями. Для исправления таких больших пакетных ошибок надо использовать кодовые слова очень большой длины, что на практике бывает не совсем удобным, например, из-за ограничений, налагаемых необходимостью монтажа. Проблема решается за счет использования кодов-произведений (рис.7). По существу это представляет собой раздельное кодирование столбцов и строк прямоугольной матрицы, представляющей собой массив цифровых данных. К столбцам матрицы добавляются проверочные символы одного кода, называемого внешним (n1, k1), а к строкам - проверочные символы другого кода, называемого внутренним (n2, k2). Такое двумерное кодирование существенно увеличивает мощность кода. Как было показано в приведенном выше примере (рис.5), с помощью двумерного кодирования с одной проверкой четности, каждый из которых позволяет только обнаруживать сам факт ошибки в кодовом слове, можно найти позицию ошибки и исправить ее.

Еще более замечательна способность кодов-произведений исправлять пакетные ошибки, т.е. ошибки значительной длины. Это достигается благодаря использованию буферной памяти между внешним и внутренними кодерами и чередованию направлений записи в память и чтения из нее (рис.8). При записи память заполняется по столбцам, к которым добавляются проверочные символы внешнего кода. Затем содержимое памяти построчно записывается на магнитную ленту вместе с добавляемыми проверочными символами внутреннего кода. При воспроизведении чередование направлений записи и чтения из буферной памяти является обратным. В результате такого чередования направлений записи и чтения из буферной памяти (перемежения) пакетная ошибка, длина которой равна нескольким строкам буферной памяти, распределяется маленькими порциями в разных кодовых словах внешнего (вертикального) кода и может быть исправлена при сравнительно небольшой его мощности. Внешний код, способный исправлять всего одну ошибку в одном кодовом слове, может исправить пакетную ошибку длиной до целой строки буферной памяти (рис.9).

Таким образом, размер буферной памяти кодера-декодера является важнейшим параметром, позволяющим сравнивать потенциальные возможности различных форматов видеозаписи. Чем больше размер памяти, тем больше возможности исправления пакетных ошибок, обусловленных выпадениями сигнала. Но в видеозаписи есть еще одно требование. Для работы с нестандартными скоростями воспроизведения размер слов и памяти должен быть сравнительно небольшим (кодовое слово внутреннего кода определяет минимальную порцию информации, которая должна считываться при любой нестандартной скорости воспроизведения). Эти два противоречивых требования удается выполнить, разбивая матрицу памяти кодера-декодера на подматрицы. Кодовое слово внутреннего кода определяется горизонтальным размером подматрицы, проверочные символы внутреннего кода добавляются к строкам матрицы частями. Одновременно достигается оптимальная стратегия борьбы со случайными и пакетными ошибками. Внутреннее кодирование позволяет обнаруживать и исправлять ошибки случайного характера, имеющие сравнительно небольшую длину. Внешнее кодирование оптимизируется для устранения пакетных ошибок, вызванных выпадениями.

Интегральными показателями, определяющими потенциальную возможность формата цифровой видеозаписи исправлять ошибки, являются, таким образом, размеры подматрицы буферной памяти и количество таких подматриц. Для классического аппарата D-1 эти показатели определяются величинами: 10 подматриц с размерами 30 информационных + 2 проверочных символа = 32 символа по вертикали и 60+4=64 по горизонтали (рис.10). Внутреннее кодирование может исправлять до двух ошибок в пределах кодового слова из 64 символов. Можно использовать возможности внутреннего кода и для обнаружения ошибок, которые будут затем исправлены системой внешнего кода.

Внешнее кодирование позволяет исправлять одну ошибку в каждом слове внешнего кода из 32 символов. Само по себе внешнее кодирование, исправляющее одну ошибку в каждом слове, может исправить полную строку матрицы, содержащую 600 символов. Если использовать способность внутреннего кода обнаруживать ошибки, то величина исправленной пакетной ошибки увеличится еще в два раза. Эти показатели означают, что в аппарате формата D-1 исправляется пакетная ошибка из-за пятимиллиметровой царапины вдоль дорожки или царапины шириной 0,5 мм вдоль ленты. Форматы видеозаписи, появившиеся после D-1, используют еще более мощные системы кодирования.

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

Для повышения эффективности интерполяции используется перемешивание отсчетов изображения перед записью на магнитную ленту (конечно, при воспроизведении восстанавливается исходный порядок следования отсчетов изображения). При этом дистанция перемешивания, т.е. размеры области изображения, в пределах которой перемешиваются отсчеты изображения, имеет важное значение при сопоставлении форматов. В современных цифровых видеомагнитофонах дистанция перемешивания определяется размерами буферной памяти в системе кодирования. Выпадение, не исправленное системой защиты от ошибок, будет выглядеть сплошной полосой в отсутствии перемешивания (рис.11). Возможности маскирования в этом случае невелики (например, можно повторить сигнал последней строки, как это делается в компенсаторах выпадений аналоговых видеомагнитофонов. В аппарате D-1 дистанция перемешивания - 50 строк одного поля. В пределах этих 50 строк и распределяются пораженные выпадениями отсчеты благодаря перемешиванию. Так как каждый ошибочный отсчет окружен в этом случае верными, не пораженными выпадением отсчетами изображения, то он может быть восстановлен с использованием методов интерполяции, например, путем замены ошибочного значения на среднее арифметическое величин соседних верных отсчетов. Надо отметить, что даже если искаженные выпадением отсчеты не заменяются на значения, вычисленные путем интерполяции, то они представляют собой точки помех, распределенные по сравнительно большой области изображения, вместо сплошной полосы, т.е. перемешивание само по себе снижает субъективную заметность ошибок.

Кодирование в современной цифровой видеозаписи, позволяющее обнаруживать и исправлять ошибки, являет собой пример гармонично сочетающегося со структурой телевизионного изображения и эффективного метода решения сложной научно-технической задачи.