У. Питерсон - Коды, исправляющие ошибки (1267328), страница 27
Текст из файла (страница 27)
Следовательно, пакет длины 2Ь илн меньше не может быть кодовым словом. Первое утверждение теоремы (в том числе для вырожденного случая) следует поэтому из теоремы 4.13. Аналогично каждый пакет ошибок длины Ь+1 нли меныпе может быть записан как разность пакета ошибок длины 1 или меньше и пакета длины Ь или меньше. Если код одновременно исправляет пакеты ошибок длины Ь нли меньше н обнаруживает все пакеты длины 1, то пакет длины Ь и пакет длины 1 должны принадлежать различным смежным классам и нх сумма не должна быть кодовым словом.
Второе утвер>кдепне теоремы тоже следует из теоремы 4.13. Ч. т. д. Можно получить еще одну нижнюю границу для числа проверочных символов, принадлежащих линейному коду„исправляющему все пакеты из Ь или меньшего числа ошибок, если заметить, что поскольку пакеты длины Ь или меньше должны принадлежать различным смежным классам, то число смежных классов по край'ней мере так же велико, как число различных пакетов ошибок длины Ь или меньше. Существует всего (а — 1)п различных пакетов ошибок длины 1, так как ненулевая компонента может появиться на месте любого из и символов и этой компонентой может быть любой из д — 1 ненулевых элементов поля. Существует (д — !)е(п — 1) возможных пакетов ошибок длины 2, потому что каждая из двух ненулевых компонент может принимать одно из д — ! возможных ненулевых значений и пакет ошибок может начинаться с любой компоненты вектора, исключая последнюю.
Пакетами ошибок длины г)2 могут быть (д — !)еде-я(п — г+ !) различных комбинаций ошибок, поскольку каждый нз крайних символов может принимать одн>о из д — 1 ненулевых значений, каждый из символов, располо- женных между ними,— одно из д возможных значений и пакет может начинаться с одной из (п — ! + 1) компонент вектора. Общее число комбиваций ошибок, включая комбинацию из всех нулей, поэтому равно ! -1- и (в — ! ) + ~, (д — 1)т вь т (и — ! + 1). Используя два тождества л +1 х' = и ~~~ !х' '= — „( ), (4.64) ю 0 можно привести выражение для общего числа пакетов ошибок к виду д' '((4 — 1)(п — Ь + 1) + Ц, и так как должно быть по крайней мере столько же смежных классов, то верна следующая теорема: Теорема 4.16.
Число проверочных символов любого линейного када, исправляющего все пакеты длины Ь или меньше, равна самое меньшее Ь вЂ” 1+ !оде((д — 1)(п — Ь+ 1) + 1!. Для некоторых из кодов, описываемых в гл. 11, требуется минимальное (или очень мало отличающееся от него) число проверочных символов, которое дается предыдущими теоремами, Для кодов, исправлшощих пакеты ошибок„можно получить границу, аналогичную границе Варшамова — Гилберта.
Предположим, что проверочная матрица Н построена для кода, исправляющего любой одиночный пакет ошибок длины Ь или меньше. Для существования такого кода необходимо и достаточно, чтобы среди кодовых векторов не было вектора, являющегося суммой двух пакетов длины Ь или меньше. В соответствии с теоремой 3.1 для этого необходимо и достаточно, чтобы никакая линейная комбинация столбцов, входящих в два подмножества по Ь или меньшего числа столбцов, расположенных рядом в матрице Н, не обращалась в нуль.
Предположим, что выбраны и — 1 столбцов 1!ь 1!и ... ..., 'п„ь Тогда в качестве столбца и к ним можно присоединить любой вектор, не являющийся линейной комбинацией последних Ь вЂ” 1 столбцов Ь„ь+ь ..., й 1 и любой совокупности из Ь последовательных столбцов, выбранных из пн ..., й„ь. Ъ„Ф(и„,Ь„, + ... +и„-ь,,й„— сы)+ +(Ьь — ь-чй.-ь-~+ + Ь,-ь-~ — ьь~Ф.— ь-;-ам). (466) Наихудшим возможным случаем был бы такой, когда различным набором коэффициентов и, и Ь; соответствовали бы различные суммы в соотношении (4.65).
Коэффициенты а; могут быть выбраны с/ь — ' способами. Коэффициенты Ьэ образуют пакет длины Ь или меньше в векторе длины и — Ь; повторяя рассуждения, аналогичные приведенным при доказательстве теоремы 4.16, можно увидеть, что имеется всего дь '[(д — 1) (и — 2Ь+ 1)+ Ц способов выбора коэффициентов Ьь включая случай, когда все они равны нулю. Таким образом, общее число возможных наборов коэффициентов равно ч ч/ 1[(д — 1)(л — 2Ь+1)+ Ц. Если число всех возможных векторов длины л — й больше, чем эта величина, то обязательно должен найтись вектор и„, удовлетворяющий неравенству (4.65) при любом выборе коэффициентов, и, таким образом, можно построить код длины и, который исправляет все пакеты ошибок длины Ь или меньше.
Так как существует всего 4"-а векторов длины л — й, то это возможно, если йа а > с/з <а и [(д — 1) (и — 2Ь + 1) + Ц. Пусть теперь через Ьг обозначено наибольшее значение Ь, удов- летворяющее этому неравенству. Тогда для Ь = Ьг + 1 справед- ливо противоположное неравенство, т. е. имеет место следующая теорема: Теорема 4.17. Если число проверочных символов п — й удовле- творяет неравенству п — А ~2Ьг+ !ода [(д — 1)(и — 2Ь вЂ” 1) + Ц, то существует линейный (п,м)-код, который исправляет любой одиночный пакет ошибок длины Ьг ( и/2 или меньше.
При больших значениях п из теорем 4.15 и 4.17 вытекает, что (и — й)/2 является практически достижимым максимумом кор- ректирующей способности линейных блоковых кодов для пакетов ошибок. Следующая теорема для сверточных кодов аналогична теореме 4.13 для блоковых кодов: Теорема 4ЛЗ'. Если кодовые слова сверточного кода нв содер- жат в первых э блоках пакетов длины зпа или меньше, то число проверочных символов этого кода равно по меньшей мере зио доказательство аналогично доказательству теоремы 4.13. Верхнюю границу корректирующей способности сверточных ко- дов для пакетов ошибок можно получить, используя следующий дополнительный результат: Теорема 4 18 (Вайнер-Эш).
Для того чтобы сверточный (гпло, гияс)-код исправлял все пакета длины Ьз, содержащиеся в г (смвзкных) блоках'), он должен содержать по меныией мере 2Ьа (г 1) (ио — йа) пРовеРочных символов. ') такие комбянапяи ошибок называются пакетами ошибок типа В2. Показательство. Если код может исправлять все комбинации ошибок, появляющиеся в г блоках, то никакое кодовое слово в неправильном подмножестве не может содержать двух пакетов длины гпо или меньше, каждый из которых состоит из г блоков.
С другой стороны, должен существовать смежный класс, содержащий две комбинации ошибок, которые являются пакетами ошибок длины гпо и различаются первыми блоками. Остается показать, что если ии одно кодовое слово ие состоит из двух таких пакетов, то код должен иметь по меньшей мере 2гп,— (г — 1) (по — йо) проверочных символов. Для доказательства этого покажем, что если код содержит меньше проверочных символов, то найдется по меньшей мере одно кодовое слово в неправильном подмножестве, состоящее из двух пакетов, каждый из которых включает г блоков. Рассмотрим проверочную матрицу Н сверточного кода с параметрами и,, йо, т' и меньшим 2гпо числом проверочных символов. По теореме 4.!3' в этом коде существует кодовое слово, которое содержит пакет длины 2гпо или меньше в первых 2г блоках.
Первый ненулевой блок в пакете может располагаться на месте любого из 2г, блоков. Если первым ненулевым блоком в этом кодовом слове является первый блок, то в неправильном подмножестве найдется кодовое слово, состоящее из двух пакетов, длина каждого из которых равна гпо или меньше. Если первым ненулевым блоком является второй блок, то сдвинем это слово влево на один блок.
При этом получается кодовое слово с, которое содержит пакет ошибок в первых 2г — 1 блоках и, возможно, еще один пакет ошибок в последнем блоке. Построим проверочную матрицу нового кода длины по(т' — 1) из (т' — !) (по — йо) верхних строк проверочной матрицы Н исходного кода. В новом коде найдется кодовое слово с', первые (т' — 1)п, символов которого совпадают с символами слова с. Следовательно, в неправильном подмножестве нового кода найдется кодовое слово, которое состоит из двух пакетов, длина каждого из которых равна гпо или меньше.
Далее, если первым ненулевым блоком является 1-й блок, где 1 =.! ~ г, то укорачивание кода до г — 1 блоков гарантирует существование в неправильном подмножестве укороченного кода кодового слова, состоящего из одного пакета длины 2гп, или меньше, который содержится в первых 2гпо блоках. Следовательно, существует кодовое слово, которое состоит из двух пакетов, длина каждого из которых равна гп, или меньше.
Если первым ненулевым блоком является (г+1)-й блок, то укорачивать код уже не нужно. В неправильном подмножестве имеется кодовое слово, которое состоит из двух пакетов в первом и последнем из г блоков. Если первый ненулевой символ появляется в 1-м блоке, где г+2(!«2г, то укорачивание кода до г — 1 блоков гарантирует существование в неправильном подмножестве нового кода кодового слова, состоящего из двух пакетов длины, не превосходящей гпе. Один пакет появляется в первых г блоках, а второй — в последних г блоках.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
