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

1 Интерфейсы 1 Интерфейс (англ. interface) совокупность линий связи, сигналов, посылаемых по этим линиям, технических средств, поддерживающих эти линии, и правил (протокола) обмена.англ. SATA (P)ATA Advanced Technology Attachment IDE, EIDE, UDMA, ATAPI Для подсоединения к 16 битной шине ISA (шина AT) 1986 Western digital IDE Integrated Drive Electronics контроллер канала IDE перешёл от прямого управления приводом к обмену данными с ним по протоколу

2 В стандарте АТА определён интерфейс между контроллером и накопителем, а также передаваемые по нему команды Принцип адресации CHS: Сперва блок головок устанавливается позиционером на требуемую дорожку (Cylinder), после этого выбирается требуемая головка (Head), а затем считывается информация из требуемого сектора (Sector). Стандарт EIDE (Enhanced IDE, т. е. «расширенный IDE»), преодолен порог 528 МБ (504 МиБ), расширен до 8,46 ГБ.МиБ переход от PIO (Programmed input/output, Программный ввод/вывод) к DMA (Direct memory access, Прямой доступ к памяти).PIO накопительпамять без CPU жёсткий диск сигнал DMARQ на операцию DMA контроллеру. Если операция DMA возможна, контроллер сигнал DMACK и жёсткий диск начинает выдавать данные в 1-й регистр (DATA), с которого контроллер считывает данные в память без участия процессора. 8 регистров, ширина шины 16 бит slave master

3 3 Архитектура с прямым доступом к памяти

4 Дорожки Секторы Минимальная порция Считывающие головки

5 5 С целью адресации пространства поверхности пластин диска делятся на дорожки концентрические кольцевые области. Каждая дорожка делится на равные отрезки секторы. Адресация CHS предполагает, что все дорожки в заданной зоне диска имеют одинаковое число секторов. Цилиндр совокупность дорожек, равноотстоящих от центра, на всех рабочих поверхностях пластин жёсткого диска. Номер головки задает используемую рабочую поверхность (то есть конкретную дорожку из цилиндра), а номер сектора конкретный сектор на дорожке.

6 6 Фрагмент дорожки диска (два сектора)

7 7 Методы записи Поверх ность диска Биты информации записываются с помощью маленькой головки, которая, проходя над поверхностью вращающегося диска, намагничивает миллиарды горизонтальных дискретных областей доменов.Битыдоменов 23 Гбит/см². Метод перпендикулярной записи это технология, при которой биты информации сохраняются в вертикальных доменах. Это позволяет использовать более сильные магнитные поля и снизить площадь материала, необходимую для записи 1 бита. магнитные поля 60 Гбит/см²

8 (АТА-3) UltraDMA 2 (UDMA 33). DMA Mode 2, данные передаются и по переднему, и по заднему фронту сигнала DIOR/DIOW. Это вдвое увеличивает скорость передачи данных по интерфейсу. Также введена проверка на чётность CRC. Оригинальная спецификация АТА предусматривала 28-битный режим адресации. 228 ( бит) секторов по 512 байт каждыйmax емкость 137 ГБ (128 ГиБ). PC BIOS поддерживал до 7,88 ГиБ (8,46 ГБ), допуская максимум 1024 цилиндра, 256 головок и 63 сектора.BIOS LBALBA (Logical Block Address), что позволило адресовать до 7,88 ГиБ. ограничение адресуемого пространства в 504 МиБ (528 МБ). Запись 28-битного числа организована путём записи его частей в соответствующие регистры накопителя (с 1 по 8 бит в 4-й регистр, 9-16 в 5-й, в 6-й и в 7-й). 32 ГиБ 128 ГиБ 28 разрядов (в АТА-4)АТА-4 0 ÷ бит 6 бит 10 бит

