Теория информации

011 100 101 110 111 4) подгруппа: 000 001 010 111 Большинство корректирующих кодов образуются путем добавления к исходной k  комбинации r  контрольных символов. В итоге в линию передаются n = k + r символов. При этом корректирующие коды называются (n,k) кодами . Как можно определить необходимое число контрольных символов? Для построения кода способного обнаруживать и исправлять одиночную ошибку необходимое число контрольных разрядов будет составлять:   1 log   n kn . Это равносильно известной задаче о минимуме числа контрольных вопросов, на которые могут быть даны ответы вида “да” или “нет”, для однозначного определения одного из элементов конечного множества. Если необходимо исправить две ошибки, то число различных исходов будет составлять . 2 n С Тогда:   2 1 1 log n n C C k n     , в этом случае обнаруживаются однократные и двукратные ошибки. В общем случае, число контрольных символов должно быть не меньше:           t i i n t n n n C C C C kn 0 2 1 log ... 1 log (2.2) Эта формула называется неравенством Хэмминга, или нижней границей Хэмминга для числа контрольных символов.