ГОСТ Р ИСО/МЭК 24778 — 2010
Приложение В
(обязательное)
Обнаружение и исправление ошибок
Кодовые слова исправления ошибок в символах Aztec Code вычисляют с использованием схемы помехо
устойчивого кодирования Рида-Соломона. Размер всех кодовых слое равен В битам, а полиномиальные арифме
тические операции над полем GF(2B) проводят с использованием поразрядных арифметических операций по
модулю 2 и арифметических операций по модулю Р над кодовыми словами (где Р — эквивалентное значение
примитивного многочлена). Значения В и Р для служебного сообщения определяют в соответствии с 7.2.3, а для
данных сообщения — в соответствии с 7.3.2.
В.1 Построение кодовых слов исправления ошибок
Кодовые слова исправления ошибок представляют собой остаток после операций умножения многочлена,
образованного из «nd» кодовых слов данных, на хк с последующим длинным делением на порождающий много
член порядка «пс». Нецелесообразно хранить списки всех возможных порождающих многочленов, используе
мых с данными сообщениями в Aztec Code. Вместо этого они генерируются непосредственно соответствующим
программным обеспечением.
Функции языка С. представленные на рисунке В.1. обеспечивают необходимое кодирование. Функция
ReedSotmon(), которая работает с «nd» значениями кодовых слов данных, хранящимися в целочисленном масси ве
wd[], генерирует логарифмические и антилогарифмические таблицы для поля Галуа размером «gf» с простым
модулем «рр». затем использует их в функции prod() — сначала для вычисления коэффициентов порождающего
многочлена порядка «пс». затем — для вычисления «пс» дополнительных контрольных кодовых слов, размеща
емых после данных в wd{). Функция ReedSotomonf) работает не только с данными сообщениями, но и со служеб
ными сообщениями.
В.2 Возможность исправления ошибок
Кодовые слова исправления ошибок могут исправлять два типа ошибок — стирания (ошибочные кодовые
слова в известных позициях) и ошибки (ошибочные кодовые слова в неизвестных позициях). Стирание представ
ляет собой неотсканироеанный или недекодируемый знак символа, а ошибка — неверно декодированный знак
символа. Число исправляемых стираний и ошибок вычисляют по следующей формуле
е + 2t < d - р.
где е — число стираний;
t — число ошибок;
d — число кодовых слов исправления ошибок;
р — число кодовых слов исправления ошибок, зарезервированных для обнаружения ошибок.
Для служебных сообщений Aztec Code р равно 0 (для обеспечения максимальной возможности продолже
ния декодирования).
Для данных сообщения значение р обычно равно двум. Тем не менее, если большая часть способности
исправления ошибок используется для исправления стираний, вероятность наличия необнаруженных ошибок
возрастает. Если ошибок меньше десяти, а число стираний составляет более половины от числа кодовых слов
исправления ошибок, р увеличивается до четырех.
В противном случае символ невозможно декодировать без риска ошибочного декодирования.
/* «prod(x.y.tog.alog.gf)» returns the product «х» times «у» V1*
int prod(int x. int y. int ’log. int ’alog. int gf) (
if (!x || !y) return 0;
else return alog((log[xl + tog(y]) % (gf—1)];
}
/’ «ReedSolomon(wd.nd.nc.gf.pp)» takes «nd» data codeword values in */2>
/* wdfl and adds on «пс» check codewords, all within GF (gf) where «gf» 7
/* is a power of 2 and «рр» is the value of its prime modulus polynomial V
void ReedSolomon(int ‘wd. int nd, int nc. int gf. int pp) {
int i, j, k, ‘log. ‘alog. *c;
Рисунок В. 1 — Функция языка С. генерирующая контрольные слова кода Рида-Соломона, лист 1
11 Функция ~prod(x,y,log.alog,gf)" возвращает произведение "х" и "у".
21Функция ’ReedSotomon(wd.nd.nc.gf.pp)" получает “nd" кодовых слов данных в массиве wd[] и добавляет
*лс" контрольных кодовых слов над полем GF(gf), где ~дГ — степень 2, а "рр" — значение примитивного
многочлена.
26