9 Версии стандарта ATA, скорость передачи и свойства Стандарт Другие названия Добавлены режимы передачи (MБ/с) Максимально поддерживаемый размер диска Другие свойстваANSI Reference ATA-1ATA, IDE PIOPIO 0,1,2 (3.3, 5.2, 8.3) Single-word DMA 0,1,2 (2.1, 4.2, 8.3) Multi-word DMA 0 (4.2) up to 137 GB28-bit LBA X X (obsolete since 1999) ATA-2 EIDE, Fast ATA, Fast IDE, Ultra ATA PIO 3,4: (11.1, 16.6) Multi-word DMA 1,2 (13.3, 16,6) X X (obsolete since 2001) ATA-3EIDE S.M.A.R.T.S.M.A.R.T., Security X X (obsolete since 2002) ATA/ATAPI-4 ATAPI-4, ATA-4, Ultra ATA/33 Ultra DMA 0,1,2 (16.7, 25.0, 33.3) aka Ultra-DMA/33 Support for CD-ROM, etc., via ATAPI packet commands NCITS ATA/ATAPI-5ATA-5, Ultra ATA/66 Ultra DMA 3,4 (44.4, 66.7) aka Ultra DMA wire cablesNCITS ATA/ATAPI-6ATA-6, Ultra ATA/100 UDMA 5 (100) aka Ultra DMA 100 up to 144 PB 48-bit LBA Automatic Acoustic Management NCITS ATA/ATAPI-7ATA-7, Ultra ATA/133 UDMA 6 (133) aka Ultra DMA 133 SATA/150 SATASATA 1.0, Streaming feature set, long logical/physical sector feature set for non- packet devices NCITS ATA/ATAPI-8ATA-8--in progress

10 SATA (англ. Serial ATA) последовательный интерфейс обмена данными с накопителями информации. SATA является развитием параллельного интерфейса ATA (IDE), который после появления SATA был переименован в PATA (Parallel ATA).англ.интерфейсATA Стандарт Частота шины Пропускная способность комментарий SATA/1501,5 ГГц ГГц 1,2 Гбит/с (150 МБ/с)ГбитсМБ система кодирования 8B/10B, на каждые 8 бит полезной информации 2 служебных бита) 8B/10B SATA/3003 ГГц ГГц 2,4 Гбит/с (300 МБ/с)SATA II SATA/6006 Гбит/с (600 МБ/с) SATA Revision 3.0 Разъёмы SATA G заземление (англ. Ground)англ. R зарезервировано D1+,D1,D2+,D2 два канала передачи данных (от контроллера к устройству и от устройства к контроллеру соответственно). Для передачи сигнала используется технология LVDS, провода каждой пары (D1+, D1 и D2+, D2) являются экранированными витыми парами.LVDSвитыми парами

11 eSATA (External SATA) интерфейс подключения внешних устройств, поддерживающий режим «горячей замены» (англ. Hot-plug). Был создан несколько позже SATA (в середине 2004).англ. Основные особенности eSATA: Разъёмы менее хрупкие и конструктивно рассчитаны на большее число подключений(~9000). Требует для подключения два провода: шину данных и кабель питания. В новых спецификациях планируется отказаться от отдельного кабеля питания для выносных eSATA-устройств. Длина кабеля увеличена до 2 м (по сравнению с 1 метровым у SATA). Средняя практическая скорость передачи данных выше, чем у USB или IEEE USBIEEE 1394 Существенно снижается нагрузка на центральный процессор.центральный процессор Уменьшены требования к сигнальным напряжениям по сравнению с SATA.

