У. Питерсон - Коды, исправляющие ошибки (1267328), страница 65
Текст из файла (страница 65)
Как следует из теоремы 9.8, при любой фиксированной скорости отношение минимального расстоянии к длине кода стремится к нулю при возрастании и. 9.4. Процедура исправления ошибок У;Х! =З е(а)= х' и значения 5; = е(соз) задаются + 2(о — 1. Заметим, что, согласно (9.11) пРовеРками пРи то ( 1 ( т + теоремам 6.14 и 6.18, У~Х," = — ~, У~Х~~~ = 51о. (9.12) 1 В этом разделе рассматривается процедура исправления ошибок для произвольного кода Боуза — Чоудхури — Хоквингема, определенного в равд.
9.1. Эта процедура позволяет исправлять любые комбинации нз 1о или меньшего числа ошибок, если йо) ) 21о+ 1. На первом этапе построения процедуры исправления ошибок нужно найти способ описания информации об ошибках, которую дают проверочные соотношения (проверки), т. е, синдром. Предположим, что передан кодовый вектор 1(Х), при передаче произошли ошибки и принят вектор г(Х) = 1(Х)+ е(Х). Рассмотрим результат подстановки а"", а +', ..., а +м-' в многочлен г(Х). Поскольку 1"(Х) — кодовый вектор и, следовательно, эти элементы будут его корнями, то в результате подстановки получим е(а '),е(а +'),...
е(аоь+ои-!) Вектор ошибок е(Х) можно задать перечнем значений его ненулевых компонент и позиций, на которых они расположены. Эти позиции будут определяться ноиеражи позиций ошибок; для (и — 1)-го символа это просто ай Каждая ненулевая компонента е(Х) описывается парой элементов У, (величиной ошибки) и Х~ (номером позиции ошибки); здесь У; — элемент бг(д), а Х,— элемент бГ(д™).
Если произошло о ошибок, то е(Х) имеет о ненулевых компонент и, следовательно, для описания ошибок требуется пар (Хьуо). Тогда В двоичном случае возможно некоторое упрощение. Так как величина У; не равна О, то она должна быть равна 1. Для исправления ошибки необходимо знать лишь ее положение, и поэтому вектор ошибок полностью описывается перечнем номеров позиций ошибок. Из принятого вектора вычисляются 2!о величин Зь тпй ( ~1 тле+ 2!о — 1, и, для того чтобы исправить ошибки, должна быть найдена пара (Уь Х;) для каждой из !о или меньшего числа ошибок.
Уравнения 5 = Х У~Х1> гпо ~(! ~ (шо+ 2!о — 1 (9.13) связывают известные и искомые величины, и любой метод решения этих уравнений составляет основу процедуры исправления ошибок. Эти уравнения нелинейны и на первый взгляд кажется, что пет надежды получить непосредственное их решение. Поскольку существует лишь конечное число возможных решений, то истинное решение может быть найдено просто перебором всех возможных решений. Однако в представляющих интерес случаях существует слишком много возможных решений для того, чтобы считать такой метод эффективным. Все же возможен приемлемый компромисс.
Предположим, что в действительности происходит о ~ !о ошибок. Они описываются о парами (У;, Х;), причем ни Уь пи Хс не равны О. Пусть уравнение (Х вЂ” Х,)(Х вЂ” Хт)... (Х вЂ” Х,)=Х'+ о;Х' '+ + ... + о 1Х+ и, (9.14) определяет величины аь ом ..., о„являющиеся элементарными' ) симметрическими функииями от Х;. Заметим, что если в уравнение (9.14) вместо Х подставить Х;, то обе его части обратятся в нуль. Оказывается, что величины 5~ и ос связаны системой линейных уравнений и это позволяет определить о;. Значения Х; могут быть найдены последовательной подстановкой всех элементов поля в уравнение (9.14). При известных значениях Х; уравения (9,1!) линейны относительно У, и могут быть решены.
Следующий этап состоит в нахождении соотношения, связывающего 3! и оь н доказательстве того, что решение всегда существует. Если обе части уравнения (9.14) умножить на УсХ~ и затем вме! сто Х подставить Х;, то получится следующее уравнение: У,Х,"о, + У;Х(+'оч, + ... + У,Х)+' 'о, + У;Х,' " = О. (9.15) Суммируя эти уравнения по всем значениям с, 1 ( ! ( о, и используя выражения (9.! Ц, получим соотношения, связывающие пс и Яч Я!о„+ Я! ь,а,, + ... + Я!+, ~о~ + Яг+, —— О, (9.16) где все 51 известны для то ( 1( гпо+ 2!о — 1 — т. '1 С точностью до анака. — Прил.
дерев. ать З,+! !!ч~.! ° ° 8и~ 1-т — ! ~те+ 2 ° 'ь!ь+ ч — ~та+~ — ! ~ее+а ° ° - Я!!ч+2т 2 невырождена, если величины 5! образуются точно из ч различных ненулевых яар (Уь Х!). Матрица вырождена, если 5! образуются из меныиего чел! ч числа ненулевых пар (У!, Х,). Доказательство. Используя уравнения (9.11), мож !о проверить, что ... х 1 1 Х! Хэ Х 'Х'' ! 2 ! х, ...
х, ' 1 Х,...ХГ' у,х'," о ... о о ухГ о (9.18) о о у,х," ! х. . х,' ' Матрица М невырождена тогда и только тогда, когда каждая из матриц в (9.18) невырождена. Первая и последняя матрицы— это матрицы Вандермонда, и, как видно из формулы (9.4), они невырождены тогда и только тогда, когда Хь Хь ., Х, различны. Средняя матрица диагональная и невырождена тогда и только тогда, когда все Х; и У! ненулевые. Таким образом, матрица М невырождена тогда и только тогда, когда все пары (Уь Х!) различны и не равны нулю.
Ч. т. д. Для того чтобы из степенных сумм и номеров позиций ошибок можно было определить значения У;, необходимо, чтобы т уравнений (9,11) были линейно независимы. Рассмотрим первые уравнений относительно У;: У!Х!"+! + У Х~ч' + ... + Г~Х~! =Я !!,+!! (9 !9) у Х в+ч !+уХ!!ь+ю !+ +у ЛФч+! ! Л Ответ на вопрос о разрешимости уравнений (9.16) дается в следуюшей теореме: Теорема 9.9.
Матрица Определитель системы равен Х! Х2 .*. Х. Хта+! Хта+! Хт.+! ! э * ° ° у' с/тв+т ! ъио+у ! ъта»м ! Х! Х2 Хт 1 1 ... 1 Х Х ...Х Х»!»»ОХ~э Хюв (9.20) ! Х определитель в правой части есть определитель Вандермонда, такой же, как н в формуле (9.4). Поэтому, если все Х! различны и ненулевые, а ° в данном случае так оно и есть, то правая часть не равна нулю. Следовательно, уравнения (9.!9) линейно независимы и, если Хь Хь ..., Х„найдены, они могут быть решены относительно неизвестных Уь Уь ..., У,. Из (9.20) видно, что эти значения ошибок могут быть определены посредством обращения матриц.
Исправление ошибок может быть проведено следующим образом: 1. По принятому вектору вычисляются значения Яь пге ~ 1' ~ =л»а+21!! — !. По существу вычисляются проверочйые соотношения. 2. Определяется максимальное число последовательных уравнений, являющихся линейно независимыми. Оно равно числу т действительно произошедших ошибок. 3. Все о,+», о,+м ..., о! полагаются равными нулю, и решаются первые т уравнений относительно и», ам ..., а,. 4. Каждый ненулевой элемент 6Р(д") подставляется в многочлен Х +о»Х ~+ ... +»»„. Корни многочлена будут номерами позиций ошибок Хь Хь ... ..., Х,.
5. (Этап, не нужный в двоичном случае.) Номера позиций ошибок, полученные на четвертом этапе, подставляются в первые т уравнений (9.1!) и находятся соответствующие неизвестные величины У». Определитель матрицы коэффициентов имеет такой же вид, как и определитель (9.4), и поэтому не равен нулю. Следовательно, эти уравнения линейно независимы. Знания значений Х» и У» достаточно для исправления ошибок, 1трамер. В предыдущем примере был рассмотрен двоичный (15,5)-код Боуза — Чоудхури, исправляющий все комбинации нз трех нли меныпего числа ошибок.
Предположим теперь, что произошло две ошибки на позициях, соответствующих аз н а". Тогда вычисления проверок на четность принятого вектора (г(Х)) дают (см, табл. 6.1) З~ = г (а) = (! 1 ! ц =,р ~.'=. ( ) =(1 О11) =аз ' сз = г (а') = (О 1 1 1) = ам (9.22) о = Ф = а = (1 О 1 О), 'сл=язз= а' =(1 000), Яо=Яз= а"=(1001). (9.23) Уравнения (9.16) принимают вид а "оз + а'о, + ато, = аз, а'о, + а'о, + а'о, = а", азаз +азо + а1оо ам (9.24) Умножая первое уравнение на соз = а ", второе †сР = а з и третье — на сзз = а-1о, получаем азиз + а'о, + о, =- а", азиз + а~аз+ о, = а', сРо +а'о +о =а'. Складывая первое уравнение с каждым из остальных, получим два уравнения, не содержащих неизвестной оз.
(1010)аз+(О! 11)оз (О 1 01), или аооз +а!оо =аз (1001)аз+(0001)о,=(1! 01), или амаз+а =аз. Хз+ а'зХ+ а'з= О. (9.26) Легко проверить, что этому уравнению удовлетворяют элементы з а и а'о и только они. Так как рассматриваемый код двоичный, знания номеров позиций ошибок достаточно для исправления этих Эти уравнения отличаются только множителем аз, и, следовательно, второе уравнение зависит от первого. Поэтому последнее из трех уравнений (9.23) должно зависеть от первых двух, и, следовательно, произошло только две ошибки.
Полагая в уравнениях (9.25) оз — — О, полУчаем и'ооз = аз, нли оз = сР. Из любого УРавнения (9,24) находим оз = а'з. Номера позиций ошибок будут корнями уравнения и уравнения (9.16) будут иметь вид оспа+ ссмоз+ аап = о1з. а'таз + аааз+ амо = а'с, оба + 12о + о14а с и (9.27) умножая первое уравнение на из = а а, второе — на а'= а-'з, а третье — на а = а-", получаем аоз + о~а, + о, = о', ~~+ ~Уо~+ п~ — — ссс, а'от + а"и, + ас —— — 1. Прибавляя к каждому из двух последних уравнений первое уравнение, находим (О О 1 1) оа + (О 1 1 0) пз = (! 0 О 0), илн а'аз + о~аз = оз> (1001) ох+(0001) аз=-(1! 01), илн а'сна+ ос=а'з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
