Вхой

Вызвать БЧХ- Векойер вля. аекойиробания столоца j

Неуйача при йекойировйниа

Установить метку стирания на j-м столбце

Успешное Векойирование

W-число исправленных ошибок

HttiJmu d*~\-p значений инйекса/, йля которых О)/ принимают наибольшие эночения, и угоряЗочить их в поряВке убывания o)j

Если p нечетно, mo

±

Установить метку стирания в позициях синВексами j\,...,jp

Вызвать исправляющий ошибки и стирания БЧХ-б8ковер йля йекойирования t-u строки

Неуйача при Векойировании

arS-lwi/d

у Л 1,если нет ошиБии, 1-1, если есть ошибка

Стоп

Рис. 10.2. Декодер для кода-произведепия кодов БЧХ.

Идея доказательства состоит в том, что ц принадлежит выпуклой оболочке множества векторов Пусть

К = 1

откуда следует, что О Л; <: 1 и I"Loh = 1. Кроме того.

Предположим (еперь, что для всех /

Тогда

/=0 (=0 /=0 1=0

что противоречит предположению теоремы. Следовательно, теорема доказана. □ Изображенный на рис 10.2 декодер основан на двух предыдущих теоремах. Если при декодировании t-й строки некоторые столбцы уже стерты, то используется та же самая процедура декодирования, но без учета стертых столбцов и при уменьшении d на число стертых столбцов. Далее, если при декодировании i-u строки некоторые столбцы были стерты или отмечены как содержащие ошибку, то при декодировании всех последующих строк они остаются стертыми. В случае когда необходимо стереть только один столбец, декодер всегда стирает два, так что число стертых столбцов всегда четно. Это не уменьшает корректирующих способностей процедуры, но сводит число необходимых итераций не более чем к «2 + (dl - 1)/2.

10.4. МНОГОМЕРНЫЕ СПЕКТРЫ

Двумерные таблицы, размеры которых согласуются с длиной преобразования, можно исследовать с помощью двумерного преобразования Фурье. Пусть \vcc} - двумерная (п X п)-таблица над GF (q), которую назовем двумерным сигналом, пусть для некоторого т длина п делит q" - 1, и пусть а - элемент порядка п из поля GF {q"). Таблицу с элементами

п-1 п-1

10.4. МНОГОМЕРНЫЕ СПЕКТРЫ 339

тзовем двумерным спектром, а индексы /и / -частотными переменными. Используя одномерное обратное преобразование, очевидно, получаем

у,- г = (1/п) (1/п) а-ча--гУц:

/=0/=0

На рис. 10.3 приведены два двумерных спектра над GF (8). В каждом квадрате сетки записан восьмеричный символ.

Чтобы задать контролирующий ошибки код, выберем множество т N - К компонент в качестве (двумерных) проверочных частот и положим их равными нулю, как на рис. 10.3. Остальные К компонент будут информационными символами, принимающими значения в поле GF {q"), а в качестве кодового слова, соответствующего данным информационным символам,-выберем результат обратного двумерного преобразования Фурье. Построенный так код, очевидно, является линейным, но, вообще говоря, не циклическим.

Если искомый код лежит в подполе поля GF (q") (в рассматриваемом примере единственным подполем поля GF (8) является поле GF (2)), то необходимо взять ограничение кода, выбирая только те кодовые слова, все компоненты которых принадлежат этому под-полю, и тем самым получая двумерный подкод над подполем. Можно также построить двумерные альтернантные коды, если перед ограничением на подполе умножить кодовое слово на двумерный шаблон.

Двумерные спектры не обязательно должны быть квадратными, но если это так и если п -{- I = q", то наибольшим рассматриваемым полем является GF {п + I). В случае когда спектр задается (щ X П2)-таблицей (п Ф щ), приходится работать в наименьшем поле GF ((?") при некотором т, таком, что и «1 и «2 делят

- 1. Пусть {Vii-} --двумерный сигнал размера X п, и

Рис. 10.3. Двумерный спектр над Cf (8). а - спектр без ограничений; б-спектр с ограничениями.