12 SCSI (англ. Small Computer System Interface) интерфейс, разработанный для объединения на одной шине различных по своему назначению устройств, таких как жёсткие диски, накопители на магнитооптических дисках, приводы CD, DVD, стримеры, сканеры, принтерыангл.интерфейсжёсткие дискиCDDVD стримерысканерыпринтеры SE (англ. single-ended) - ассиметричный SCSI, для передачи каждого сигнала используется отдельный проводник.англ. 50-контактный неэкранированный разъем для внутрисистемных соединений и аналогичный экранированный разъем типа Centronics (Alternative 2) для внешних подключений. Передача сигналов осуществляется 50 контактным кабелем типа - A-50 на 8 разрядной (битной) шине. LVD (англ. low-voltage-differential) интерфейс дифференциальной шины низкого напряжения, сигналы положительной и отрицательной полярности идут по разным физическим проводам - витой паре. На один сигнал приходится по одной витой паре проводников. Используемое напряжение при передаче сигналов ±1,8 В.англ. Для 8 битной шины предусматривался кабель типа A, который как и в SCSI-1 поддерживал 50-контактными разъемами типа D с уменьшенным шагом выводов (Alternative 1). Разъемы типа Centronics (Alternative 2) в SCSI-2 построенны 8 и 16 битной шине. Передача информации осуществляется по 68-контактным кабелям типа - A-68 и P- 68(Wide). Для 32 битной версии шины был предусмотрен тип кабеля B, который должен был параллельно подключаться одновременно с кабелем A в одно устройство. Однако кабель B не получил широкого признания и из стандарта SCSI-3 исключен. HVD (англ. high-voltage-differential) интерфейс дифференциальной шины высокого напряжения, отличается от LVD повышенным напряжением и специальными приемопередатчиками.англ. Кабеля A-68 и P-68 поддерживались экранированными, либо неэкранированными разъемами типа D. Кабеля в SCSI- 3 снабжены фиксаторами-защелками, а не проволочными кольцами, как разъемы Centronics. Начиная с этой версии SCSI в массивах накопителей используется 80-контактный разъем, называемый Alternative 4. Накопители с таким разъемом поддерживают "горячее" подключение устройств

13 Команды SCSI посылаются в виде блоков описания команды (англ. Command Descriptor Block, CDB). Длина каждого блока может составлять 6, 10, 12 или 16 байт. В последних версиях SCSI блок может иметь переменную длину. Блок состоит из однобайтового кода команды и параметров команды.англ. Все команды SCSI делятся на четыре категории: N (non-data), W (запись данных от инициатора целевым устройством), R (чтение данных) и B (двусторонний обмен данными). Всего существует порядка 60 различных команд SCSI, из которых наиболее часто используются: Test unit ready проверка готовности устройства, в т.ч. наличия диска в дисководе. Inquiry запрос основных характеристик устройства. Send diagnostic указание устройству провести самодиагностику и вернуть результат. Request sense возвращает код ошибки предыдущей команды. Read capacity возвращает ёмкость устройства. Format Unit Read (4 варианта) чтение. Write (4 варианта) запись. Write and verify запись и проверка. Mode select установка параметров устройства. Mode sense возвращает текущие параметры устройства. Каждое устройство на SCSI-шине имеет как минимум один номер логического устройства (LUN англ. Logical Unit Number). В некоторых более сложных случаях одно физическое устройство может представляться набором LUN.англ.

14 Обзор интерфейсов SCSI Наименование Разрядность шины Частота шины Пропускная способность Максимальная длина кабеля Максимальное количество устройств SCSI8 бит 5 МГц 5 МБайт/сек 6 м 8 Fast SCSI8 бит 10 МГц 10 МБайт/сек 1,5-3 м 8 Wide SCSI16 бит 10 МГц 20 МБайт/сек 1,5-3 м 16 Ultra SCSI8 бит 20 МГц 20 МБайт/сек 1,5-3 м 5-8 Ultra Wide SCSI16 бит 20 МГц 40 МБайт/сек 1,5-3 м 5-8 Ultra2 SCSI8 бит 40 МГц 40 МБайт/сек 12 м 8 Ultra2 Wide SCSI 16 бит 40 МГц 80 МБайт/сек 12 м 16 Ultra3 SCSI16 бит 40 МГц DDR160 МБайт/сек 12 м 16 Ultra-320 SCSI16 бит 80 МГц DDR320 МБайт/сек 12 м 16

