У. Питерсон - Коды, исправляющие ошибки (1267328), страница 7
Текст из файла (страница 7)
а) Покажите, что с помощью кода С можно обнаружить любую ошибку величины г( или меньше тогда и только тогда, когда расстояние между сообщениями в коде С больше чем г(. б) Покажите, что с помощью кода С можно исправить любую ошибку величины 1, если минимальное расстояние между сообщениями кода больше чем 2й с) Покажите, что с помощью кода С можно исправлять эшибки величины ! и одновременно обнаруживать ошибки велигины 3, д ) й если минимальное расстояние между сообщениями кода равно по крайней мере ! + д + !. 1.4. Покажите, что если код с минимальным расстоянием Хэмиинга е+ ! между кодовыми блоками используется для канала со стиранием, то можно декодировать таким образом, что будут исправлены все комбинации из е (или меньше) стираний, ио не все комбинации из е+! стираний.
1.5. Покажите, что для исправления всех комбинаций из 1 ошибок и е стираний необходимо и достаточно, чтобы минимальное расстояние Хэмминга между кодовыми блоками равнялось по крайней мере 2!+ е+ !. 1.6. Постройте таблицу декодирования кода, исправляющего все эдиночные ошибки, для второго узла древовидного кода, использоганиого в примерах. Предполагается, что первый полученный блок равен 1!. 1.7. Дерево, изображенное на фнг. 1.6, является периодически повторяющимся.
Определите вес пути наименьшего веса, проходящего через все дерево. Используя эту информацию, покажите, что независимо от того, сколь велико допустимое значение и, не все двойные комбинации ошибок могут быть исправлены. (Вес равен числу единиц; см. стр. 53.)' 1.8. Определите вероятность ошибочного декодирования для первого блока кода, рассматриваемого в примере, в случае, когда этот код используется для двоичного симметричного канала с вероятностью ошибки Р. 1.9.
Удовлетворяет лн правило декодирования, задаваемое таблицей, изображенной на фиг. 1.3, условиям декодирования по ме. тоду максимального правдоподобия? Предполагается, что исполь. зуется ДСК-канал и производится только исправление ошибок. 2 Введение в алгебру Существование особых структурных закономерностей в строе. нии кодов, исправляющих ошибки, желательно по двум причинам.
Они облегчают изучение различных свойств кода и, что дагке более важно, обеспечивают возможность практической реализации таких кодов. Основой построения наиболее важных известных кодов является их алгебраическая структура. Данная глава состоит из двух частей. Сначала вводятся наиболее значительные алгебраические понятия и каждое из них иллюстрируется несколькими примерами. В конце главы дается обзор некоторых разделов теории векторных пространств и матриц. Гл. 6 также является чисто математической и посвящена теории колец и конечных полей. Эти две главы ни в коей мере не претендуют на полное математическое изложение материала, а скорее дают лишь минимальные математические предпосылки для исследования кодов, Алгебраические системы — это системы, которые подчиняются определенным правилам или законам; в большей части — это те же законы, которые приложимы к обычным числовым системам.
Так, группа — это система, в которой заданы одна основная операция и операция, ей обратная, например сложение и вычитание или умножение и деление. В кольце определены две основные операции — сложение и умножение и операция, обратная первой из этих операций, — вычитание. В поле определены две основные операции и для каждой из них обратные операции. 2.1. Группы Группой 6 называется совокупность объектов илн элементов, для которых определена некоторая операция и выполняются аксиомы 0.1 — О.4, Пусть а, Ь, с, ...
— элементы группы. Операция— это однозначная функция двух переменных, которая может быть обозначена как Да, Ь) = с, но обычно ее записывают в виде + =с или аЬ= с и называют сложением нли умножением, даже есл если она не является арифметическим сложением нли арифметическим умножением обычных чисел. Аксиома О.! (замкнутость). Операция может быть применена. двум элементам группы, в результате чего получается третий элемент группы. Аксиома 6.2 (ассоциативный закон), Для любьсх трех элементов а, Ь и с группы (а+ Ь)+ с = а+(Ь+ с), если операц я записана как сложение, или а(Ьс) = (аЬ)с, если операция записана как умножение.
Ассоциативный закон означает, что порядок выполнения операций несуществен и поэтому скобки не необходимы. Аксиома В.З. Существует единичный элемент. Если операция называется сложением, то единичный элемент называется нулем, обозначается как О и определяется из уравнения О + а = а + О = а, которое должно выполняться для любого элсмента группы. Если операция называется умножением, то единичный элемент называется единицей, обозначается как 1 и определяется из уравнения 1а = а1 = а. Аксиома б.4.
Каждый элемент группы обладает обратным элементом. Если операция называется сложением, то обратный элемент, соответствующий элементу а, обозначается через — а и определяется как решение уравнения а+( — а) =( — а)+ а = О. Если операция называется умногкением, то обратный элемент обозначается как а-' и определяется уравнением аа-' = а-'а = 1. Кроме перечисленных аксиом, элементы группы могут удовлетворять коммутатнвному закону, т. е. для ннх может выполняться равенство а+ Ь = Ь+а или, если операция является умножением, равенство аЬ = Ьа. В этом случае группа называется абелевой или коммутативной.
При изложении общей теории групп в этой книге используются обозначения, принятые для операции умногкения. Теорема 2.1. Группа обладает единственным единичным элементом, и каждый элемент группы имеет единственный обратный элемент. Доказательство. В группе только один единичный элемент, ибо если имеются два единичных элемента 1 н 1', то (1)(1') = 1 = 1'. Аналогично обратный элемент единствен, нотому что если бы некоторому элементу группы у соответствовали два обратных элемента д ' и д ,то выполнялась бы цепочка равенству-' = !д-' = =д;1дд-~=у 1=у, так что эти элементы должны были бы совпадать.
Ч. т. д. Заметим, что обратный элемент произведения равен произведению обратных элементов сомножителей, взятых в обратном порядке, так как (аЬ) (Ь вЂ” 'а — ') = а(ЬЬ вЂ” ')а-' = а1а — ' = аа-' = 1 и поэтому Ь вЂ” 'а-' = (аЬ) — ', Примеры. Совокупность всех действительных чисел является группой относительно операции обычного сложения, Совокупность всех положительных н отрицательных целых чисел с нулем также вляется группой относительно сложения.
Совокупность всех дей- ительных чисел без нуля является группой относительно обычпого умножения. Все эти группы абелевы. Совокупность всех не- рожденных квадратных матриц порядка а представляет собой относительно матричного умножения неабелеау группу. многие важные группы могут быть описаны как совокупности ,реобразований некоторого пространства. Групповая операция, называемая умножением, определяется при этом следующим образом: преобразование аЬ есть результат последовательного выполнения сначала преобразования Ь, а затем преобразования а.Например, совокупность вращений а-мерного евклидова пространства является группой. Заметим, что вращения двумерного пространства образуют абеаеву группу, тогда как вращения трехмерного пространства не коммутативны.
В качестве первого примера конечной группы рассмотрим линейные преобразования плоскости, которые переводят квадрат в себя. Преобразование полностью определено, если указан результат его воздействия на четыре вершины квадрата. Ю С Например, одиим из возможных преобразований является поворот квадрата на 90' против часовой стрелки, так что А переходит в В,  — в А, С в в В, а Π— в С. Это преобразование можно записать с помощью обозначений, обычно используемых для подстановок: В А В С Существует восемь таких преобразований: Таблица умножения имеет вид 1 а Ь с е е 1!еЬсс'е1е в а Ь с 1 е 1 я Л Ь Ь с 1 а ! Е Н е с е 1 а Ь Е Н е а Л д ! е 1 с Ь а е е е я ! а ! с Ь евяьа!с ЕЕ!елсЬа! Из этой таблицы легко увидеть, что у каждого элемента есть обратный элемент.
Хотя ассоциативный закон также можно было бы проверить с помощью таблицы, это было бы очень утомительной работой; однако из определения группы ясно, что ассоциативный закон имеет место. Существует группа, состоящая только из одного элемента. Этот элемент должен быть единичным элементом в соответствии с аксиомой О.З; легко проверить, что при этом выполняются и другие аксиомы.
Существует также группа, состоящая из двух элементов. Один из них должен быть единичным элементом О. Обозначим второй элемент через а. Так как должен быть обратный элемент и а+ О = а Ф О, — а ~ О, то — а = а. Таким образом„правила сложения должны быть такими: О+О = О, О+а = = а + О = а, а+ а = О, н совокупность двух элементов, сложение которых определено этими правилами, удовлетворяет аксиомам 6.1 — 6.4. Итак, единственная группа из двух элементов также является абелевой. 2.2. Кольца Кольцом Й называется множество элементов, на котором определены две операции. Одна из них называется сложением и обозначается как а + Ь, а другая называется умножением и обозначается как аЬ, даже если эти операции не являются обычными операциями сложения и умножения чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
