Способность кодов обнаруживать и исправлять ошибки

 

Кодовым расстоянием или расстоянием Хэмминга между двумя кодовыми словами одинаковой длины называется число несовпадающих в них символов. Например, расстояние Хэмминга между комбинациями 10010011 и 10000001 составляет d =2. Чем больше минимальное расстояние между разрешенными кодовыми комбинациями, тем больше избыточность. При безызбыточном кодировании d =1.

Ошибка кратности r приводит к тому, что искаженная комбинация отодвигается на расстояние d = r от исходной. В то же время ошибка не может быть обнаружена, если она переводит одну разрешенную кодовую комбинацию в другую. Следовательно, способность кодов обнаруживать ошибки зависит от кодового расстояния между разрешенными кодовыми словами: чем больше расстояние, тем большей кратности требуется ошибка, переводящая одну разрешенную комбинацию в другую. Таким образом, если минимальное кодовое расстояние между разрешенными комбинациями равно d_min, то можно обнаружить ошибки кратностью r≤ d_min -1.

Способность кодов исправлять обнаруженные ошибки состоит в возможности однозначного отнесения запрещенной кодовой комбинации к некоторой единственной разрешенной комбинации. Для этого достаточно, чтобы выполнялось условие d_min ≥ 2r +1, следовательно, коды с заданным d_min обеспечивают исправление ошибок кратностью r≤ (d_min -1)/2. В рассмотренном примере коды содержат 4 информационных и 3 контрольных символа, d_min=3, поэтому они могут обнаруживать однократные и двукратные ошибки, а исправлять только однократные.

 

ПОИСК ДАННЫХ

Проблема поиска данных

С проблемой кодирования данных, передаваемых по каналу связи, тесно связаны проблемы их хранения в запоминающих устройствах (ЗУ) и поиска необходимых данных по специальному запросу. Действительно, чтобы исходному сообщению поставить в соответствие определенное кодовое слово, это слово часто нужно найти в некотором ЗУ. Приняв кодовое слово, также бывает необходимо найти в ЗУ данные, соответствующие исходному сообщению. С другой стороны, сложные системы поиска (например, в СУБД) в процессе своего функционирования используют большое число процедур кодирования и декодирования информации.

При рассмотрении задач поиска будем предполагать, что данные находятся в ЗУ в виде записей, каждая из которых содержит специальное поле, называемое ключом. Обычно требуется, чтобы ключи были различными и чтобы каждый ключ однозначно определял свою запись. Совокупность записей образует таблицу или файл, размещаемый в запоминающем устройстве.

Поиск обычно начинается с получения извне аргумента поиска и состоит в отыскании записи, ключ которой совпадает с аргументом поиска или находится с ним в определенном соотношении. Существуют две возможности окончания поиска: либо поиск оказался удачным, т.е. позволил найти нужную запись, либо неудачным, т.е. показал, что записи с данным ключом в таблице отсутствуют.

Хотя целью поиска являются данные, содержащиеся в некоторой записи, их извлечение, когда запись найдена, принципиальных затруднений не вызывает. Поэтому для простоты можно считать, что записи состоят только из ключей.

Конкретные процедуры поиска и их эффективность во многом определяются теми возможностями, которые предоставляют различные виды запоминающих устройств. Поэтому изучение методов поиска целесообразно начать с рассмотрения важнейших разновидностей ЗУ.

Виды ЗУ

С точки зрения поиска данных большинство известных запоминающих устройств можно отнести к одному из трех видов: последовательные, адресные и ассоциативные.

Последовательные ЗУ при каждом считывании предоставляют во внешнюю среду очередную запись таблицы или файла. Чтобы получить в распоряжение некоторую i -ю запись таблицы, нужно прежде произвести считывание предыдущих (i-1) записей. Последовательный доступ к данным реализуют такие технические устройства, как накопитель на магнитной ленте, автомат магазинной памяти и т.п.

Адресные ЗУ при каждом считывании предоставляют запись, находящуюся в ячейке, адрес которой указан на входе устройства. Чтобы получить некоторую i -ю запись таблицы, нужно на входе ЗУ указать адрес (номер) ячейки, в которой размещена эта запись. На рис. 2.1 представлена схема адресного ЗУ.

 

 

Рис.2.2

Схема адресного ЗУ

 

Адресное ЗУ состоит из двух частей: дешифратора адреса и матрицы ЗУ. Записи хранятся в строках матрицы ЗУ. Двоичный код адреса записи поступает на вход дешифратора адреса, который преобразует его в унитарный код с числом разрядов, равным количеству строк в матрице ЗУ. Логическая единица появляется на выходе дешифратора, номер которого соответствует двоичному коду адреса. Под действием сигнала логической единицы содержимое соответствующей строки матрицы ЗУ выводится на выход устройства. В качестве адресных ЗУ выступают такие технические устройства, как оперативное и постоянные запоминающие устройства ЭВМ, накопители на магнитных, оптических дисках и т.п.