15 Serial Attached SCSI Интерфейс SAS (англ. Serial Attached SCSI) обеспечивает подключение по физическому интерфейсу, аналогичному SATA, устройств, управляемых набором команд SCSI. Обладая обратной совместимостью с SATA, он даёт возможность подключать по этому интерфейсу любые устройства, управляемые набором команд SCSI не только НЖМД, но и сканеры, принтеры и др. По сравнению с SATA, SAS обеспечивает более развитую топологию, позволяя осуществлять параллельное подключение одного устройства по двум или более каналам.SASангл.SCSIНЖМДсканеры принтеры Также поддерживаются расширители шины, позволяющие подключить несколько SAS устройств к одному порту. SAS и SATA2 в первых редакциях были синонимами. Но, позже производители посчитали, что реализовывать SCSI полностью в настольных компьютерах нецелесообразно, поэтому мы сейчас наблюдаем такое разделение. К слову, такие высокие скорости, заложенные в стандарте SATA на первый взгляд могут показаться излишними обычный SATA HDD (Hard Disk Drive жёсткий диск) использует, в лучшем случае, % пропускной способности шины. Однако работа с буфером винчестера происходит на полной скорости интерфейса.

16 Типичная система с интерфейсом SAS состоит из следующих компонентов: Инициаторы (англ. Initiators)англ. Инициатор устройство, которое порождает запросы на обслуживание для целевых устройств и получает подтверждения по мере исполнения запросов. Целевые устройства (англ. Targets)англ. Целевое устройство содержит логические блоки и целевые порты, которые осуществляют приём запросов на обслуживание, исполняет их; после того, как закончена обработка запроса, инициатору запроса отсылается подтверждение выполнения запроса. Целевое устройство может быть как отдельным жёстким диском, так и целым дисковым массивом. Подсистема доставки данных (англ. Service Delivery Subsystem)англ. Является частью системы ввода-вывода, которая осуществляет передачу данных между инициаторами и целевыми устройствами. Обычно подсистема доставки данных состоит из кабелей, которые соединяют инициатор и целевое устройство. Дополнительно, кроме кабелей в состав подсистемы доставки данных могут входить расширители SAS. Расширители (англ. Expanders)англ. Расширители SAS устройства, входящие в состав подсистемы доставки данных и позволяют облегчить передачи данных между устройствами SAS, например, позволяет соединить несколько целевых устройств SAS к одному порту инициатора. Подключение через расширитель является абсолютно прозрачным для целевых устройств.

17 17 RAID

18 18 RAID

19 RAID (англ. redundant array of independent/inexpensive disks) избыточный массив независимых/недорогих жёстких дисков матрица из нескольких дисков управляемых контроллером, взаимосвязанных скоростными каналами и воспринимаемых как единое целое. Обеспечивает отказоустойчивость, в случае повреждения одного из дисков, восстановление данных на нём происходит автоматически.англ. массивжёстких дисковматрица Калифорнийский университет в Беркли Калифорнийский университет в Беркли представил следующие уровни спецификации RAID, которые были приняты как стандарт де-факто: RAID 0 представлен как неотказоустойчивый дисковый массив. RAID 0 («Striping») дисковый массив из двух или более жёстких дисков с отсутствием избыточности. Информация разбивается на блоки данных (Ai) и записывается на оба/несколько дисков одновременно.жёстких дисков (+): За счёт этого существенно повышается производительность (от количества дисков зависит кратность увеличения производительности). (+): RAID 0 может быть реализован как программно, так и аппаратно. (): Страдает надёжность всего массива (при выходе из строя любого из входящих в RAID 0 винчестеров полностью и безвозвратно пропадает вся информация). В соответствии с теорией вероятностей, надёжность массива RAID 0 равна произведению вероятностей безотказной работы составляющих его дисков, каждая из которых меньше единицы, таким образом совокупная надёжность заведомо ниже надёжности любого из дисков.

