Дипломная работа "Программная реализация БЧХ-кодов переменной длины"

197-577-902

Программная реализация БЧХ-кодов переменной длины

Данная страничка является приложением к моему выпускному диплому на математическом факультете ОмГУ. Здесь вы найдете, как текст диплома, так и все, что с ним связано.

Дипломная работа заключалась в реализации алгоритмов кодирования и декодирования двоичных БЧХ-кодов с параметрами m и t. Параметр m задает длину кода n=2^m-1, а параметр t - количество исправляемых кодом ошибок. Параметры m и t задаются пользователем.

Реализовано систематическое и несистиматическое кодирование. Для декодирования используется декодер Питерсона-Горенстейна-Цирлера с алгоритмом Беркелэмпа-Месси. Также создана демонстрационная программа Magic Coder. В качестве среды разработки использовалась Delphi 2006. Но не составит труда откомпилировать проекты под более ранними версиями.

К сожалению на оптимизацию не хватило времени, и поэтому декодирование производится медленно. Но если у вас есть желание, вы можете заняться ею. Для поиска слабых мест я советую использовать профайлер AQTime. Так беглый просмотр результов профилирования показал, что 75% времени потраченного на декодирование уходит на вычисление компонент синдрома. Данное место можно оптимизировать отказавшись от явных операций сложения и умножения многочленов и их коэффициентов. Т.к. действие происходит в конечном поле, то можно построить таблицу для сложения коэффициентов многочленов. Более того, таблицу можно строить не для самим коэффициентов, а для степеней примитивного элемента. Дело в том, что любой коэффициент можно представить в виде степени примитивного элемента.

Остается только создать таблицу для сложения. Причем таблица эта будет состоять всего из одного столбца. Дело в том, что если i>j, то aⁱ+a^j=a^j(a^i-j+1). Т.о. образом достаточно иметь таблицу степеней примитивного элемента для элементов вида a^k+1.