Файл: Методы кодирования данных (Задача кодирования).pdf

Сложное программное обеспечение при сборке требует использования десятков или даже сотен файлов с исходным кодом. В таких случаях для упрощения сборки обычно используются файлы проектов, содержащие описание зависимостей между файлами с исходным кодом и описывающие процесс сборки. Эти файлы также могут содержать параметры для компилятора и среды проектирования. Для разных сред проектирования могут применяться разные файлы проекта, причём в некоторых средах эти файлы могут быть в текстовом формате, пригодном для непосредственного редактирования программистом с помощью универсальных текстовых редакторов, в других средах поддерживаются специальные форматы, а создание и изменение файлов производится с помощью специальных инструментальных программ. Файлы проектов обычно включают в понятие «исходный код». Часто под исходным кодом подразумевают и файлы ресурсов, содержащие различные данные, например графические изображения, нужные для сборки программы.

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

В отличие от человека, для компьютера нет «хорошо написанного» или «плохо написанного» кода. Но то, как написан код, может сильно влиять на процесс сопровождения ПО. О качестве исходного кода можно судить по следующим параметрам:

читаемость кода (в том числе наличие комментариев к коду);
лёгкость в поддержке, тестировании, отладке и устранении ошибок, модификации и портировании;
экономное использование ресурсов: памяти, процессора, дискового пространства;
отсутствие замечаний, выводимых компилятором;
отсутствие «мусора» — неиспользуемых переменных, недостижимых блоков кода, ненужных устаревших комментариев и т. д.;
адекватная обработка ошибок;
возможность интернационализации интерфейса.

3.3. Защита и хранение

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

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

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

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

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

Глава 4. Энтропийное кодирование

4.1. Определения

Энтропийное кодирование – кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности.

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

Различают несколько вариантов кодов:

- сопоставление каждому элементу исходной последовательности различного числа элементов результирующей последовательности. Чем больше вероятность появления исходного элемента, тем короче соответствующая результирующая последовательность. Примером могут служить код Шеннона – Фано, код Хаффмана;

- сопоставление нескольким элементам исходной последовательности фиксированного числа элементов конечной последовательности. Примером является код Танстола;

- другие структурные коды, основанные на операциях с последовательностью символов. Примером является кодирование длин серий.

Если приблизительные характеристики энтропии потока данных предварительно известны, может быть полезен более простой статический код, такой как унарное кодирование, гамма-код Элиаса, код Фибоначчи, код Голомба или кодирование Райса.

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

4.2. Энтропийное сжатие

Кодирование энтропии – кодирование словами (кодами) переменной длинны, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в определенном сообщении.

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

Три самых распространенных способа кодирования энтропии – это кодирование Хаффмана, кодирование длин серий и арифметическое кодирование.

Глава 5. Дельта-кодирование

5.1. Основы дельта-кодирования

Дельта-кодирование (англ. Delta encoding) – способ представления данных в виде разницы (дельты) между последовательными данными вместо самих данных. Пожалуй, наиболее простой пример заключается в сохранении значений байтов как различия (дельты) между последовательными значениями, в отличие от самих значений. Поэтому вместо 2, 4, 6, 9, 7, мы будем сохранять 2, 2, 2, 3, −2. Это не очень полезно в случае, когда используется само по себе, но может помочь в случае дальнейшей компрессии этих данных, в которых часто встречаются повторяющиеся значения. Например, звуковой формат IFF 8SVX применяет это кодирование к чистым звуковым данным перед тем, как применять к ним компрессию. Только 8-битные звуковые семплы хорошо сжимаются в случае дельта-кодирования, а в случае 16-битных и выше семплов этот метод работает хуже. Поэтому, алгоритмы компрессии часто выбирают дельта-кодирование только тогда, когда сжатие с ним лучше, чем без него. Однако в сжатии видео дельта-фреймы могут значительно уменьшать размер фрейма, и используются практически в каждом видеокодеке.

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

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

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

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