20 20

21 RAID 1 определён как зеркальный дисковый массив. (+): Обеспечивает приемлемую скорость записи и выигрыш по скорости чтения при распараллеливании запросов. (+): Имеет высокую надёжность работает до тех пор, пока функционирует хотя бы один диск в массиве. (-): Недостаток заключается в том, что приходится выплачивать стоимость двух жёстких дисков, получая полезный объем одного жёсткого диска (классический случай, когда массив состоит из двух дисков).

22 RAID

23

24

25 25

26 RAID 2 зарезервирован для массивов, которые применяют код Хемминга. код Хемминга В массивах такого типа диски делятся на две группы для данных и для кодов коррекции ошибок, причем если данные хранятся на n дисках, то для складирования кодов коррекции необходимо n 1 дисков. Данные записываются на соответствующие винчестеры так же, как и в RAID 0, они разбиваются на небольшие блоки по числу дисков, предназначенных для хранения информации. Оставшиеся диски хранят коды коррекции ошибок, по которым в случае выхода какого-либо винчестера из строя возможно восстановление информации. Метод Хемминга давно применяется в памяти типа ECC и позволяет на лету исправлять однократные и обнаруживать двукратные ошибки.ECC

27 27

28 28

29 29

30 RAID 3, 4, 5 используют чётность для защиты данных от одиночных неисправностей. Структура массива RAID 3 такова: в массиве из n дисков данные разбиваются на блоки размером 1 байт и распределяются по n 1 дискам, а еще один диск используется для хранения блоков четности. В RAID 2 для этой цели стояло n 1 дисков, но большая часть информации на этих дисках использовалась только для коррекции ошибок на лету, а для простого восстановления в случае поломки диска достаточно меньшего ее количества, хватает и одного выделенного винчестера. Соответственно, отличия RAID 3 от RAID 2 очевидны: невозможность коррекции ошибок на лету и меньшая избыточность. (+): скорость чтения и записи данных высока, а для создания массива требуется совсем немного дисков, всего три. (-): массив этого типа хорош только для однозадачной работы с большими файлами, так как наблюдаются проблемы со скоростью при частых запросах данных небольшого обьёма. (-): большая нагрузка на контрольный диск, что приводит к тому, что его надёжность сильно падает по сравнению с дисками с данными. RAID 4 похож на RAID 3, но отличается от него тем, что данные разбиваются на блоки, а не на байты. Таким образом, удалось «победить» проблему низкой скорости передачи данных небольшого объема. Запись же производится медленно из-за того, что четность для блока генерируется при записи и записывается на единственный диск. Используются массивы такого типа очень редко

31 Большой недостаток уровней RAID от 2-го до 4-го это наличие отдельного диска (или дисков), хранящего информацию о четности. Скорость выполнения операций считывания достаточно высока, так как не требует обращения к этому диску. Но при каждой операции записи на нем изменяется информация, поэтому схемы RAID 24 не позволяют проводить параллельные операции записи. RAID5 не имеет этого недостатка. Блоки данных и контрольные суммы циклически записываются на все диски массива, отсутствует выделенный диск для хранения информации о четности, нет асимметричности конфигурации дисков. Самый популярный из уровней, в первую очередь благодаря своей экономичности. Жертвуя ради избыточности ёмкостью всего одного диска из массива, мы получаем защиту от выхода из строя любого из винчестеров тома. На запись информации на том RAID5 тратятся дополнительные ресурсы, так как требуются дополнительные вычисления, зато при чтении (по сравнению с отдельным винчестером) имеется выигрыш, потому что потоки данных с нескольких накопителей массива распараллеливаются

