Для любого номера проверочного бита n, начиная с него, n битов подряд оказываются проверяемыми,
затем следует группа из n непроверяемых битов, далее происходит
чередование групп.
Номер бита, содержащего ошибку, равен
сумме номеров контрольных битов,
указавших на ее существование.
Алгоритм проверки и исправления
передаваемой последовательности бит
в представлении Хемминга:
1. Произвести проверку всех битов четности.
2. Если все биты четности верны, то перейти
к пункту 5.
3. Вычислить сумму номеров всех неправильных
битов четности.
4. Инвертировать содержимое бита, номер
которого равен сумме, найденной в пункте
3.
5. Исключить биты четности, передать правильный
информационный код.
Избыточность кодов Хемминга для
различных длин передаваемых последовательностей
приведена в табл. 10.
Видно, что выгоднее передавать и
хранить более длинные последовательности
битов. При этом избыточность не должна
оказаться меньше Lmin для выбранного канала связи.
Таблица 10. Избыточность кодов Хемминга
Число информационных битов |
Число контрольных битов |
Избыточность, L |
8 |
4 |
1,50 |
16 |
5 |
1,31 |
32 |
6 |
1,06 |
2.Чем обусловлена необходимость
структурирования данных?
При любом методе отображения предметной
области в машинных базах, данных
в основе отображения, лежит фиксация
(кодирование) понятий и отношений между
понятиями. Абстрактное понятие структуры ближе всего
к так называемой концептуальной модели
предметной среды и часто лежит в основе
последней. Понятие структуры используется
на всех уровнях представления предметной
области и реализуется как:
• структура информации — схематичная форма представления сложных
композиционных объектов и связей реальной
предметной области, выделяемых как актуально
необходимые для решения прикладных задач;
• структура данных — атрибутивная форма представления свойств
и связей предметной области, ориентированная
на выражение описания данных средствами
формальных языков (т. е. учитывающая возможности
и ограничения конкретных средств с целью
сведения описаний к стандартным типам
и регулярным связям);
• структура
записей — целесообразная (учитывающая особенности
физической среды) реализация способов
хранения данных и организации доступа
к ним как на уровне отдельных записей,
так и их элементов (с целью определения
основных и вспомогательных функциональных
массивов, а также совокупности унифицированных
процедур манипулирования данными). Структура
является общепринятым и удобным инструментом,
одинаково эффективно используемым как
на уровне сознания человека при работе
с абстрактными понятиями, так и на уровне
логики машинных алгоритмов. Структура
позволяет простыми способами свести
многомерность содержательного описания
к линейной последовательности записей.
Именно это позволяет формализовать на
общей понятийной основе взаимосвязь
представлений информации в разных средах:
обеспечить контролируемое сведение бесконечного
разнообразия объектов и видов взаимосвязей
реального мира к жестко детерминированному
описанию—совокупности двоичных данныхи
машинно-ориентированных алгоритмов их
обработки. Выделение трех видов структур,
относящихся к представлению объектов
предметной области, имеет, в некотором
смысле, принципиальный характер. Структура информации — это неотъемлемое свойство
информации (сведений, сигналов, воспринимаемых
субъектом) о некоторой совокупности объектов
предметной области в контексте практической
задачи (решаемой субъектом), в общем случаебезучетатого,будутлидляеерешенияиспользованысредствапрограммированияивычислительныемашины.Структурированиеинформацииосуществляетсясистемныманалитикомисводится к выделениюоперационныхобъектов
и определению их характеристических
свойств и взаимосвязей. Структура данных — этоопределениеинформационныхмассивов(составаивзаимосвязейданныхналогическомуровне,соответствующих
характеру информации и видам соответствующих
преобразований). При определении структур
данных необходимо не только установить
состав массива, но и определить оптимальную
их взаимосвязь (и, соответственно, определить
критерии и методы оценки эффективности),
например, выделение групп или агрегатов,
имеющих иерархическую идентификацию.
Эффективность в этом случае связывается
с процессом построения программы («решателя»
прикладной задачи) и, в каком – то смысле
— с эффективностью работы программиста.
Например, при функциональной обработке
массива необходимо обращаться к отдельным
элементам, в то время как в операциях
присваивания или при записи массива в
файл поэлементное обращение приведет
к увеличению размера текста программы,
а в ряде случаев—к увеличению времени
выполнения. Структура записи — это определение структуры
физической памяти: выделение, освобождение
и защита областей физического носителя,
способы адресации и пересылки. Эффективность
в этом случае связывается с процессами
обмена между устройствами оперативной
и внешней памяти, искусственно вводимой
для обеспечения функциональной эффективности
отдельных операций (например, поиска
по ключам) посредством избыточности данных.
Рассмотрим разновидности и типологию
«компьютерных» логических структур данных
с точки зрения особенности их организации.
Структура здесь в первую очередь определяет
алгоритм выборки отдельных элементов
данных, но в то же время необходимо отметить,
что она отражает и особенности«технологии»организациииобработкиинформации,свойственныечеловекувегоповседневнойдеятельности.Физическипонятию структура соответствует записьданных. Записьэтоупорядоченнаявсоответствиисхарактеромвзаимосвязейсовокупность полей (элементов)данных,размещаемыхвпамятивсоответствиисих типом". Полепредставляетсобойминимальную адресуемую (идентифицируемую)
часть памяти — единицу данных, на которую
можно ссылаться при обращении к данным.
Таким образом, структура данных — это
способ отображениязначенийвпамяти:размеробластиипорядокеевыделения(которыйиопределитхарактерпроцедурыадресации/выборки).Зачастуюименноуспешностьструктурирования
данных определяет сложность процедур
их обработки. Классификация структур
данных должна проводиться с двух точек
зрения.
1. По характеру взаимосвязи элементов
структуры (с точки зрения порядка
их размещения/выборки) виды структур
можно разделить на линейные и нелинейные.
2. По характеру информации, представляемой
структурой (с точки зрения однородности
и «элементарности» типов данных, отражающих
понятийную структуру предметной области)
— на однородные структуры, где все элементы
находятся на одном понятийном уровне
и имеют один тип данных, и неоднородные
(композиционные), где элементы относятся к нескольким
понятийным уровням или имеют разную природу.
3.5.1. Линейные структуры.
К линейным структурам относятся массивы
и последовательности таблицы. Порядок
следования (и, соответственно, выборки)
элементов таких структур имеет
линейный характер и соответствует
порядку расположения элементов
в памяти: один за другим без каких-либо
промежутков. Адрес элемента соответствует
его положению и определяется
индексом — порядковым номером элемента
в последовательности размещения. К
элементу имеется прямой доступ, если
известен его индекс. Особенностью
линейной структуры является то, что
при последовательной организации
(размещении) она допускает возможность
прямого доступа к произвольному
элементу, поскольку условие однородности
(однотипности) предполагает, что все
элементы занимают расположенные строго
последовательно области одинакового
размера, что и позволяет достаточно
просто вычислять значение физического
адреса элемента по значению его индекса. Массив представляет
собой совокупность однотипных элементов,
причем число элементов массива известно
до его размещения, что позволяет строить
гибкие многомерные системы адресации. Последовательность, так
же, как и массив, представляет собой совокупность
однотипных элементов. Однако число элементов
до размещения неизвестно. И, хотя каждая
конкретная последовательность имеет
конечную длину, до начала обработки (и,
соответственно, размещения) необходимо
считать длину последовательности бесконечной.
Принципиальность такого предположения
выражается в том, что необходимо предусматривать
специальную процедуру использования
памяти (выделения/освобождения) и, возможно,
алгоритм обработки последовательности
по частям. Важность рассмотрения такого
типа данных обусловлена тем, что именно
он превалирует в операциях ввода/вывода
с устройствами внешней памяти. Именно
последовательный доступ позволяет организовать
«потоковые» операции : однородность позволяет
рассматривать пересылаемые данные как
непрерывный поток. Поток не может быть
прерван по контекстно определяемому
условию, например, при пересылке текста
— по значению кода «перевод строки»,
и это не заставляетпрограммуанализироватьзначениекаждогоочередногоэлемента.И,крометого,последовательныйдоступэтопростотауправленияпамятьюиустройствомвводавывода.Таблицаэтопоследовательности,обычнопредставляемыестроками—
совокупностями разнотипных элементов.
Или, иначе, таблица — это множество записей,
каждаяизкоторыхпредставляетнаборпоименованныхполей.Однакосточкизренияразмещенияэлементовтаблицаможетбытьпредставленакакодномерныймассив(или,вслучаеВДпоследовательность)соднороднымикомпозиционнымиэлементами,каждыйизкоторыхпредставляетсобойсовокупность
разнотипных элементов. Именно это позволяет
свести ввод/вывод таких джипов структур
к последовательным элементарным операциям.
Кроме того, разнотипность элементов позволяет
ввести отличную от перечислительной
схему идентификации записей, определив
одно из полей как ключ записи. Обычно
ключ содержит значение, используемое
в процедурах упорядочения и поиска записей.
3.5.2. Нелинейные структуры.
В качестве примеров нелинейных структур
рассмотрим списки, деревья и сети.
Порядок следования (и, соответственно,
выборки) элементов таких структур
может не соответствовать порядку
расположения элементов в памяти.
Списки представляют собой пример линейного
упорядочения, деревья — двумерного,
сети — произвольного. Соответственно
различаются методы и средства, обеспечивающие
последовательность выборкиэлементовданных.Обычнодляобеспечениявозможностипрямогодоступакпроизвольномуэлементунеобходимоиспользоватьвспомогательныеструктурытипаинвертированныхсписков. Какимассив, список представляет
собой совокупность однотипных элементов.
Однако порядок выборки элементов может
отличаться от порядка следования в памяти,
определенного при размещении. Наиболее
очевидный способ установления однонаправленного
порядка выборки элементов — это сопоставить
каждому элементу списка ссылку, указывающую
на следующий элемент. Соответственно,
для организации двунаправленного списка,
допускающего также выборку в обратном
порядке, каждый элемент должен иметь
ссылку на предыдущий. Такая организация
уже не допускает возможности прямого
доступа, например, по номеру элемента.
Кроме того, число элементов списка, как
и в случае последовательностей, может
быть неизвестно до размещения, и до начала
обработки (и, соответственно, размещения)
необходимо считать длину списка бесконечной,
что ведет к необходимостипредусматриватьспециальнуюпроцедурувыделения/освобожденияпамяти.Такимобразом,сточкизренияфизическойреализацииэлементспискадолженбыть составным, включающимсобственноинформативные
данные, несущие смысловое значение, и
дополнительные данные (ссылки), определяющие
порядок доступа к информативным элементам.
Понятие списка достаточно универсально.
В общем случае ссылки могут указывать
ответвления к другим спискам — подспискам. В зависимости от способа
построения списка и предполагаемых путей
доступа к элементам различают следующие
виды ссылок: перекрестные, боковые, иерархические,
множественные, что позволяет изменять
«естественный» последовательный порядок
прохода по элементам списка. Дерево (рис.
3.7) представляет собой иерархию элементов,
называемых узлами. На самомверхнемуровнеиерархииимеетсятолькоодинузелкорень.Каждыйузел,кромекорня,связансоднимузломнаболеевысокомуровне,называемым исходным узлом для данного узла.
Каждый элементимееттолько один исходный.
Каждый элемент может быть связан с одним
или несколькими элементами на более низком
уровне, которые называются порожденными. Элементы,
расположенные в конце ветви, т. е. не имеющие
порожденных, называются листьями. Существует
несколько способов представления структуры
дерева. Например, дерево может быть определено
как иерархия узлов с по парными связями,
в которой:1. Самый верхний уровень иерархии
имеет один узел, называемый корнем. 2. Все узлы,
кроме корня, связываются с одним и только
одним узлом на более высоком уровне по
отношению к ним самим. Такое определение
в части организации связей совпадает
со списком, и, в частности, список представляет
вырожденный случай дерева, в котором
каждаявершинаимеетнеболееодногоподдерева.Ещеразотметим,чтодеревьяздесьрассматриваютсякаксредствоидлялогического,идляфизическогопредставленияданных.Влогическомописанииданныхонииспользуютсядляопределениясвязеймеждуэлементамиструктуры,априопределениифизическойорганизацииданныхдляопределениянаборауказателей,
реализующих связи между ними. Использование
ссылок для организации доступа к отдельным
элементам структурынепозволяетсократить
процедуру поиска, в основу которой положен
последовательныйперебор.Процедурапоискабудетэффективнее,еслибудетпредварительноустановленнекоторыйпорядокпереходак следующемуэлементудерева.Такойпорядокврядеслучаевопределяетсявотношении методаобхода и регулярности итераций,определяемойдлинойпутиикратностьюделениявершины.Выделяют[2]триметодаобхода: сверхувниз,слеванаправо,снизувверх.Регулярностьобходадереваможетбытьсвязанас упорядоченнымидеревьями, ккоторымотносятся сбалансированные (рис.3.8)и двоичныедеревья (рис.3.9).Сбалансированноедерво вкаждомузлеимеетодинаковое число ветвей,причемпроцессвключенияновыхветвейвузлыдереваидетсверхувниз,анакаждомуровнедереваслеванаправо.Длядеревасфиксированнымчисломветвейфизическаяорганизацияданныхбудетболеепростой.Однакобольшаячастьлогическихорганизацийданыхнеможетбытьзаданаввидесбалансированной
древовидной структуры, и для их представления
требуется переменное число ветвей в каждом
узле. В то же время индексымогутбытьпостроеныввидесбалансированныхдреввидныхструктур.Двоичныедеревьяэтоособаякатегориясбалансированных
древовидных структур, в которой допускается
не более двух ветвей для одного узла.
На рис. 3.9 показано несбалансированное
двоичное дерево. Любые связи в дереве
можно представить в виде двоичных древовидных
структур. Рис. 3.10 иллюстрирует представление
дерева в виде двоичного дерева. При таком
представлении каждый элемент может иметь
указатели как на порожденные, так и на
подобные элементы. Различные виды двоичных
деревьев, для которых характерно наличие
жесткой схемы управления их ростом, достаточно
эффективно используются для построения
больших поисковых индексов, размещаемых
обычно на устройствах внешней памяти.
Кроме того, для таких деревьев можно организовать
специальное «страничное» хранение под
деревьев, что сократит число физических
обращений к устройству. Заметим, что деревья
по исковых индексов являются однородными структурами:
каждый узел представлен элементами одного
типа. Однако большинство баз должно поддерживать
организацию данных, имеющих различную
природу. В этом случае при работе с неоднородными
структурами разной глубины, гарантировать
регулярность, обеспечивающую эффективность
процедур доступа, становится затруднительно.
3.5.3.Сетевые структуры.
Иерархические структуры характерны
для многих областей, однако во многих
случаях отдельная запись требует
более одного представления или
связана с несколькими другими.
В результате получаются обычно более
сложные структуры по сравнению
с древовидными. Например, генеалогическое
дерево может быть представлено в виде
древовидной структуры, только если для
каждого элемента (личности) будет показан
только один исходный элемент (родитель).
Если бы были показаны оба родителя, то
это была бы более сложная структура. В
сетевой структуре любой элемент может
быть связан с любым другим элементом.
Примеры сетевых структур приведены на
рис. 3.11.Так же, как и в случае древовидных
структур, сетевую структуру можно описать
с помощью исходных и порожденных элементов.
Удобно представлять ее так, чтобы порожденные
элементы располагались ниже исходных.
При рассмотрении некоторых сетевых структур
естественно говорить об уровнях, так
же как и в случае древовидных структур.
Во многих сетевых структурах, задающих
связи между элементами, представление
отношений между исходными и порожденными
элементами аналогично представлению
отношений в случае дерева: отношение
исходный — порожденный является сложным
(указывается сдвоенными стрелками), а
отношение порожденный — исходный — простым
(указывается одинарными стрелками). На
рис. 3.12 показана неоднородная сетевая
структура с пятью типами элементов.
Ни одна из их соединяющих линий не имеет
сдвоенных стрелок в обоих направлениях.
Каждое отношение может рассматриваться
как отношение « исходный — порожденный».
Запись ЗАКАЗ-НА-ЗАКУПКУ является порожденной
по отношению к записи ИЗДЕЛИЕ и исходной
по отношению к записи ПАРТИЯ-ТОВАРА. на
закупку Желательно отличать структуры,
в которых представление отношений « порожденный
- исходный» является простым или не используется,отструктур,вкоторыхпредставлениеотношениймеждукакимитодвумятипамиданных является сложным в обоих направлениях.
Для структур второго типа на одной
из линий схемы будут сдвоенные
стрелки, указывающие в разные стороны.
Этот тип схемы назовем сложной сетевой
структурой, а схему, в которой ни на одной из
линий нет сдвоенных стрелок в обоих направлениях,
— простой сетевой структурой.
На рис. 3.12 показана простая сетевая структура.
Она станет сложной, если ввести отношение
ЗАКАЗ-НА-ЗАКУПКУ — ИЗДЕЛИЕ, когда один
заказ может быть сделан сразу на несколько
изделий. Для образования сложной сетевой
структуры достаточно двух типов элементов.
Например, ПОСТАВЩИК может иметь несколько
порожденных записей, потому что может
поставляться более одного вида изделий.
С другой стороны, элемент ИЗДЕЛИЕ может
иметьболееодногоисходногоэлемента,посколькуэтоизделиеможетпоставлятьсяразличнымипоставщиками.Внекоторыхслучаяходинэлементданныхможетбытьсвязансцелой совокупностью других
элементов данных. Например, одно изделие
может поставляться несколькими поставщиками,
каждый из которых установил свою ценунаэтоизделие.ЭлементданныхЦЕНАнеможетбытьассоциировантолькосэлементомИЗДЕЛИЕилитолькосэлементомПОСТАВЩИК,адолженбытьсвязанодновременносдвумя.Информациятакогорода,т.е.данные,ассоциированныессовокупностьюэлементов,называютиногда даннымипересечения. Некоторыеструктурысодержатциклы. Циклом считается ситуация,
в которой предшественник узла является
в то же время его последователем. Отношения
«исходный — порожденный» образуют при
этом замкнутый контур. Например, завод
выпускает различную продукцию. Некоторые
изделия производятся на других заводах-субподрядчиках.
С одним контрактомможетбытьсвязанопроизводствонесколькихизделий.Представлениеэтихотношенийиобразуетцикл. Иногдаэлементысвязанысдругимиэлементамитогожетипа.Такаяситуацияназывается петлей. Нарис.3.13 приведены
две достаточно распространенные ситуации,
где могут использоваться петли. В массиве
служащих специфицированы связи, существующие
между некоторыми служащими. В базу данных
списка материалов введено дополнительное
усложнение: некоторые узлы сами состоят
из узлов. Разделение сетевых структур
на простые и ,что сложные структуры
требуют более сложных методов физического представления.
Это не всегда является недостатком, поскольку
сложную сетевую структуру можно (а в большинстве
случаев и следует) преобразовать к простому
виду.