ВС:Бухгалтерия 6.3 Печенье с предсказаниями fortune-cookies ru п... (от Печенье с предсказаниями)
Коды с исправлением ошибок
Несмотря на то что бит четности является эффективным методом выявления ошибок, он не дает информации, необходимой для исправления возникшей ошибки. Многих удивляет сам факт, что можно разработать коды с исправлением ошибок, позволяющие не только выявлять ошибки, но и исправлять их. В конце концов, интуиция подсказывает, что мы не в состоянии исправить ошибку в полученном сообщении, если заранее не знаем, о чем том идет речь. Тем не менее существует довольно простой код. позволяющий исправлять возникающие ошибки (рис. 1.28). Для того чтобы понять принцип действия этого кода, сначала необходимо определить дистанцию Хэмминга между двумя кодовыми комбинациями, которая будет равна количеству битов, отличающихся в этих комбинациях. (Понятие дистанция Хэмминга получило свое название в честь Р.В. Хэмминга (R.W. Hamming), который провел первые исследования в области разработки кодов с исправлением ошибок. Он обратился к этой проблеме в 1940-х годах по причине крайней ненадежности существовавших в то время релейных вычислительных машин.) Например, дистанция Хэмминга между кодами букв А и В равна четырем, а дистанция Хэмминга между кодами букв В и С равна трем. Важной особенностью этого кода является то. что дистанция Хэмминга между любыми двумя комбинациями будет не меньше трех. Если в результате сбоя в каком-либо отдельном бите появится ошибочное значение, то ошибка будет легко установлена, так как получившаяся комбинация не является допустимым кодовым значением. В любой комбинации потребуется изменить не меньше трех битов, прежде чем она вновь станет допустимой. Если в любой комбинации, возникла одиночная ошибка, то легко можно вычислить ее исходное значение. Дело в том. что дистанция Хэмминга для измененной комбинации по отношению к исходной форме будет равна единице, тогда как по отношению к другим разрешенным комбинациям она будет равна не менее чем двум. При декодировании некоторого сообщения достаточно просто сравнивать каждую полученную битовую комбинацию с допустимыми комбинациями кода, пока не будет найдена комбинация, находящаяся на дистанции, равной единице, от полученной комбинации. Найденная допустимая кодовая комбинация принимается за правильный символ, полученный в результате декодирования. Предположим, что получена битовая комбинация 010100. Если сравнить ее с допустимыми битовыми комбинациями кода, то будет получена таблица дистанций. По содержанию этой таблицы можно сделать заключение, что поступивший символ — это буква D. так как ее битовая комбинация в наибольшей степени соответствует полученной. Страница: 1 | 2
.gif){kind=small}
.gif){kind=small}