32 RAID 6 используют чётность для защиты данных от двойных неисправностей Большой недостаток уровней RAID от 2-го до 4-го это наличие отдельного диска (или дисков), хранящего информацию о четности. Скорость выполнения операций считывания достаточно высока, так как не требует обращения к этому диску. Но при каждой операции записи на нем изменяется информация, поэтому схемы RAID 24 не позволяют проводить параллельные операции записи. RAID5 не имеет этого недостатка. Блоки данных и контрольные суммы циклически записываются на все диски массива, отсутствует выделенный диск для хранения информации о четности, нет асимметричности конфигурации дисков. Самый популярный из уровней, в первую очередь благодаря своей экономичности. Жертвуя ради избыточности ёмкостью всего одного диска из массива, мы получаем защиту от выхода из строя любого из винчестеров тома. На запись информации на том RAID5 тратятся дополнительные ресурсы, так как требуются дополнительные вычисления, зато при чтении (по сравнению с отдельным винчестером) имеется выигрыш, потому что потоки данных с нескольких накопителей массива распараллеливаются RAID 6 (Advanced Data Guarding) похож на RAID 5, но имеет более высокую степень надежности под контрольные суммы выделяется емкость 2-х дисков, рассчитываются 2 суммы по разным алгоритмам. Требует более серьезный процессор контроллера сложная материнская плата. Обеспечивает работоспособность после «смерти» одновременно 2-х дисков. Для организации массива требуется минимум 4 диска.

33 RAID 7 зарегистрированная марка компании Storage Computer Corporation. Структура массива такова: на n 1 дисках хранятся данные, один диск используется для складирования блоков четности. Но добавилось несколько важных деталей, призванных ликвидировать главный недостаток массивов такого типа: кэш данных и быстрый контроллер, заведующий обработкой запросов. Это позволило снизить количество обращений к дискам для вычисления контрольной суммы данных. В результате удалось значительно повысить скорость обработки данных (кое-где в пять и более раз).Storage Computer Corporation Помимо базовых уровней RAID 0 RAID 5, описанных в стандарте, существуют комбинированные уровни RAID 1+0, RAID 3+0, RAID 5+0, RAID 1+5, которые различные производители интерпретируют каждый по-своему. RAID 1+0 это сочетание зеркалирования и чередования. Нынешние контроллеры используют этот режим по умолчанию для RAID 1. То есть, 1 диск основной, 2-й диск зеркало, причем чтение производится с них поочередно, как для RAID 0. Собственно, сейчас можно считать что RAID 1 и RAID 1+0 это просто разное название одного и того же метода аппаратного зеркалирования дисков. Но не стоит забывать, что полноценный RAID 1+0 должен содержать как минимум 4 диска. RAID 5+0 это чередование томов 5-го уровня. RAID 1+5 зеркалирование «пятерок». И так далее.

34 34 RAID Redundant Array of Inexpensive Disks

35 35 RAID Redundant Array of Inexpensive Disks

36 Схема Intel Matrix RAIDIntel Matrix RAID это технология, реализованная фирмой Intel в своих чипсетах начиная с ICH6R. Строго говоря, эта технология не является новым уровнем RAID (ее аналог существует в аппаратных RAID-контроллерах высокого уровня), она лишь позволяет, используя лишь 2 диска, организовать одновременно один или несколько массивов уровня RAID 1 и один или несколько массивов уровня RAID 0. Это позволяет за сравнительно небольшие деньги обеспечить для одних данных повышенную надёжность, а для других высокую скорость доступа.IntelчипсетахICH6R Пример использования: Имеются в наличии два диска по 160 Гбайт. Каждый диск разбивается на тома по 60 и по 100 Гбайт, затем 100-гигабайтные тома объединяются в скоростной массив RAID 0, а 60-гигабайтные в массив повышенной надежности RAID 1. В массиве RAID 1 можно разместить операционную систему, рабочие документы, фото- и видеоархивы, коллекцию mp3 и прочие важные данные, а файл подкачки и «игрушки» в массиве RAID 0. В результате получается весьма рациональное сочетание повышенной производительности и надежности хранения данных.