Ассоциативные ЗУ при каждом считывании выдают на выходе запись, содержимое определенного поля которой совпадает со значением ключевого слова, поданного на вход устройства. Чтобы получить в распоряжение i -ю запись таблицы, нужно на вход ЗУ подать кодовое слово, соответствующее ключевому слову i -й записи. На рис. 2.2 приведена схема ассоциативного ЗУ.

 

Рис.2.2

Схема ассоциативного ЗУ

 

 

Ассоциативное ЗУ состоит из справочника и матрицы ЗУ. В строках матрицы ЗУ хранятся записи. Каждая ячейка справочника представляет собой регистр, рассчитанный на хранение одного ключевого слова соответствующей записи матрицы ЗУ. Он дополнен специальными комбинационными логическими схемами, предназначенными для сравнения содержимого регистра с ключевым словом, поступающим одновременно на вход всех ячеек. Выходные шины справочника выполняют функцию адресных линий, следовательно, необходимость в дешифраторе адреса отпадает. В качестве ассоциативных ЗУ выступают технические устройства, называемые памятью с адресацией по содержанию, файлом с параллельным поиском, ассоциативным процессором и т.п.

Из запоминающих устройств всех видов ассоциативные ЗУ непосредственно решают задачу поиска: подавая на вход ассоциативного ЗУ аргумент поиска, на выходе сразу получаем запись, ключ которой совпадает с аргументом. Однако ассоциативные ЗУ являются также наиболее дорогими и сложными технически, поэтому в настоящее время задачи поиска обычно приходится решать на основе адресного или последовательного ЗУ.

Адресное ЗУ позволяет легко получить запись, зная ее порядковый номер в таблице. Следовательно, чтобы решить задачу поиска, нужно от аргумента поиска перейти к номеру записи в таблице. Для этого перехода требуется осуществить либо некоторую процедуру преобразования аргумента в адрес, либо некоторую процедуру проверки содержимого последовательности записей. В последовательных ЗУ поиск строится на основе просмотра содержимого записей.

Далее будут рассмотрены методы поиска, ориентированные, в основном, на адресные ЗУ. При этом, отвлекаясь от конкретных способов задания адресов в различных ЭВМ и системах программирования, будем считать, что имеется возможность получить значение ключа записи по ее номеру в файле или таблице.

Методы поиска можно разделить на два класса:

поиск, основанный на преобразовании аргумента в адрес;

поиск, основанный на сравнении ключей.

Рассмотрим оба этих класса.

 

§3. Поиск на основе преобразования ключа в адрес

 

Идея данных методов поиска состоит в том, чтобы по аргументу поиска определить адрес соответствующей записи и получить эту запись за одно считывание данных.

Простейшей реализацией этой идеи является использование аргумента, эквивалентного адресу. Например, на каждой квитанции по квартплате может быть указан адрес записи в файле, соответствующей данному абоненту. Физический адрес вводится в ЭВМ и по нему считываются необходимые данные.

Примерно такой же простотой и быстротой характеризуется поиск, основанный на определенной регулярности возможных значений ключей. Например, если в файле успеваемости студентов в качестве ключей использовать последовательность NMP, то адрес записи с информацией об успеваемости студента с номером N в месяце M по предмету с номером P может вычисляться по формуле (N-1)∙35∙12∙L + (M-1)∙12∙L + (P-1)∙L + 1, где L – длина записей в файле.

Рассмотренные способы основаны на учете конкретных закономерностей значений ключей, поэтому они носят ограниченный характер. Во многих задачах поиска нежелательно или недопустимо накладывать какие-либо ограничения на возможные значения ключей. Так, в предыдущем примере может потребоваться искать записи по фамилиям студентов, а не по их порядковым номерам. В этом случае нет практически никакой регулярности в возможных значениях ключей и вышеуказанные методы неприемлемы.

Строку символов, составляющих ключ, всегда можно взаимно однозначно преобразовать в целое число. Например, ее можно рассматривать как запись числа в системе счисления с основанием, равным размеру алфавита. Так, для русского алфавита А=0, Б=1, В=2, …, Ю=31, Я=32 и фамилия «ДЕЕВ» будет преобразована в число 4∙33³ + 5∙33² + 5∙33¹ + 4∙33⁰ = 149362. Однако и после такого преобразования значения ключей не приобретут регулярности.

 

Перемешивание

 

Простым и в то же время универсальным методом поиска, основанным на преобразовании аргумента в адрес, является так называемое перемешивание. Этот метод называется также хешированием (кешированием) или рандомизацией.

