Обеспечение достоверности передаваемой информации применением корректирующих кодов. Код Хэмминга - алгоритм обнаружения и исправления одиночной ошибки. Использование циклических кодов при последовательной передачей между ЭВМ и внешними устройствами.
Аннотация к работе
В соответствии с теоремой Шеннона для дискретного канала с помехами, вероятность ошибки при передаче данных по каналу связи может быть сколь угодно малой при выборе соответствующего метода кодирования сигнала, т. е. помеха не накладывает существенных ограничений на точность передачи информации (данных). Помехоустойчивыми или корректирующими кодами называются коды, позволяющие обнаружить и устранить ошибки при передаче информации изза воздействия помех. Для обнаружения кратных ошибок используется код КО-ОД-ООГ (коррекция одиночной, обнаружение двойной и обнаружение кратной ошибки в одноименной группе битов). Для исправления двух и более ошибок (d0 ? 5) используются циклические коды БЧХ (Боуза - Чоудхури - Хоквингема), а также Рида-Соломона, которые широко используются в устройствах цифровой записи звука на магнитную ленту или оптические компакт-диски и позволяющие осуществлять коррекцию групповых ошибок. Способность кода обнаруживать и исправлять ошибки достигается за счет введений избыточности в кодовые комбинации, т. е. кодовым комбинациям из к двоичных информационных символов, поступающих на вход кодирующего устройства, соответствует на выходе последовательность из n двоичных символов (такой код называется (n, k) - кодом).Линейным называется код, в котором проверочные символы представляют собой линейные комбинации информационных. Групповым называется код, который образует алгебраическую группу по отношению операции сложения по модулю два. Свойство линейного кода: сумма (разность) кодовых векторов линейного кода дает вектор, принадлежащий этому коду. Коды, порождаемые этими матрицами, называются (n, k)-кодами, а соответствующие им матрицы порождающими (образующими, производящими). При этом, информационная часть остается без изменений, а корректирующие разряды определяются путем суммирования по модулю два тех строк проверочной матрицы, номера которых совпадают с номерами разрядов, содержащих единицу в информационной части кода.Код Хэмминга относится к классу линейных кодов и представляет собой систематический код - код, в котором информационные и контрольные биты расположены на строго определенных местах в кодовой комбинации. Номера информационных бит, включаемых в каждую проверку, определяются по двоичному коду натуральных n-чисел разрядностью - m (табл. Для обнаружения и исправления ошибки составляются аналогичные проверки на четность контрольных сумм, результатом которых является двоичное (n-k)-разрядное число, называемое синдромом и указывающим на положение ошибки, т. е. номер ошибочной позиции, который определяется по двоичной записи числа, либо по проверочной матрице. Если при исправлении ошибки контроль на четность фиксирует ошибку, то значит в кодовой комбинации две ошибки. По заданной длине информационного слова (k = 4), определим количество контрольных разрядов m, используя соотношение: m = [log2 {(k 1) [log2(k 1)]}]=[log2 {(4 1) [log2(4 1)]}]=3, при этом n = k m = 7, т. е. получили (7, 4)-код.