37 37 Пример использования: Имеются в наличии два диска по 160 Гбайт. Каждый диск разбивается на тома по 60 и по 100 Гбайт, затем 100-гигабайтные тома объединяются в скоростной массив RAID 0, а 60-гигабайтные в массив повышенной надежности RAID 1. В массиве RAID 1 можно разместить операционную систему, рабочие документы, фото- и видеоархивы, коллекцию mp3 и прочие важные данные, а файл подкачки и «игрушки» в массиве RAID 0. В результате получается весьма рациональное сочетание повышенной производительности и надежности хранения данных. Интересные факты Сотрудник корпорации Y-E Data, которая является крупнейшем в мире производителем USB флоппи-дисководов, Дэниэл Олсон в качестве эксперимента создал RAID-массив флоппи-дисководов.Y-E DataUSBфлоппи-дисководовRAID-массив флоппи-дисководов

38 Программный RAID 38 Ядро GNU/Linux (последнее из вышедших в 2008 году) поддерживает программные RAID следующих уровней: 0, 1, 4, 5, 6, 10. ОС Windows 2000/XP/2003 поддерживает программный RAID 0, RAID 1 и RAID 5. Более точно, Windows XP Pro поддерживает RAID 0. Поддержка RAID 1 заблокирована разработчиками, но, тем не менее, может быть включена, путем редактирования системных бинарных файлов ОС.[1] Windows Server , 1 и 5. Windows XP Home RAID не поддерживает.Windows 2000XP2003[1] В ОС FreeBSD есть несколько реализаций программного RAID. Так, atacontrol, может как полностью строить программный RAID, так и может поддерживать полу аппаратный RAID на таких чипах как ICH5R. Во FreeBSD, начиная с версии 5.0, дисковая подсистема управляется встроенным в ядро механизмом GEOM.FreeBSD

39 Ошибки Память компьютера время от времени может делать ошибки из-за всплесков напряжения на линии электропередачи или по другим причинам. Для борьбы с такими ошибками используются коды с обнаружением и исправлением ошибок. При этом к каждому слову в памяти особым образом добавляются дополнительные биты. Когда слово считывается из памяти, эти биты проверяются на наличие ошибок.

40 Ричард Хэмминг Ричард Уэсли Хэмминг (11 февраля 1915, Чикаго 7 января 1998, Монтеррей) американский математик, работы которого в сфере теории информации оказали существенное влияние на компьютерные науки и телекоммуникации. Основной вклад т. н. код Хэмминга, а также расстояние Хэмминга. Хэмминг родился в Чикаго. Он получил степень бакалавра в Чикагском университете в 1937 году. Затем он продолжил образование в Университете Небраска и в 1939 году получил там степень магистра. В 1942 году он защищает диссертацию в университете Иллинойс и становится доктором философии. Некоторое время числится профессором в Университете Луисвилль, где прерывает работу для участия в Манхэттенском проекте в В рамках этого проекта Хэмминг занимается программированием одного из первых электронных цифровых компьютеров для расчета решения физических уравнений. Цель программы состояла в том, чтобы выяснить, не приведет ли взрыв атомной бомбы к возгоранию атмосферы. Ответ оказался отрицательным, вследствие чего было принято решение об её использовании. В период с 1946 по 1976 года Хэмминг работал в Bell Labs, где сотрудничал с Клодом Шенноном. 23 июля 1976 года он переехал в Монтеррей и возглавил там научные исследования в области вычислительной техники в Высшем военно-морском училище. Скончался 7 января 1998 года в возрасте 82 лет. В его честь Институт инженеров по электротехнике и электронике учредил медаль, которой награждаются ученые, внесшие значительный вклад в теорию информации медаль Ричарда Хэмминга.11 февраля 1915Чикаго 7 января 1998Монтеррейамериканский математиктеории информации компьютерные наукителекоммуникациикод Хэммингарасстояние Хэмминга ЧикагобакалавраЧикагском университете Университете Небраска магистрауниверситете Иллинойсдоктором философии Университете Луисвилль Манхэттенском проекте 1945 программированиемкомпьютеров атомной бомбыатмосферыBell Labs Клодом Шенноном 23 июля 1976 года Монтеррей вычислительной техники Высшем военно-морском училище 7 января Институт инженеров по электротехнике и электроникемедаль Ричарда Хэмминга

