Экзамен Курс делится на две части: Теоретическая (стр. 10 из 10)
где σ – кратность ошибки;
r – проверочные символы, исправляющие все 2r ошибки.
Для выбора наиболее эффективного кода следует, кроме минимальной избыточности при требуемой корректирующей способности, обеспечить также согласование корректирующей способности кода с характером распределения ошибок в реальном канале связи. Поэтому вначале определяют распределение ошибок в канале и по обобщенным параметрам подбирают класс кодов, а затем из этого класса с использованием более точной модели потока ошибок находят код, согласующийся с ней наилучшим образом.
5.3. Простейшие коды с обнаружением ошибок
Код с четным числом единиц – блочный, линейный, разделимый (k+1, k)-код, комбинации которого образуются добавлением к информационным k-символам одного проверочного (r = 1) такого значения, чтобы общее число единиц получилось четным. В коде с четным числом единиц dmjn = 2 он позволяет, кроме однократных ошибок δ=1, обнаруживать также ошибки более высокой кратности δ =3, 5, 7,..., так как такие ошибки превращают разрешенные комбинации кода в запрещенные. Ошибки четной кратности код не обнаруживает, так как комбинации из разрешенных вновь переходят в разрешенные.
Вероятность необнаруженной ошибки кода равна сумме вероятностей появления ошибок четной кратности (5 = 2, 4, 6, ...).
Коды с четным числом единиц применяют в системах передачи дискретной информации, ЭВМ и др.
Код с постоянным весом – блочный нелинейный неразделимый код, у которого любая кодовая комбинация имеет постоянный вес (постоянное число единиц).
Вероятность необнаруженной ошибки кода с постоянным весом равна сумме вероятностей появления одной, двух, трех и т.д. пар ошибок.
Наибольшее применение на практике, особенно в радиосвязи, получил международный код МТК-3 (w=3, п=7) с постоянным весом, у которого число разрешенных комбинаций S =
= 35.5.4. Линейные коды, их свойства и разновидности
Линейными называют равномерные коды, проверочные символы которых получаются в результате линейных операций над информационными символами. В двоичных кодах в качестве линейной операции используют сложение по модулю 2.
Так как линейные коды образуют алгебраическую группу (замкнутое пространство, замкнутое множество) по отношению к операции сложения по модулю 2, они являются также групповыми кодами. Любой (п,r)-код полностью определяется совокупностью k линейно независимых комбинаций, образующих порождающую (производящую, образующую) матрицу, которая состоит из п столбцов и k строк:
Например, порождающая матрица линейного (5, 3)-кода имеет вид
Минимальное кодовое расстояние (п, k)-кода равно весу кодовой комбинации порождающей матрицы с минимальным числом единиц. Это весьма важное свойство значительно упрощает определение корректирующих свойств линейного кода.
На практике иногда встречаются случаи, когда для передачи сообщений требуется меньшее число информационных символов, чем имеется в линейном (п, k)-коде с определенным кодовым расстоянием. В таких случаях код укорачивают исключением из его комбинаций i первых информационных символов. Так как при этом число проверочных символов остается постоянным, то корректирующая способность кода не изменяется.
Например, матрица (5, 3)-кода (5.9) при укорочении (i = 1) принимает вид
Минимальное кодовое расстояние полученного (4, 2)-кода осталось без изменения, т.е. dmin= 2. Следовательно, его корректирующие свойства не хуже, чем у исходного (5, 3)-кода. Однако длина его кодовой комбинации уменьшилась на один символ n = 4, так же как и сократилось число разрешенных комбинаций Sр = 2k –– 1 = 3.
5.5. Циклические коды и их свойства
Циклические коды являются разновидностью линейных и вследствие высоких корректирующих свойств, а также более простых кодеров и декодеров, находят широкое применение на практике. Схемы кодеров и декодеров упрощают наложением дополнительных ограничений на подгруппу разрешенных комбинаций циклического кода.
В линейном коде ограничение на подгруппу разрешенных комбинаций сводилось к следующему: сумма любых его комбинаций является также разрешенной, т.е. совокупность комбинаций линейного кода образует замкнутую подгруппу по отношению к операции сложения.
В циклическом коде на подгруппу комбинаций, помимо условия замкнутости по отношению к операции сложениям, накладывается ограничение по отношению к операции умножения (циклического сдвига символов кодовых комбинаций на одну позицию вправо или влево), т.е. циклический код вместе с каждой входящей в него комбинацией содержит все ее циклические сдвиги.
В теории циклического кодирования каждую r-элементную комбинацию принято записывать в виде некоторого полинома G(х) степени (n - 1);
где а - цифры двоичной системы счисления, отображающие элементы кодовой комбинации;
х - фиктивная переменная, заменяющая собой основание системы счисления.
Например, комбинация 1001101 может быть записана в виде
Свойства циклического кода, а также вид кодера и декодера полностью определяются образующим многочленом g (х) степени r. Операции кодирования и декодирования в циклическом коде сводятся к умножению и делению полиномов по правилам двоичной алгебры.
Рассмотрим процесс кодирования на примере. Пусть исходная кодовая комбинация кода 10110 представляет собой k информационных разрядов. Этой комбинации будет соответствовать полином А (х) = х4 + х2 + + х. Предположим, что число контрольных разрядов r = 4 и используется образующий многочлен g (х) = х3+ х + +1. При построении избыточного кода полином неизбыточной кодовой комбинации сначала умножается на xr:
Полученный в результате умножения полином Р (х) делится на образующий многочлен g(х):
Кодовая комбинация циклического кода F(х) получится сложением полинома Р(х) с остатком от деления, т. е. F(х) = Р(х) + остаток Р (x)/g(x) = х8 + х6 + х5 + х3 + х2 + х + 1. Полученная кодовая комбинация избыточного циклического кода будет иметь вид 101101111. Первые пять разрядов ее являются информационными, а оставшиеся четыре – контрольными.
Обнаружение ошибки происходит путем деления полинома F' (х), соответствующего принятой кодовой комбинации, на образующий полином g(x). Признаком принадлежности кодовой комбинации разрешенному подмножеству является деление без остатка полинома F'(х) на образующий полином g(x). При делении запрещенных кодовых комбинаций, образующихся при ошибочном приеме в результате действия помех, обязательно получится остаток, что и используется для обнаружения и исправления ошибок.