Файл: Методы кодирования данных (ОСНОВЫ КОДИРОВАНИЯ ИНФОРМАЦИЯ).pdf

Такие прикладные математические теории, как теория информации, теория принятия решений, теория массового обслуживания, теория управления, моделирование систем, математическая и формальная логики, теории алгоритмов и автоматов, теории формальных языков и грамматик, социальная информатика, исследование операций и другие и сегодня составляют основу «информационного» образования. ^[12]

Общее у этих теорий – это «переборный» или «цифровой» метод:

1. сначала интеллектуал должен сформулировать цель исследования;

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

Затем квантованный выход демодулятора поступает на декодер, который, используя внесенную кодером избыточность, определяет переданное источником сообщение. Основная сложность реализации модели системы связи заложена в реализации кодера и декодера. ^[13]

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

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

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

---

Рассмотрим с общих позиций те физические ресурсы, которые необходимы для выполнения функций базовыми информационными технологиями сохранения, распространения и обработки данных

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

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

− для технологий сохранения – размер запоминающих устройств для записи и плотность записи данных;

− для технологий распространения – территория, в пределах которой организуется информационное взаимодействие пользователей (зона охвата) и распределение (плотность) пользователей на этой территории;

− для технологий обработки – размер техпроцесса и количество транзисторов, размещаемых в одном чипе. ^[14]

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

Поэтому в процессе разработки было решено реализовать динамическое подключение к основной программе новых компонентов системы передачи данных через библиотеки классов (*.dll). ^[15]

Таким образом, в каждом подобном классе будет реализован набор свойственных данному компоненту функций, которые обеспечат взаимодействие с основной программой и механизм гибкой настройки данного класса. Подобная реализация предоставит широкую возможность настройки и быстрого расширения системы. ^[16]

Так даже при 100 % загрузке CPU не получалось достичь скорости моделирования больше, чем 2000 кбит/с, даже для алгоритмически простого и вычислительно не сложного метода коррекции ошибок, основанного на коде Хэмминга.

При этом, чтобы сделать сколько-нибудь обоснованные выводы об эффективности того или иного алгоритма, часто требуются гигабиты битового потока, пропущенного через систему передачи данных. К примеру, для того, чтобы оценить эффективность алгоритма с требованием к вероятности появления ошибки в 10−12, требуется смоделировать передачу порядка 14 10 бит данных.

---

Таким образом при скорости 2000 кбит/с потребуется как минимум 6 5 •10 секунд, что эквивалентно 57 дням только для одного эксперимента. При этом нужно понимать, что одного эксперимента может быть недостаточно, и процесс моделирования может носить итерационный характер. ^[17]

Очевидно, что подобная загрузка абсолютно недопустима для персональных компьютеров, которые являются зачастую единственным инструментом исследований и повседневной работы разработчиков и не могут быть столь сильно загружены на таком длительном временном промежутке. ^[18]

Исходя из вышесказанного, актуальной является задача по ускорению процесса моделирования и сокращению временных затрат на проведение эксперимента до уровня, который сделает регулярное получение результатов моделирования удобными и быстрым. Очевидным решением является перенос вычислительной нагрузки моделирования на устройства персонального компьютера, более заточенные на выполнения операций с векторами данных, чем CPU. ^[19]

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

Графические процессоры по сложности абсолютно не уступают центральным процессорам, но из-за своей узкой специализации в состоянии более эффективно справляться с задачей обработки графики, построением изображения с последующим выводом его на монитор. Если говорить о параметрах, то они у графических процессоров весьма схожи с центральными процессорами. ^[20]

Но у них имеются и довольно специфические характеристики. Например немаловажная характеристика графического процессора – это количество пиксельных конвейеров. Эта характеристика определяет количество обрабатываемых пикселей за один такт работы GPU. Количество данных конвейеров может различаться.

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

Также количество пиксельных конвейеров влияет на немаловажный параметр – скорость заполнения видеокарты. Скорость заполнения видеокарты можно рассчитать, умножив частоту ядра на количество конвейеров.

---

Давайте рассчитаем скорость заполнения, к примеру, для видеокарты на базе процессора NVidia GeForce 780Ti. Частота ядра GPU этого чипа составляет 1008 МГц, а количество пиксельных конвейеров – 240.

Нехитрыми математическими вычислениями (1008⋅240) мы приходим к выводу, что скорость заполнения будет приблизительно равна 250 Гпиксель/c.

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

На данный момент самый эффективный функционал по использованию ресурсов GPU предоставляет библиотека OpenCL. OpenCL обеспечивает параллелизм на уровне инструкций и на уровне данных.

В своей работе OpenCL использует CPU, GPU, другие процессоры, доступные на персональном компьютере, предоставляя разработчику доступ к максимальным вычислительным мощностям, доступным на персональном компьютере. OpenCL является полностью открытым стандартом, его использование не облагается лицензионными отчислениями, что также является важным фактором. ^[21]

Дополнительный путь ускорения процесса моделирования – использование вычислительных кластеров, т. е. группы компьютеров, которые будут объединены по локальной сети. Причем вычислительный кластер может состоять из любых видов вычислительных единиц. ^[22]

Это могут быть как персональные компьютеры или ноутбуки, так и виртуальные машины. Единственным условием является объединение их в локальную сеть.

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

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

Пользователи будут иметь доступ на головную машину кластера, а входить на узлы кластера для них нет необходимости. ^[23]

Таким образом, в процессе исследования была изучена система передачи данных, разработана гибкая модульная архитектура модели системы моделирования данных. Найдены «узкие места» модели системы передачи данных, ограничивающие увеличение скорости моделирования, выявлены способы ускорения моделирования через использование дополнительных ресурсов персонального компьютера, таких, как GPU. ^[24]

---

Глава 2. ОСНОВНЫЕ МЕТОДЫ КОДИРОВАНИЯ ИНФОРМАЦИИ

2.1. СПОСОБ ПРЯМОГО ОТОБРАЖЕНИЯ НА ФУНКЦИЮ КАК КОДИРОВАНИЕ ДАННЫХ

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

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

После определения текущего значения аргумента xk, при котором происходит совпадение значений кодирующей функции и текущего отсчета входной последовательности, вычисляется длина временного интервала между предыдущим и текущим закодированными значениями [xk-1; xk], причем для первого отсчета берется длина интервала, измеряемая от начала оси координат до этого отсчета. ^[25]

В результате каждому элементу исходной последовательности данных сопоставляется элемент последовательности вычисленных длин интервалов. Следует отметить, что в общем случае кодирующая функция определяется на некотором интервале [0; T], не связанном с временным интервалом, на котором расположена исходная последовательность данных.

Для первичного исследования предлагаемого способа кодирования в качестве кодирующей функции была использована синусоида с фиксированной частотой и нулевой начальной фазой: max () 0 (0) sin (2 /) F x A A A xT К = + −⋅ π, где: T – период синусоиды; max min AA A 0 ()/2 = + – постоянная составляющая; Amax и Amin – максимальное и минимальное значения отсчетов исходной последовательности данных соответственно. При исследовании предлагаемого способа в качестве исходных данных, подлежащих кодированию, использовались реализации случайного процесса с нормальным распределением.

---