41 41 Код Хэмминга

42 Допустим, что слово состоит из m бит данных, к которым мы добавляем r бит контрольных разрядов. Тогда единицу размером n бит (n = m + r), содержащую m бит данных и r бит контрольных разрядов, будем называть кодированным словом. Для любых двух слов можно определить, сколько соответствующих битов в них различается. Для этого применяется операция XOR и считается кол-во единиц в результате. Число битовых позиций по которым различаются два слова называется интервалом Хэмминга.

43 правильное неправильное

44 Смысл интервала Хэмминга Если интервал Хэмминга для двух слов равен d, это значит, что достаточно d битовых ошибок, чтобы превратить одно слово в другое. Пример: XOR = => d = 3

45 Интервал Хэмминга полного кода Для памяти из m-битных слов существует 2 m вариантов сочетания битов. Кодированные слова состоят из n битов, но из-за способа подсчета контрольных разрядов допустимы только 2 m из 2 n комбинаций. Если получилось значение с недопустимой комбинацией контрольных разрядов, то сразу известно, что произошла ошибка. Зная алгоритм подсчета контрольных разрядов, мы можем найти все возможные комбинации кодированных слов и вычислить для них минимальный интервал Хэмминга. Т.е. выбрать минимум из всех интервалов Хэмминга для каждой пары кодированных слов. Этот интервал назовем интервалом Хэмминга полного кода.

46 Алгоритм для обнаружения и исправления одиночной ошибки Попробуем придумать алгоритм для обнаружения и исправления одиночной ошибки в произвольном коде при параметрах n = m + r. Для каждого из 2 m допустимых значений кода есть n возможных одиночных ошибок => n + 1 сочетание на слово. (n + 1)*2 m должно быть 2 n (чтобы каждая ошибка была уникальной комбинацией и мы могли бы разгадать ее изначальное представление) => (m+r+1) 2 r. Таким образом мы получаем нижний предел числа контрольных разрядов.

47 Значения нижнего предела Размер слова Количество контрольных разрядов Общий размер %-ное увеличение длины слова

48 Смысл интервала Хэмминга полного кода От этой величины зависят свойства проверки и исправления ошибок кода. Чтобы обнаружить d ошибок в битах необходим код с интервалом Хэмминга d + 1 (так как d ошибок не смогут изменить одно допустимое слово на другое). Соответственно, чтобы исправить d ошибок надо чтобы интервал Хэмминга кода был 2d + 1 (так как даже при d изменениях кодированное слово будет ближе к изначальному, чем к какому-либо другому слову).

49 Примеры Пример 1: код с битом четности. Пример 2: код с четырьмя возможными значениями d = 2 => можем обнаружить одиночную ошибку d = 5 => можем обнаружить до 4-х ошибок и исправить две.

50 Логические основы компьютеров 50 Диаграммы Венна (круги Эйлера) A B A B A A·BA·B A B A+B A B A B A B

51 Логические основы компьютеров 51 Диаграмма с тремя переменными Х очу М огу Н адо Логические выражения можно упрощать! !

52 Метод Ричарда Хэмминга Диаграмма Вена

53 Контроль чётности (a) Кодирование 1100 (b) Добавление Контроля Чётности (c) Суммы одинаковы - 2 (d) Ошибка в AC 4 бит данных 3 бит четности Единственный способ исправить ошибку – возвратить значение 0 биту в секторе АС

54

55