ГЛАВА 1. АНАЛИЗ ТЕХНОЛОГИЙ ВОССТАНОВЛЕНИЯ ИНФОРМАЦИИ В СОВРЕМЕННЫХ СИСТЕМАХ ХРАНЕНИЯ ДАННЫХ
Система хранения данных (СХД) представляет собой конгломерат программного обеспечения и специализированного оборудования, предназначенный для хранения и передачи информации больших объемов. Особенностью СХД является оптимальное распределение ресурсов при хранении информации на дисковых площадках.
Надежное хранение данных и быстродействие доступа к ним требуют организации средств хранения, как отдельной подсистемы вычислительных комплексов. Эта подсистема должна быть грамотно спроектирована и внедрена, чтобы обеспечить возможность восстановления утраченных данных.
СХД должна быть масштабируемой, то есть гибкой, отказо и катастрофоустойчивой. Необходимо обеспечивать ее соответствие стандартам и требованиям информационной и физической безопасности.
В случаях, когда требуется хранение больших объемов данных, важно не просто создать СХД, но и сделать ее оптимальной для решения конкретных задач. СХД состоит из накопителей информации, серверов, инфраструктуры, обеспечивающей связь между ними, и системы управления.
Так была создана технология RAID. Это технология объединения двух и более накопителей в единый логический элемент с целью повышения производительности и отказоустойчивости отдельно взятого элемента массива. Так же рассмотрим методы кодирования, используемые в этих системах.
Свойства различных методов помехоустойчивого кодирования
К настоящему времени разработано много различных помехоустойчивых кодов, отличающихся друг от друга основанием, расстоянием, избыточностью, структурой, функциональным назначением, энергетической эффективностью, корреляционными свойствами, алгоритмами кодирования и декодирования, формой частотного спектра. На рисунке, представленном выше, приведены типы кодов, различающиеся по особенностям структуры, функциональному назначению, физическим свойствам кода как сигнала.
Рисунок 1.1. Классификация помехоустойчивых кодов
Наиболее важный подкласс непрерывных кодов образуют сверточные коды, отличающиеся от других непрерывных кодов методом построения и более широкой областью применения.
В общем случае, чем длиннее код при фиксированной избыточности, тем больше расстояние и тем выше помехоустойчивость кода. Однако длинные коды сложно реализуются. Составные коды дают компромиссное решение задачи; из них основное значение имеют каскадные коды и коды произведения. Как правило, каскадный код состоит из двух ступеней (каскадов): внутренней и внешней. По линии связи сигналы передают внутренним кодом nвт, символьные слова которого являются символами внешнего кода длины nвш. Основание внешнего кода равно qвтk.
Коды произведения строят в виде матрицы, в которой строки суть слова одного кода, а столбцы - того же или другого кода.
При формировании каскадного кода входную информационную последовательность символов разбивают на блоки по kвт символов в каждом, каждый блок сопоставляют с информационным символом внешнего кода из алфавита, содержащего qвтk значений символов. Затем kвш информационных символов внешнего кода преобразуют в блоки из nвш символов внешнего кода и, наконец, блоки из kвт информационных символов внутреннего кода преобразуют в блоки из nвт символов внутреннего кода. Возможны различные варианты: внешний и внутренний коды - блочные, внешний блочный - внутренний сверточный, внешний сверточный - внутренний блочный, внешний и внутренний сверточные.
Один из наиболее распространенных методов формирования кода произведения заключается в последовательной записи по k1 символов входной информационной последовательности в k2 строк матрицы (например, в ячейки памяти ОЗУ), добавлении избыточных символов по n1-k1 в каждую строку и по n2-k2 в каждый столбец, после чего в последовательность символов кода считывают по строкам или столбцам из матрицы. Физическим аналогом кода произведения является, в частности, частотно-временной код, у которого строки располагаются вдоль оси времени, а столбцы - по оси частот.
Параметры составных кодов: каскадных - n=nвшnвт, k=kвшkвт, d=dвшdвт; произведения - n=n1n2, k=k1k2, d=d1d2.
Производные коды строят на основе некоторого исходного кода, к которому либо добавляют символы, увеличивая расстояние (расширенный код), либо сокращают часть информационных символов без изменения расстояния (укороченный код), либо выбрасывают (выкалывают) некоторые символы (выколотый, или перфорированный код). Код Хэмминга дает пример процедуры расширения, увеличивающей расстояние кода с 3 до 4. Необходимость в выкалывании возникает в результате построения на основе исходного кода другого, менее мощного, более короткого кода с тем же расстоянием.
При более широкой трактовке термина "производный код" к этому классу можно отнести все коды, полученные из исходного добавлением или исключением как символов, так и слов.
Формально деление кодов на двоичные и недвоичные носит искусственный характер; по аналогии следует выделять троичные, четверичные и другие коды большего основания. Оправдывается такое деление усложнением алгоритмов построения, кодирования и декодирования недвоичных кодов.
При прочих равных условиях желательно, чтобы информационные и избыточные символы располагались отдельно. В систематических кодах это условие выполняется.В циклических кодах каждое слово содержит все свои циклические перестановки. Все n циклических перестановок (слова длины n) образуют цикл. В квазициклических кодах цикл образуется на числе символов n-1 или, реже, n-2. Циклические коды важны как с точки зрения математического описания, так и для построения и реализации кода.
Ошибки в каналах связи имеют самое различное распределение, однако для выбора помехоустойчивого кода целесообразно разделить все возможные конфигурации ошибок на независимые (некоррелированные) и пакеты (коррелированные ошибки). На практике приходится учитывать качество интервалов между пакетами: они могут быть свободными от ошибок или же содержать случайные независимые ошибки.
Под корреляционными подразумевают коды, обладающие хорошими корреляционными свойствами, важными при передаче сигналов вхождения в связь, для повышения защищенности от некоторых видов помех, извлечения сигналов из интенсивных шумов, обеспечения многостанционного доступа, построения асинхронно-адресных систем связи. Корреляционные коды включают в себя пары противоположных сигналов с хорошей функцией автокорреляции (метод внутриимпульсной модуляции), импульсно-интервальные коды, имеющие на фиксированном интервале времени постоянное для всех слов кода число импульсов с неперекрывающимися (при любом взаимном сдвиге слов во времени) значениями интервалов между импульсами, ансамбли сигналов с хорошими взаимокорреляционными свойствами.
Особый класс образуют частотно-компактные коды, предназначенные для сосредоточения энергии сигнала в возможно более узкой полосе частот. Столь общая постановка задачи понимается в различных системах связи по-разному: в проводных линиях и линейных трактах, содержащих полосно-ограничивающие фильтры с крутыми фронтами, необходимо основную энергию сигналa "отодвинуть" от крайних частот к центру полосы пропускания целью уменьшения межсимвольных искажений; в сетях радиосвязи с жесткими ограничениями по электромагнитной совместимости радиосредств от кода требуется значительно (на десятки децибел) уменьшить уровень внеполосных излучений. Построение кодирование и декодирование частотно-компактных кодов существенно зависят от метода модуляции.
Арифметические коды служат для борьбы с ошибками при вы полнении арифметических операций в процессоре ЭВМ.
Далее рассматриваются два типа кодов: блоковые и древовидные. Определяющее различие между кодерами для кодов этих двух типов состоит в наличии или отсутствии памяти. Кодер для блокового кода является устройством без памяти, отображающим последовательности из k входных символов в последовательности из n выходных символов. Термин "без памяти" указывает, что каждый блок из n символов зависит только от соответствующего блока из k символов и не зависит от других блоков. Это не означает, что кодер не содержит элементов памяти. Важными параметрами блокового кода являются n, k, R=k/n и dmin. На практике значения k лежат между 3 и несколькими сотнями, a R= =1/4 ...7/8. Значения, лежащие вне этих пределов, являются возможными, но часто приводят к некоторым практическим трудностям. Входные и выходные последовательности обычно состоят из двоичных символов, но иногда могут состоять из элементов некоторого алфавита большего объема. Кодер для древовидного кода является устройством с памятью, в которое поступают наборы из m двоичных входных символов, а на выходе появляются наборы из n двоичных выходных символов. Каждый набор n выходных символов зависит от текущего входного набора и от v предыдущих входных символов. Таким образом, память кодера должна содержать v+m входных символов. Параметр v+m часто называют длиной кодового ограничения данного кода и обозначают k=v+m (не следует путать с параметром k для блокового кода). Отметим, что обозначения часто не согласуются друг с другом. Некоторые авторы называют длиной кодового ограничения параметр k, в то время как другие - параметр v. Здесь длиной кодового ограничения будем называть величину v, поскольку это приводит к меньшей путанице для кодов с m>1. Параметр k=v+m почти не будет использоваться. Древовидные коды характеризуются также скоростью R=m/n и свободным расстоянием dсв. Точное определение dсв более громоздко, чем определение dmin для блоковых кодов, однако параметр dсв, по существу, содержит ту же информацию о коде, что и dmin. Типичные значения параметров древовидных кодов таковы: m, n=1...8, R= 1/4... 7/8, v=2...60.
При другом подходе коды можно разделить на линейные и нелинейные. Линейные коды образуют векторное пространство и обладают следующим важным свойством: два кодовых слова можно сложить, используя подходящее определение суммы, и получить третье кодовое слово. В случае обычных двоичных кодов эта операция является посимвольным сложением двух кодовых слов по модулю 2 (т. е. 1+1=0, 1+0=1, 0+0=0). Это свойство приводит к двум важным следствиям. Первое из них состоит в том, что линейность существенно упрощает процедуры кодирования и декодирования, позволяя выразить каждое кодовое слово в виде "линейной" комбинации небольшого числа выделенных кодовых слов, так называемых базисных векторов. Второе свойство состоит в том, что линейность существенно упрощает задачу вычисления параметров кода, поскольку расстояние между двумя кодовыми словами при этом эквивалентно расстоянию между кодовым словом, состоящим целиком из нулей, и некоторым другим кодовым словом. Таким образом, при вычислении параметров линейного кода достаточно рассмотреть, что происходит при передаче кодового слова, состоящего целиком из нулей. Вычисление параметров упрощается еще и потому, что расстояние Хемминга между данным кодовым словом и нулевым кодовым словом равно числу ненулевых элементов данного кoдового слова. Это число часто называют весом Хемминга данного слова, и список, содержащий число кодовых слов каждого веса, можно использовать для вычисления характеристик кода с помощью аддитивной границы. Такой список называют спектром кода.
Линейные коды отличаются от нелинейных замкнутостью кодового множества относительно некоторого линейного оператора, например сложения или умножения слов кода, рассматриваемых как векторы пространства, состоящего из кодовых слов - векторов. Линейность кода упрощает его построение и реализацию. При большой длине практически могут быть использованы только линейные коды. Вместе с тем часто нелинейные коды обладают лучшими параметрами по сравнению с линейными. Для относительно коротких кодов сложность построения и реализации линейных и нелинейных кодов примерно одинакова.
Как линейные, так и нелинейные коды образуют обширные классы, содержащие много различных конкретных видов помехоустойчивых кодов. Среди линейных блочных наибольшее значение имеют коды с одной проверкой на четность, M-коды (симплексные), ортогональные, биортогональные, Хэмминга, Боуза-Чоудхури-Хоквингема, Голея, квадратично-вычетные (KB), Рида-Соломона. К нелинейным относят коды с контрольной суммой, инверсные, Нордстрома-Робинсона (HP), с постоянным весом, перестановочные с повторением и без повторения символов (полные коды ортогональных таблиц, проективных групп, групп Матье и других групп перестановок).
Почти все схемы кодирования, применяемые на практике, основаны на линейных кодах. Двойные линейные блоковые коды часто называют групповыми кодами, поскольку кодовые слова образуют математическую структуру, называемую группой. Линейные древовидные коды обычно называют сверточными кодами, поскольку операцию кодирования можно рассматривать как дискретную свертку входной последовательности с импульсным откликом кодера.
Наконец, коды можно разбить на коды, исправляющие случайные ошибки, и коды, исправляющие пакеты ошибок. В основном мы будем иметь дело с кодами, предназначенными для исправления случайных, или независимых, ошибок. Для исправления пакетов ошибок было создано много кодов, имеющих хорошие параметры. Однако при наличии пачек ошибок часто оказывается более выгодным использовать коды, исправляющие случайные ошибки, вместе с устройством перемежения восстановления. Такой подход включает в себя процедуру перемешивания порядка символов в закодированной последовательности перед передачей и восстановлением исходного порядка символов после приема с тем, чтобы рандомизировать ошибки, объединенные в пакеты.
1.1.1 Блочные коды
Важное семейство кодов образуют линейные двоичные блочные коды. Эти коды замечательны тем, что представляя информационные и кодовые слова в форме двоичных векторов, мы можем описать процессы кодирования и декодирования с помощью аппарата линейной алгебры, при этом компонентами вводимых векторов и матриц являются символы 0 и 1. Операции над двоичными компонентами производятся по правилам двоичной арифметики. Кодер двоичного блочного (n, k) – кода отображает множество 2 k возможных двоичных информационных слов в множество 2 k n – мерных кодовых слов. Где k – число информационных символов (символов в информационном слове), а n – число кодовых символов (символов в кодовом слове). В теории кодирования между этими множествами всегда существует однозначное соответствие.
Рисунок 1.2. Кодер блокового кода
Вместо k бит информационного вектора в канал передается n бит кодового вектора. К каждому блоку данных кодирующее устройство прибавляет (n - k) избыточных бит, которые также называют контрольными битами или битами ч?тности. Отношение числа избыточных бит к числу информационных бит, (n - k)/k называется избыточностью кода. Отношение числа бит данных к общему числу бит, k/n, называется степенью кодирования. Степень кодирования показывает долю кода, которая приходится на полезную информацию. Кодирование линейного блокового (n, k)-кода задается порождающей матрицей G размером (k х n). Таким образом, кодовое слово v и информационное слово u связаны соотношением v = u*G.
Правильно декодировать можно далеко не все модели ошибки. Возможности кода для исправления ошибок в первую очередь определяются его структурой. Весовой коэффициент Хэмминга w(U) кодового слова U определяется как число ненулевых элементов в U. Для двоичного вектора это эквивалентно числу единиц в векторе. Например, если U=100101101, то w(U)=5. Расстояние Хэмминга между двумя кодовыми словами U и V, обозначаемое как d(U,V), определяется количеством элементов, в которых они отличаются. Согласно свойствам сложения по модулю 2, можно отметить, что сумма двух двоичных векторов является другим двоичным вектором, двоичные единицы которого расположены на тех позициях, которыми эти векторы отличаются. Таким образом, можно видеть, что расстояние Хэмминга между двумя векторами равно весовому коэффициенту их суммы, то есть d(U,V)= w(U+V). Также видно, что весовой коэффициент кодового слова равен его расстоянию до нулевого вектора. Наименьший элемент из множества расстояний между парами кодовых слов называется минимальным расстоянием кода и обозначается dmin. Минимальное расстояние дает нам меру минимальных возможностей кода и, следовательно, характеризует его помехоустойчивость. Сумма двух произвольных кодовых слов дает другой элемент кодовых слов, что является свойством линейных кодов. Если U и V кодовые слова, то и W=U+V тоже должно быть кодовым словом. Следовательно, расстояние между двумя кодовыми словами равно весовому коэффициенту третьего кодового слова. Таким образом, минимальное расстояние линейного кода соответствует минимальному весу кодового слова. Иными словами, минимальное расстояние соответствует наименьшему из множества расстояний между нулевым кодовым словом и всеми остальными кодовыми словами. Линейный код с минимальным расстоянием Хэмминга dmin ? 2t+1 может обнаружить dmin-1 ошибок и исправить t ошибок. Код корректирующий ошибки в t битах называется совершенным.
Систематический линейный блочный код это код, в котором n символов кодового слова содержат k символов информационного сообщения. Таким образом, кодовое слово систематического кода имеет n-k бит четности и k информационных символов. Порождающую матрицу любого систематического кода всегда можно путем перестановки столбцов к виду:
G_kxn=(P_(kx(n-k)) I_k (1.1)
где нижние индексы обозначают размерность матрицы, а I_k единичная матрица размером (k х k). Цикличные коды являются подмножеством линейных кодов. Линейный (n, k)-код является циклическим, если циклический сдвиг любого кодового слова также является также кодовым словом этого кода. Циклический сдвиг соответствует сдвигу всех компонент на один разряд вправо, причем, освободившееся место слева занимает крайняя правая компонента.
1.1.2 Свёрточные коды
Свёрточные коды - это коды, использующие непрерывную обработку потока данных короткими блоками. Свёрточный кодер имеет память и символы на его выходе зависят не только от очередного блока символов на входе, но и от предыдущих символов. Свёрточное кодирование является отображением информационной последовательности символов в кодовую последовательность с помощью линейной схемы с параметрами, не меняющимися во времени. Выходная последовательность n-кодовых символов, получаемая при свёрточном кодировании, является функцией не только одной входной последовательности k-информационных символов, но и предыдущих К-1 входных последовательностей. Целое число К является параметром, называемым длинной кодового ограничения, - оно указывает число разрядов в кодирующем регистре сдвига в которые помещаются информационные символы. Теоретически входная последовательность бит бесконечна, но на практике свёрточным кодам обычно придают блоковую структуру, устанавливая состояние свёрточного кодера в некоторое заранее известное состояние (например нулевое). Декодирование свёрточных кодов, обычно, производится по довольно сложному алгоритму Витерби. Алгоритм Витерби проводит декодирование согласно критерию максимального правдоподобия. Свёрточные коды эффективно борются с одиночными ошибками, но плохо справляются с пакетами ошибок. Более того, ошибка декодера приводит к образованию на его выходе пакета ошибок.
1.1.3 Каскадные коды и турбокоды
В каскадных кодах кодирование осуществляется в два уровня. Входные данные сначала кодируются внешним кодом, а затем внутренним, после чего осуществляется модуляция сигнала. Декодирование происходит в обратном порядке. Искаженные каналом данные с демодулятора поступают сначала на декодер внутреннего кода, а затем на декодер внешнего кода. Структурная схема системы каскадного кодирования изображена на рисунке 1.3. Достоинством каскадных кодов является относительно низкая сложность кодирующих и декодирующих устройств, так как каскадные коды позволяют выполнить процедуры кодирования и декодирования по этапам, применяя на каждом этапе достаточно короткие по сравнению с результирующим коды. Каскадные коды позволяют реализовать достаточно большое кодовое расстояние, поэтому их применение в каналах с высоким уровнем помех эффективно.
Турбокод является развитием системы каскадного кодирования путем применения итеративного декодирования. Основная идея турбо-кодирования заключается в подаче мягкого решения с выхода одного декодера на вход другого и повторение этой процедуры до тех пор, пока не будет достигнута необходимая точность принятия решения. Методы декодирования турбокодов имеют большую вычислительную сложность. Этого недостатка лишены методы многопорогового декодирования. Итеративные алгоритмы при каждом изменении корректируемых ими символов всегда находят строго более правдоподобные решения. В системах передачи данных использующей радиомодемы, выдающие жесткое решение, применение турбокодов и многопорогового кодирования затруднительно.
Рисунок 1.3. Структурная схема системы каскадного кодирования
1.1.4 Коды Хемминга
Коды Хемминга образуют важное семейство простейших линейных блоковых кодов. Для каждого натурального числа m?3 существует двоичный код Хэмминга со следующими параметрами: - длина кодовых слов n = 2m – 1; - число информационных разрядов k = 2m – 1– m; - число проверочных разрядов m = n – k; 33 - корректирующая способность t = 1, dmin = 3. Код Хэмминга требует минимальной избыточности при заданной длине блока для исправления одной ошибки. Код Хемминга является совершенным кодом. Из всего вышесказанного видно, что код Хемминга или только обнаруживает все ошибки кратностью не выше 2, или только исправляет все однократные ошибки. Преимуществом данного кода является его простота, и как следствие высокие скорости кодирования и декодирования. Недостатком является его способность исправлять лишь одиночные ошибки.
1.1.5 Коды Рида-Соломона
Основная идея помехозащитного кодирования Рида ? Соломона заключается в умножении информационного слова, представленного в виде полинома D, на неприводимый полином G, известный обеим сторонам, в результате чего получается кодовое слово C, опять-таки представленное в виде полинома.
Декодирование осуществляется с точностью до наоборот: если при делении кодового слова C на полином G декодер внезапно получает остаток, то он может рапортовать наверх об ошибке. Соответственно, если кодовое слово разделилось нацело, его передача завершилась успешно.
Если степень полинома G (называемого так же порождающим полиномом) превосходит степень кодового слова, по меньшей мере, на две степени, то декодер может не только обнаруживать, но и исправлять одиночные ошибки. Если же превосходство степени порождающего полинома над кодовым словом равно четырем, то восстановлению поддаются и двойные ошибки. То есть, степень полинома k связана с максимальным количеством исправляемых ошибок t следующим образом: k = 2t.
Следовательно, кодовое слово должно содержать два дополнительных символа на одну исправляемую ошибку. В то же время максимальное количество распознаваемых ошибок равно t, т. е. избыточность составляет один символ на каждую распознаваемую ошибку.
В отличие от кодов Хемминга, коды Рида ? Соломона могут исправлять любое разумное количество ошибок при вполне приемлемом уровне избыточности. В кодах Хемминга контрольные биты контролировали лишь те информационные биты, что находятся по правую сторону от них и игнорировали всех «левосторонних» товарищей. Обратимся к таблице 1: добавление восьмого контрольного бита D ничуть не улучшило помехозащищенность кодирования, поскольку контрольному биту D было некого контролировать.
В кодах же Рида ? Соломона контрольные биты распространяют свое влияние на все информационные биты и потому с увеличением количества контрольных бит увеличивается и количество распознаваемых/устраняемых ошибок. Именно благодаря последнему обстоятельству, собственно, и вызвана ошеломляющая популярность корректирующих кодов Рида ? Соломона.
Для работы с кодами Рида ? Соломона обычная арифметика не подходит. Так как кодирование предполагает вычисления по правилам действия над полиномами, с коэффициентами которых надо выполнять операции сложения, вычитания, умножения и деления, причем все эти действия не должны сопровождаться каким-либо округлением промежуточных результатов (даже при делении), чтобы не вносить неопределенность. Причем и промежуточные, и конечные результаты не имеют права выходить за пределы установленной разрядной сетки.
Умножать информационное слово на порождающий полином вовсе не обязательно, можно поступить иначе:
- Добавляем к исходному информационному слову D справа k нулей, в результате чего у нас получается слово длины n = m + r и полином XrD, где m – длина информационного слова.
- Делим полученный полином XrD на порождающий полином G и вычисляем остаток от деления R, такой что: XrD = GQ + R, где Q – частное, которое мы благополучно игнорируем за ненадобностью, т. к. нас интересует только остаток.
- Добавляем остаток R к информационному слову D, в результате чего получаем кодовое слово C, информационные биты которых хранятся отдельно от контрольных бит.
