Разработка динамических сайтов
SEO услуги
Управление контекстной рекламой

Вход на хостинг

Имя пользователя:*

Пароль пользователя:*

IT-новости

20.04.2016 iPhone 2017 года поместят в водонепроницаемый корпус из стекла

Линейка iPhone в новом году серьезно поменяется. В этом уверен аналитический исследователь Мин Чи Ку......

подробнее

30.07.2015 Ищем уникальный контент для сайта

Ищем уникальный контент для сайта Без уникального контента Ваш сайт обречен на то, что его страницы......

подробнее

11.05.2015 Распространённые ошибки разработчиков сайтов

Не секрет, что в сети Интернет насчитывается миллионы сайтов, и каждый день появляются тысячси новых......

подробнее

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

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

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

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

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

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

 

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

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

// изучения

#include <stdio.h>

 

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

#define SYM_WIDE 8

 

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


Предыдущая страницаОглавлениеСледующая страница
 
[001] [002] [003] [004] [005] [006] [007] [008] [009] [010] [011] [012] [013] [014] [015] [016] [017] [018] [019] [020]
[021] [022] [023] [024] [025] [026] [027] [028] [029] [030] [031] [032] [033] [034] [035] [036] [037] [038] [039] [040]
[041] [042] [043] [044] [045] [046] [047] [048] [049] [050] [051] [052] [053] [054] [055] [056] [057] [058] [059] [060]
[061] [062] [063] [064] [065] [066] [067] [068] [069] [070] [071] [072] [073] [074] [075] [076] [077] [078] [079] [080]
[081] [082] [083] [084] [085] [086] [087] [088] [089] [090] [091] [092] [093] [094] [095] [096] [097] [098] [099] [100]
[101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120]
[121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140]
[141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151]

+7 (831) 413-63-27
ООО Дельта-Технология ©2007 - 2016 год
Нижний Новгород, ул. Дальняя, 17А.
Rambler's Top100