Идея данного метода заключается в том, что записи размещаются в ячейках памяти, адреса которых получены преобразованием ключей в псевдослучайные числа из диапазона возможных значений адресов.

Пусть, например, таблицу поиска составляют записи с данными о 31 студенте группы и в качестве ключей выступают фамилии студентов. Воспользовавшись тем, что дни рождения более или менее равномерно распределены в диапазоне от 1 до 31, будем в качестве адреса использовать день рождения студента. В этом случае может быть получена таблица адресов, приведенная на рис. 2.3.

 

Рис.2.3

Пример использования перемешивания

 

Теперь, если требуется найти в таблице сведения о каком-либо студенте группы, то его фамилию (аргумент поиска) нужно «преобразовать» в день рождения (адрес), по которому обратиться к соответствующей ячейке памяти.

В приведенном примере отражены две существенные проблемы перемешивания:

1) как найти преобразование значений аргумента в целые числа из заданного диапазона, при котором числа были бы распределены в диапазоне достаточно равномерно?

2) как поступать в тех случаях, когда двум различным аргументам в результате преобразования присваиваются одинаковые значения адресов и возникает так называемая коллизия?

Для преобразования аргумента в адрес, которое называется функцией перемешивания или хеш-функцией, предложено много алгоритмов, идеи которых в большинстве случаев связаны с методами формирования на ЭВМ псевдослучайных чисел. Процедура получения хеш-адресов выполняется обычно в три этапа:

1. Перевод аргумента (если он не числовой) во взаимно однозначное числовое представление.

2. Преобразование числового представления аргумента в псевдослучайное число, имеющее тот же порядок, что и значения адресов памяти.

3. Нормирование полученного числа для того, чтобы оно строго укладывалось в диапазоне значений адресов памяти.

Следует особо отметить, что псевдослучайный, а не чисто случайный характер получаемых хеш-адресов имеет принципиальное значение. Функция перемешивания должна быть строго детерминированной, так как она используется как при начальном заполнении таблицы или файла, так и при последующем поиске (в обоих случаях по одному значению аргумента должен получаться один и тот же хеш-адрес).

Наиболее распространенная функция перемешивания основана на методе деления. Аргумент в числовом представлении делится на число, равное или близкое к числу записей в таблице. Остаток от деления дает относительный хеш-адрес. Данный метод при всей его простоте обеспечивает достаточно равномерное рассеивание хеш-адресов при заполнении таблицы. Для лучшей равномерности перемешивания делитель должен быть нечетным числом, не должен выражаться степенью основания, по которому ключи переводятся в числовую форму, по мере возможности это должно быть простое число. Например, если число адресов равно 7000, то в качестве делителя подходит число 6997. Пусть числовая форма ключа равна 149362 (строка «ДЕЕВ»), тогда остаток от деления ее на число 6997 равен 2425. Поэтому запись с ключом «ДЕЕВ» при заполнении таблицы направляется в ячейку с адресом 2425, а при поиске извлекается из той же ячейки.

Проблема коллизий решается достаточно просто: при заполнении таблицы для записи, претендующей на уже занятую ячейку, отводится место, расположение которого легко установить, зная адрес коллизии. Простейший прием состоит во введении ячеек переполнения и указании в точках коллизии ссылок на эти ячейки (метод ячеек переполнения). Другой прием заключается в просмотре последовательности ячеек, следующих за вычисленным хеш-адресом, до тех пор, пока не будет обнаружена свободная (метод внутренней адресации).

В любом случае при наличии одной или нескольких ячеек с одинаковыми адресами необходимо иметь возможность идентифицировать по ключам попавшие туда записи, поскольку неизвестно, каким образом эти записи распределены по ячейкам памяти. Обычно для этого вместе с данными записывается ключ соответствующей записи, а на этапе поиска он сравнивается с аргументом поиска.

Возможность коллизий приводит к тому, что не всегда нужная запись находится за одно считывание данных из памяти. При возникновении коллизии, возможно, потребуется два, три или даже более считываний данных – так называемых опробований, пока не будет найдена требуемая запись или не выяснится, что данная запись отсутствует. Другой особенностью данного метода организации поиска является наличие пустых мест в таблице. Дело в том, что чем плотнее заполнена таблица, тем больше вероятность коллизии и, следовательно, больше опробований нужно совершить, чтобы найти нужную запись. Поэтому для сокращения времени поиска целесообразно не заполнять таблицу до конца (на практике плотность заполнения таблицы обычно не более 80-90%).

Во многих случаях методом перемешивания удобно определять адреса не отдельных ячеек, а групп из установленного числа ячеек – участков. По мере заполнения памяти записи помещаются в свободные ячейки участка с вычисленным хеш-адресом. При поиске определяется хеш-адрес участка и далее перебираются записи в участке до тех пор, пока не будет найдена та из них, ключ которой совпадает с аргументом поиска.