Кловский Д.Д. Теория электрической связи. Сборник задач и упражнений (1990) (1151854), страница 17
Текст из файла (страница 17)
Линейный (л, «).иод можно задать проверочной матрицей Н, имеющей размерность гхл. Эта матрица имеет следующий вид: Т,,+, 72 «1,,, Т««+1 1 0... О 71, «+2 72, «-ьз 1'«, «+2 В каждой строке проверочной матрицы на позициях информационных сим. валов стоят коэффициенты у|„, а на позициях нронорочных символов — единицы и нули, причем единица указывает, какой именно проверочный символ соответствует совокупности коэффициентов данной строки. Лля каждой кодовой комбинации (л, «)-кода матричное произведение Таким образом, совокупность кодовых комбинаций (л, «)-кода — это мно.
жество всех последовательностей Ь, для которых выполняется условие (5.13). Это соотношение лежит в основе процедуры декодирования линейных кодов. Проверочная матрица (л, «)-кода является порождающей матрицей нового линейного (л, л — «)-кода, содержащего 2"-" комбинаций, т. е. н(,«|=с(», -1„ Такой (л, л — «)-код называется двойственным для исходного (л, «)-кода. Из (5.13) следует, что (((»,1(Н („„| — — С(» 1|С (,»-Н=О г (5,14) Это условие означает, что двойственные коды (л, «) и (л„л — й) являются ортогональными. Избыточность линейного двоичного кода где г=л — « — число проверочных символов «Оптимальным» является код (л, «), обеспечивающий наименьшую вероятность ошибочного декодирования среди всех кодов той же длины л и избыточности г(л.
Совершенные коды — это коды, которые свою избыточность расходуют на исправление ошибок заданной кратности (1. Квазисовершениым называется код, который, кроме того, исправляет некотор>ю часть ошибок кратности ()+ 1. 83 Обнаружение ошибои при использовании линейных кодов основана на проверке соотношений (5 7): по принятой кодовой комбинации составляются конг. рольные суммы по модулю 2 ь 'Г"р= Хт! гйг, =й+! й+, г=.! (5.
)5) ! ! и знал прннятон лозоваи комбинации Ь) и сспсставтяетс веро ~ными символами принятои кодовой комбинации. Совокупность чисел > рр '"" л„р для данил! ладовой комбинации называетсн сиидрг,мом с(6) =с!с! .. с„ Декодирование принятой кодовой комбинации может быть осуществлено с помощью проверочной матрицы Н Если принята комбинация Ь, то синдроз с можно определить равенством с=ЬН'. Таким образом, синдром — это вектор- строка (сь сз,,с„) с г компонентами (по одкой для каждого проверочно"а символа) Если Ь вЂ” переданная кодовая комбинация, а Ь вЂ” принятая. то сумма их по модулю 2 ЬгсЬ=-2 называется шумовой псследователышстью Прн !том с=опт. П ри права.тьнот! приеме все элементы синдрома равны нулю Отличае хотя бы одного элемента синдрома ат н)ля означает, что произошла ошибка При декодировании с исправлением ошибок по виду синдрома можно определгпь разряд кодовой комбинации, в котором произошла ошибка Задачи 5,2, .
.2.1. Двоичный код, предназначенный для кодирования восьми сообщений, содержит кодовые комбинации: Ь! 00000 Ьз 10011 Ьз — О!010 Ь4= 11001 Ьз =00!01; Ьа = 10110; Ьг =011!1; Ьа= 11100. Является ли данный код ли~нейным? Найти избыточность кода и !гмин. 5.2.2. Построить систематический код (7, 4), цредназначенный для кодирования сообщений двоичного источника, имеющего объем К=2" символов. Показать, что с(„„, такого кода равно 3.
5.2.3, Для систематического кода (7, 4) из предыдущей задачи построить пгроизводяшую и проверочную матрицы. 5.2.4. Построить линейный код (7, 4) по заданной производящей матрице 1000111 0100110 0010101' 0001011 По производящей матрице составить правило формирования проверочных разрядов. Составить проверочную матрицу.
84 5.2.5. Л!инейный !код (7, 4) построен по матрице 1000011 0100101 0 0 1 0 1 1 0' 0001111 1 0 О О О О О О О О О О О 1 1 0 1 0 0 0 0 0 0 0000 1 0 1 001000000000110 0001000000001!1 000010000001001 000001000001010 000000100001011 0 0 О 000010001100 000000001001101 0 0 0 О О О О 0 0 1 О 1 1 1 0 000000000011111 исправляет одиночные ошибки в произвольной кодовой комбинации.
5.2.10. Сравн~ить с точки зрения способности исправления одиночных ошибок линейные коды, заданные произнодяшими матри- цами 1 0 1 1 1 1 0 1 0 0 0 0 0 0 000000111 100000111 010000110 001000101 000100011 000010100 00000101! 000011 000101 000110 001001. 001011 101100 010110 10000 01000 00100 00010 00001 ООООО 00000 Выяснить, какой из кодов, реализуется более простыми средст- вами.
85 Составить про!верочную матрицу и показать процесс исправления ошибок в произнольном,разряде кор!ректирующего кода, информационная часть которого предста|вляет собой 4-разрядные комбинации примитивного дво!ичного кода. 5.2.6. Для кода, заданного в задаче 5.2.4, составить таблицу синдромов и показать, каким ошибочным разрядам они соответствуют, 5.2.7. Составить таблицу синдромов одиночных ошибок для кода (7.4) из задачи 5.2.5 и показать, каким ошибочным разрядам он!и, соответст!вуют.
5.2.8. Убедиться в том, что в кодовых комбинациях 1000111, 0111010, 1101001, 0000000, принадлежащих коду из задачи 5.2.4, может быть исп!равлена ошибка в любом информационном разряде. 5.2.9. Показать, что код, заданный производящей матрицей 1000000111! 01000000111 0010000101! 00010001101 00001001110 00000101001 00000010110 10000001100 01000000110 00!00000011 00010001010 00001000101 00000101001 000000111!О 5.3. ЦИКЛИЧЕСКИЕ КОДЫ од построен по матрице 1000111 0100011 0010110' 0001101 (5.17) й(х) = (х" — 1)lя(х). (5.!В) Таблица 51 Информацноннаа последовательность Колонам комбинация 00 10 О! 1! 00000 !0111 0110! ! Ю!О Рнс.
5.1. Схема формирования дв»- ичного кода 5.2.П. Решить задачу 5.2.10 для кодов, заданных производящими матрицами 5.2.12. Определить, какие из приведенных кодовых комбинаций линейного кода содержат ошибку: 11001!1, 0110101, 0011010, 0010110, 1000100, 1011011, 0010101, 0110010, 1!00100, 01'10101, 100!010, 0011011. К 5.2.13. Для кода (7, 4) из задачи 5.2.2 построить комбинации двойственного кода (7, 3). б.2.14.
Найти комбинации кода (7, 3), двойственного коду (7, 4), из задачи 5.2.4. 5.2.15. Найти комбинации кода (7, 3), двойственного коду (7,4), заданного производящей матрнцей в задаче 5.2.5. 5.2.1б. В табл. 5.1 приведены 2-»разрядные двоичные информационные последовательности и соответствующие им кодовые комбинации. Показать, что полученный код является систематическим кодом с проверкой на четность, и выразить !каждый разряд кодовой комбинации в виде линейной комбинации информационных символов. Найти для заданного кода порождающую и проверочную матрицы.
Найти вероятность неправильного декодирования. 5.2.17. На .рвс. 5Л показана схема формирования двоичного кода при передаче по двоичному симметриаьному каналу с вероятностью ошибочного перехода ро(0,5. Первоначально сдвиговый регистр заполнен нулями; затем в регистр поступают четы»ре информационных символа и одновременно передаются по каналу. После этого передаются три проверочных сиьгвола. Перед вычислением проверочного символа все четыре информационных символа сдвигаются н регистре,на одну позицию вприво. Найти проверочную матрицу, порождающую матрицу, таблицу декодирования и вероятность ошибочного декодирования для данного кода.
Линейный двоичный код, которому принадлежат кодовые комбинации, пол ченные путем циклической перестановки символов, называется циклическим. Кодовый вектор Ь циклического кода представляют полиномом (л 1) степени: Ь(х) =аа+а,х+ааха+ ... +а»х"-', где коэффициенты а» принимают значения 0 или 1.
Прв таком представлении кодовый вектор, полученный ит Ь циклической перестановкой элементов, можно рассма р т ивать как ез льтат умножения полинома Ь(х) на х, если считать, что х" = !. Полипом наименьшей степени среди всех полиномов, соответствующих кодовым комбинациям циклического кода, называется порождающим полиномом й(х) =1+7»х+ттха+ ... +Т,х', Коэффициенты т» равны 0 или 1.
Степень порождающего полинома определяет число проверо чных символов в кодовой комбинации. Число ненулевых членов полиномз п(х) спределяет предельное для данного кода »(мвн. Зная порождающий полинам, можно построить все кодовые комбинации циклического кода, а также устройства кодирования д д р и еко и ования. На по. рождающий полинам должен делиться без остатка двучле ~, у н х 1. Пол чениый результат определяет проверочный полипом Порождающий полинам п(х) и проверочный полипом й(х) являются ортогональными, так как при х" — 1=0 они удовлетворяют условию я(х)й(х) =О. П отсутствии ошибок в кодовой комбинации циклического кода должно выри полняться условие б(х) й(х) =О. (5.19) Невыполнение условия (519), т. е.
б(х)й(х)чьО, является признаком ошибки Задачи 5.3.1. Записать кодовые, комбинации циклического кода, полученные циклическим сдвигом комбинации 110101. 57 5.3.2. Первые т!ри комбинации циклического кода имеют,внд 100001101, 1!0000110, 011000011. Постро~ить остальные комбинации этого кода. 5.3.3. Представить в виде многочлеиов заданные комбинации некоторого циклического кода: 0111110, 0011111, 1001111. 5.3.4. Показать, что полинам д(х) =1+х+х' является порождающим для циклического кода (7, 4). Составить кодовые ко~мбинаци~и циклического кода (7, 4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
