Файл: Теория и техника передачи данных и телеграфия учебник..pdf

КО Р Р Е К Т И Р У Ю Щ И Е К О Д Ы

§6.1. Принципы построения корректирующих кодов

ками в принимаемых сообщениях является применение в аппа­ ратуре передачи данных корректирующих кодов.

Корректирующими называются коды, позволяющие обнару­ живать или исправлять ошибки, возникающие в сообщении в процессе передачи вследствие воздействия помех.

Поясним принцип построения корректирующих кодов на при­ мере равномерных кодов. В этой главе, как и далее, будем рассматривать только двоичные коды, значения элементов кото­ рых обозначим «О» и «1». Это не ограничивает возможности рас­ пространения методов на случаи кодов с любым основанием. Идея построения корректирующих кодов заключается в том, что

Принцип обнаружения ошибок с помощью кода состоит в сле­ дующем. Переход переданной кодовой комбинации в запрещен^ ную, возможный в результате воздействия помех, выявляется при анализе принятой комбинации в декодирующем устройстве, и тем самым устанавливается факт наличия ошибки в анализируемой комбинация. Вполне очевидно, что если под воздействием помех переданная комбинация трансформируется в разрешенную, то в этом случае ошибки не обнаруживаются и происходит ложное отождествление принятого сообщения с некоторым сообщением источника (необнаруженная ошибка). Таким образом, множе­ ство запрещенных комбинаций можно рассматривать как общую защитную область кода, при этом ошибки в переданной комби­ нации обнаруживаются в Nn— Лг к случаях возможных ее транс-

включает защитная зона, тем выше корректирующие свойства кода.

Вполне понятно, что у наиболее эффективных корректирую­ щих кодов число разрешенных комбинаций значительно уменьшается по сравнению с полным числом возможных ком­ бинаций. При этом код способен исправить jVn — 7VK возмож­ ных трансформаций кодовых комбинаций. Доля же исправля­ емых трансформаций от общего числа возможных составляет

Рис. 6.1.

(1 — NKl Л/Д7VK, т. е. в NK раз меньше доли обнаруживаемых трансформаций. В этом отношении обнаружение ошибок эф­ фективнее, чем исправление.

бинациях в определенных разрядах содержатся все возможные двоичные последовательности длины k или когда набор из NK комбинаций при помощи некоторого преобразования может быть отображен на множество из 2h всех возможных последователь­ ностей длины k. Если же Лг к не равно степени числа 2, то это приводит к тому, что log2 A/K не будет равен целому числу. В та­ ком случае следует log2 A/K округлять до ближайшего большего

ния. Эта операция осуществляется в кодирующем устройстве. Таким образом, в каждой кодовой комбинации корректирую­

щего кода, наряду с k элементами, несущими информацию источ­ ника сообщений (информационные элементы), имеется г эле­ ментов, обеспечивающих коду корректирующие свойства (избы­ точные элементы).

Вводимая в кодовую комбинацию избыточность оценивается либо числом избыточных элементов (абсолютная избыточность), либо отношением kin (скорость передачи или коэффициент передачи кода).

Минимальное кодовое расстояние. Минимальное кодовое расстояние dM 1 ,„ между различными парами кодовых комбинаций

исправляются кодом.

Пусть s означает кратность гарантийно обнаруживаемых ко­ дом ошибок, a t — кратность гарантийно исправляемых ошибок. Если код используется только для обнаружения ошибок, то для обнаружения всех вариантов из s или менее ошибок в кодовой комбинации необходимо и достаточно иметь минимальное кодо­ вое расстояние, равное dM„„ s-L 1. Действительно, если мини­ мальное расстояние равно s - f l , то никакой вариант s-кратной ошибки не может перевести передаваемую комбинацию в разре­ шенную, в го время как при минимальном расстоянии dMWH^.s существует хотя бы одна пара комбинаций, отстоящих друг от друга на расстоянии, меньшем или равном s, и найдется такой

можно, если с/М И н^2^4-1. В этом случае в защитную зону каж­ дой кодовой комбинации входят все запрещенные комбинации,