Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Связь корректирующей способности кода с кодовым расстоянием
|
|
Для оценки степени различия между двумя произвольными комбинациями данного кода используется, как уже отмечалось, характеристика, получившая название кодовое расстояния между комбинациями. Наименьшее расстояние между разрешенными кодовыми комбинациями d min - очень важная характеристика кода, ибо именно она характеризует его корректирующие способности.
Актуальной является задача определения наибольшего числа Nd кодовых комбинаций n-разрядного двоичного кода с кодовым расстоянием d. В теории кодирования существуют следующие оценки:
| d = 1 | N  =2 
|
| d = 2 | N =2 
|
| d = 3 | N 
|
| …….. | …….. |
| d = 2 t +1 | N  .
|
При d min=1 все кодовые комбинации являются разрешенными.
В качестве примера рассмотрим код со значностью n = 3. Все возможные комбинации кода представлены в таблице 1.1.
Таблица 1
Комбинации кода значностью n = 3
| А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | А 7 | А 8 |
Матрица расстояний между кодовыми комбинациями имеет вид (табл. 2).
Таблица 2
Матрица расстояний между кодовыми комбинациями
| A 1 | A 2 | A 3 | A 4 | A 5 | A 6 | A 7 | A 8 | |
| A 1 | ||||||||
| A 2 | ||||||||
| A 3 | ||||||||
| A 4 | ||||||||
| A 5 | ||||||||
| A 6 | ||||||||
| A 7 | ||||||||
| A 8 |
Для данного кода d min=1, поэтому любая одиночная ошибка трансформирует данную комбинацию в другую разрешенную комбинацию. Это случай безызбыточного кода, не обладающего корректирующей способностью.
Для того, чтобы код обеспечивал обнаружение однократных ошибок, необходимо из всего множества N 0 = 8 возможных комбинаций выбрать в качестве разрешенных такие комбинации, кодовое расстояние между которыми было бы не менее 2, т.е. d min= 2. Например:
| А 1 | А 4 | А 6 | А 7 |
Или
| А 2 | А 3 | А 5 | А 8 |
Тогда любая однократная ошибка переводит комбинации А 1 – А 7 или А 2 – А 8 в запрещенные и ошибка обнаруживается.
Для обнаружения двукратных ошибок необходимо выбрать кодовые комбинации с d min=3. Это
| А 1 | А 8 |
Или
| А 2 | А 7 |
Или
| А 3 | А 6 |
Или
| А 4 | А 5 |
Таким образом, для того, чтобы код обнаруживал все ошибки кратности t и ниже, необходимо, чтобы
Рассмотрим возможности исправления однократных ошибок. Возьмем комбинации А 1 и А 4, кодовое расстояние между которыми d =2.
Видно, что подмножества запрещенных комбинаций для А 1 и А 4 оказались пересеченными и при возникновении ошибки нельзя однозначно установить, какой сигнал был передан А 1 или А 4.
Возьмем в качестве второй разрешенной комбинации комбинацию, отстоящую от А 1 на d =3, т.е. А 8 =111. При возникновении однократной ошибки возможны следующие подмножества запрещенных комбинаций:
В этом случае подмножества запрещенных комбинаций не пересекаются. Следовательно, при d =3 обеспечивается исправление всех однократных ошибок.
В общем случае, для исправления ошибок кратности t необходимо d min 
2 t +1.
|
|