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

Мы будем исходить из того, что если g = 2ⁿ + 1, то для любого a из диапазона 0…2ⁿ, произведение a*g = c (где с – кодовое слово), будет представлять, по сути, полную мешанину битов обоих исходных чисел.

Допустим n = 2, тогда g = 3. Легко видеть: на что бы мы не умножали g – хоть на 0, хоть на 1, хоть на 2, хоть на – 3, полученный результат делится нацело на g в том и только  том случае, если никакой из его бит не инвертирован (то есть, попросту говоря, одиночные ошибки отсутствуют).

Остаток от деления однозначно указывает на позицию ошибки (при условии, что ошибка одиночная, групповые же ошибки данный алгоритм исправлять не способен). Точнее, если ошибка произошла в позиции x, то остаток от деления k будет равен k = 2^x. Для быстрого определения x по k можно воспользоваться тривиальным табличным алгоритмом. Впрочем, для восстановления сбойного бита знать его позицию совершенно необязательно, достаточно сделать R = e ^ k, где e – искаженное кодовое слово, ^ – операция XOR, а R – восстановленное кодовое слово.

В общем, законченная реализация кодера/декодера может выглядеть так:

Листинг 9. Простейший пример реализации кодера/декодера Рида-Соломна, работающего по обычной арифметике (т.е. с неоправданным расширением разрядной сетки), и исправляющим любые одиночные ошибки в одном 8-битном информационном слове (впрочем, программу легко адаптировать и под 16-байтовые информационные слова). Обратите внимание, что кодер реализуется чуть ли не на порядок проще декодера. В настоящем декодере Рида-Соломна, способном исправлять групповые ошибки, этот разрыв еще значительнее.

// ВНИМАНИЕ! данный кодер/декодер построен на основе обычной арифметики, не арифметики полей Галуа,

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

// изучения

#include <stdio.h>

// ширина входного информационного символа (бит)

#define SYM_WIDE 8

// входные данные (один байт)