Использование непрефиксного вырожденного кода при чтении и записи информации

Описано алгоритм читання і запису інформації за допомогою непрефіксного виродженого коду. Алгоритм побудовано на ідеї використання першого біта символа, наступного за поточним символом, як префіксного. Як приклад використання алгоритму розглянуто випадок читання і запису довільного бітового потоку,...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Дядьков, К.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Назва видання:	Проблемы управления и информатики
Теми:	Методы обработки информации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/207605
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Использование непрефиксного вырожденного кода при чтении и записи информации / К.В. Дядьков // Проблемы управления и информатики. — 2013. — № 2. — С. 105–110. — Бібліогр.: 5 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207605
record_format	dspace
spelling	irk-123456789-2076052025-10-12T00:17:15Z Использование непрефиксного вырожденного кода при чтении и записи информации Використання непрефіксного виродженого коду при читанні та запису інформації Usage of Non-Prefix Degenerate Code at Information Reading and Writing Дядьков, К.В. Методы обработки информации Описано алгоритм читання і запису інформації за допомогою непрефіксного виродженого коду. Алгоритм побудовано на ідеї використання першого біта символа, наступного за поточним символом, як префіксного. Як приклад використання алгоритму розглянуто випадок читання і запису довільного бітового потоку, при цьому структура коду, за допомогою якого здійснювалося читання і запис інформації, збіглася зі структурою генетичного коду. This article presents a description of information reading and writing algorithm by means of non-prefix degenerate code. The algorithm is based on the idea of usage of the first bit of a symbol following the current symbol as a prefix one. As an example of the algorithm application, the case of reading and writing of a random bit stream is considered. Therewith code structure by means of which information reading and writing were carried out concurred with the genetic code structure. 2013 Article Использование непрефиксного вырожденного кода при чтении и записи информации / К.В. Дядьков // Проблемы управления и информатики. — 2013. — № 2. — С. 105–110. — Бібліогр.: 5 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207605 519.7 10.1615/JAutomatInfScien.v45.i3.60 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки информации Методы обработки информации
spellingShingle	Методы обработки информации Методы обработки информации Дядьков, К.В. Использование непрефиксного вырожденного кода при чтении и записи информации Проблемы управления и информатики
description	Описано алгоритм читання і запису інформації за допомогою непрефіксного виродженого коду. Алгоритм побудовано на ідеї використання першого біта символа, наступного за поточним символом, як префіксного. Як приклад використання алгоритму розглянуто випадок читання і запису довільного бітового потоку, при цьому структура коду, за допомогою якого здійснювалося читання і запис інформації, збіглася зі структурою генетичного коду.
format	Article
author	Дядьков, К.В.
author_facet	Дядьков, К.В.
author_sort	Дядьков, К.В.
title	Использование непрефиксного вырожденного кода при чтении и записи информации
title_short	Использование непрефиксного вырожденного кода при чтении и записи информации
title_full	Использование непрефиксного вырожденного кода при чтении и записи информации
title_fullStr	Использование непрефиксного вырожденного кода при чтении и записи информации
title_full_unstemmed	Использование непрефиксного вырожденного кода при чтении и записи информации
title_sort	использование непрефиксного вырожденного кода при чтении и записи информации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2013
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207605
citation_txt	Использование непрефиксного вырожденного кода при чтении и записи информации / К.В. Дядьков // Проблемы управления и информатики. — 2013. — № 2. — С. 105–110. — Бібліогр.: 5 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT dâdʹkovkv ispolʹzovanieneprefiksnogovyroždennogokodapričteniiizapisiinformacii AT dâdʹkovkv vikoristannâneprefíksnogovirodženogokodupričitannítazapisuínformacíí AT dâdʹkovkv usageofnonprefixdegeneratecodeatinformationreadingandwriting
first_indexed	2025-10-12T01:11:37Z
last_indexed	2025-10-13T01:09:48Z
_version_	1845826984899248128
fulltext	© К.В. ДЯДЬКОВ, 2013 Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 105 УДК 519.7 К.В. Дядьков ИСПОЛЬЗОВАНИЕ НЕПРЕФИКСНОГО ВЫРОЖДЕННОГО КОДА ПРИ ЧТЕНИИ И ЗАПИСИ ИНФОРМАЦИИ Введение Динамичное развитие информационных технологий, берущих свое начало в середине прошлого века благодаря работам К. Шеннона, требует постоянных исследований в целях повышения эффективности их дальнейшего использования. В связи с этим появляется необходимость в новых современных средствах прие- ма, обработки, хранения и передачи информации. Непрерывно увеличивающиеся объемы информации ведут к росту стоимос- ти, энергоемкости и расходу ресурсов, связанных с их обработкой, хранением и передачей. Актуальность настоящего исследования обусловлена необходимостью поиска новых решений в области хранения и передачи данных больших объемов. К таким новым решениям можно отнести разработку алгоритмов сжатия инфор- мации, основанных на использовании непрефиксных вырожденных кодов. Кроме этого, важнейшим фактором была и остается проблема безопасного хранения и передачи информации, хотя исследования в этой области выходят за рамки настоящей публикации. Рассматриваемый в статье алгоритм чтения и записи информации может представлять интерес для исследований в области разработки компьютерных про- грамм сжатия информации, способствовать дальнейшему развитию мультимедий- ных средств и так далее. В качестве примера рассматривается применение алго- ритма к генетическому коду, что, в свою очередь, может вызвать интерес не толь- ко у специалистов по информатике, но и по генетике. В настоящее время алгоритмы сжатия информации подразделяются, в основ- ном, на алгоритмы сжатия информации без потерь и с частичной потерей данных. Такие алгоритмы описаны во многих источниках, например в [1–5]. Эффектив- ность алгоритмов сжатия без потерь ограничена энтропией. Эффективность алго- ритмов с частичной потерей данных ограничена качеством восстановленной пос- ле сжатия информации. Чем выше степень сжатия, тем хуже качество восстанов- ленной информации. В связи с этим к нерешенным проблемам можно отнести разработку таких алгоритмов, которые обладали бы большой степенью сжатия при сохранении приемлемого качества информации после ее восстановления. Считается, что непрефиксный вырожденный код не поддается однозначному восстановлению при распаковке информации после сжатия и поэтому не вызыва- ет интереса у специалистов по информатике [1]. В настоящей статье описан алго- ритм чтения и записи информации с помощью конструкций непрефиксного вы- рожденного кода, который может быть записан и затем однозначно прочитан. Примером способа сжатия информации может служить виртуальное устройство, включающее в себя два алфавита: А и В. Входной алфавит А представляет собой обычный двоичный код переменной длины, состоящий из 23 букв (9 из которых име- ют длину по 4 бита и 14 букв имеют длину по 5 бит). Выходной алфавит В представ- лен в правой части таблицы, который тоже состоит из 23 букв. Сжимаемый файл счи- тывается входным алфавитом А, после чего алфавит сортируется в порядке убывания повторений букв в потоке (отдельно по группам 4 и 5 бит). Затем входной поток снова перечитывается с помощью отсортированного алфавита А и с помощью алфавита В формируется выходной поток (файл). При этом каждой букве в отсортированном ал- фавите А ставится в соответствие буква из алфавита В. Итерации могут повторяться до 106 ISSN 0572-2691 тех пор, пока во входном потоке не начнет уравниваться количество повторений букв из алфавита А. Распаковка информационного потока производится в обратном порядке. Принцип работы алгоритма Сам алгоритм достаточно прост и может быть объяснен на нескольких при- мерах. Из многих источников, например из [1], известно, что в общем случае с помощью непрефиксных или вырожденных кодов невозможно записывать и затем однозначно считывать информацию, но это утверждение справедливо не для всех кодов такого рода. Рассмотрим любую произвольную битовую последовательность: 0100111000100011101010000101. Ее можно прочитать с помощью различных алфавитов, например, вот так: А В D E A С 0100 1110 01000 11101 01000 0101. В верхней строке записаны буквы произвольного алфавита, а в нижней — двоич- ная запись этих букв. Как видим, последовательность прочитана с помощью непрефиксного кода. Чтение осуществлялось по следующему правилу: символ А читается как 0100 и имеет длину 4 бита в том случае, если следующий за ним символ начинается с единицы (в примере она выделена жирным шрифтом). Сим- вол D читается как 01000 и имеет длину 5 бит в том случае, если следующий за префиксом символа D0100 поток начинается с нуля, т.е. мы заимствуем пре- фиксный бит из следующей буквы. Такое же правило применяется к символам В1110 и Е11101, но только единица меняется на ноль. Символы А, D, B и E непрефиксные и принимают значения соответственно 0100 и 01000, 1110 и 11101 в зависимости от того, какой бит следует за префиксами 0100 и 1110. Понятно, что если мы имеем запись АА, то ее невозможно прочитать однозначно. В самом деле, АА в двоичном коде имеет вид 01000100. По указанному нами правилу за префик- сом 0100 следует ноль, поэтому первый символ должен быть прочитан как D01000, а это приводит к ошибке считывания. Теперь изменим правила считывания (для этого пришлось немного изменить и первоначальный битовый поток): А В D E А С 0100 1110 01000 11101 11001 0101, т.е. символ А имеет два различных значения: 0100 и 11001. Читаются они по сле- дующему правилу. Если битовая последовательность читается как 0100 и следу- ющий бит в последовательности является единицей, то символ читается как А0100. Если битовая последовательность читается как 11001 и следующий бит в последовательности — ноль, то символ читается как А11001. Такой символ называется вырожденным, так как он задается двумя различными битовыми набо- рами. Теперь начинаем считывать битовую последовательность. Первым следует символ А0100, за ним символ начинается с единицы (в примере она выделена жирным шрифтом). Если бы он начинался с нуля, то вместо символа А был бы прочитан символ D01000, рамка считывания сместилась бы на один бит и вся буквенная последовательность при этом изменилась бы. Но тем не менее следу- ющий символ — В1110. Если бы следующий символ начинался с единицы, то был бы прочитан символ Е11101. Такая последовательность может быть однозначно восстановлена. Но при чте- нии меняется направление, т.е. если запись такой последовательности должна осу- ществляться справа налево, то читать ее мы должны слева направо. Итак, имеется последовательность ABDEAC. Последний символ C0101 и он не является вы- рожденным, поэтому нет сомнений в том, как его записывать. Далее перед симво- лом С находится символ А. Так как С начинается с нуля, то мы знаем, что в этом Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 107 случае символ А имеет значение 11001. Общая цепочка пока восстановлена: 11001 0101. Теперь рассмотрим символ E. Он также не является вырожденным, и мы знаем, как его записать: Е11101 и общая последовательность 11101 11001 0101. Дальше следует символ D01000 и общая последовательность записывается как 01000 11101 11001 0101. Теперь нужно записать символ В, который тоже не является вырожденным, и В1110. Осталось записать последний, т.е. на самом деле, первый символ — А. Поскольку следующий за ним символ В начинается с единицы, то мы знаем, что в этом случае символ А приобретает значение А0100. Теперь вся исходная последовательность записана однозначно: А В D E А С 0100 1110 01000 11101 11001 0101. Данный пример сильно упрощен, и в нем не учтены все значения полного алфави- та, но он приведен лишь для того, чтобы объяснить принцип работы алгоритма чтения-записи непрефиксного вырожденного кода. Пример использования алгоритма Интересным является тот факт, что при определенном допущении таблица гене- тического кода, опубликованная во многих источниках, например в [4], по своей структуре полностью соответствует приведенным выше принципам. В качестве тако- го допущения нам нужно лишь предположить, что символы этой (генетической) таб- лицы кодируются не четверичным кодом, а двоичным. Известно, что генетический код построен с помощью четырех оснований: A, C, U, G. Последовательность из лю- бых трех букв этого набора кодирует одну аминокислоту и называется триплетом или кодоном, т.е. для кодирования этих оснований требуется различать четыре значения. С помощью двоичного кода это можно записать так: А11, C01, U00, G10. Та- кая кодировка выбрана потому, что основания являются попарно комплементарными, запишем их попарно инвертированными. Этими парами являются А-U и C-G. Теперь, заменив все триплеты в таблице генетического кода их двоичными эквивалентами, получим 64 двоичных слова длиной по 6 бит каждое. Например, в таблице напротив фенилаланина UUU стоит его двоичный эквивалент 000000. Известно также, что некоторые аминокислоты в генетическом коде записываются не одним, а несколькими словами. Например, фенилаланин записывается с помощью двух слов: UUU и UUC. Их двоичные эквиваленты запишутся соответственно 000000 и 000001. Мы видим, что эти значения различаются в последнем бите. Поэтому, отбросив его, фенилаланин можно записать с помощью только одного пятибитового двоичного слова — 00000. Дальше в таблице идет лейцин. Он кодируется с помощью шести буквенных символов: UUA, UUG, CUU, CUC, CUA и CUG. В двоичном виде все эти значения запишутся так: UUA000011; UUG000010; CUU=010000; CUC010001; CUA010011; CUG010010. Если отбросить неповторяющиеся биты, получим два различных значения для лейцина: 00001 и 0100, тогда мы сможем считывать после- довательность, содержащую такие значения, но не сможем ее однозначно записать. Применяя описанные выше правила для чтения и записи вырожденного кода, полу- чим два других значения: 0000 и 010, т.е. если битовая последовательность читается как 0000 и следующий бит — единица, то символ читается как лейцин 0000. Если же последовательность читается как 010 и следующий бит — ноль, то символ чи- тается как лейцин 010. В итоге получим последовательность UUA0000 11; UUG0000 10; CUU010 000; CUC010 001; CUA010 011; CUG010 010. Жирным шрифтом выделены те биты, которые используются в качестве пре- фиксных, заимствованных из следующих в последовательности символов. Ами- нокислоты, встречающиеся в таблице только один раз, например, такие как мети- онин или коды окончания синтеза, записываются с помощью всех шести бит. Например, метионин 110010. 108 ISSN 0572-2691 Таблица № Триплет Название аминокислоты U00; C01; A11; G10; Двоичный аналог триплета № Название аминокислоты Двоичный аналог 1 2 3 4 5 6 7 1 UUU 00000 0 010 0 0000 1 2 UUC Фенилаланин 00000 1 1 Лейцин 3 UUA 0000 11 000 1 1110 0 4 UUG* Лейцин 0000 10 2 Серин 5 CUU 010 000 011 0 1110 1 6 CUC 010 001 3 Аргинин 7 CUA 010 011 4 Валин 1000 8 CUG Лейцин 010 010 5 Пролин 0101 9 AUU 1100 00 6 Треонин 1101 10 AUC 1100 01 7 Аланин 1001 11 AUA Изолейцин 11001 1 8 Глицин 1010 12 AUG* Метионин 110010 1100 0 11001 1 13 GUU 1000 00 9 Изолейцин 14 GUC 1000 01 10 Фенилаланин 00000 15 GUA 1000 11 11 Тирозин 00110 16 GUG* Валин 1000 10 12 Гистидин 01110 17 UCU 000 100 13 Глутамин 01111 18 UCC 000 101 14 Аспарагин 11110 19 UCA 000 111 15 Лизин 11111 20 UCG Серин 000 110 16 Аспарагиновая кислота 10110 21 CCU 0101 00 17 Глутаминовая кислота 10111 22 CCC 0101 01 18 Цистеин 00100 23 CCA 0101 11 19 Метионин 110010 24 CCG Пролин 0101 10 20 Триптофан 001010 25 ACU 1101 00 21 Конец синтеза 1 001111 26 ACC 1101 01 22 Конец синтеза 2 001110 27 ACA 1101 11 23 Конец синтеза 3 001011 28 ACG Треонин 1101 10 29 GCU 1001 00 30 GCC 1001 01 31 GCA 1001 11 32 GCG Аланин 1001 10 33 UAU 00110 0 34 UAC Тирозин 00110 1 35 UAA Конец синтеза 1 001111 36 UAG Конец синтеза 2 001110 37 CAU 01110 0 38 CAC Гистидин 01110 1 39 CAA 01111 1 40 CAG Глутамин 01111 0 41 AAU 11110 0 42 AAC Аспарагин 11110 1 43 AAA 11111 1 44 AAG Лизин 11111 0 45 GAU 10110 0 46 GAC Аспарагиновая кислота 10110 1 47 GAA 10111 1 48 GAG Глутаминовая кислота 10111 0 49 UGU 00100 0 50 UGC Цистеин 00100 1 51 UGA Конец синтеза 3 001011 Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 2 109 Продолжение таблицы 1 2 3 4 5 6 7 52 UGG Триптофан 001010 53 CGU 011 000 54 CGC 011 001 55 CGA 011 011 56 CGG Аргинин 011 010 57 AGU 1110 00 58 AGC Серин 1110 01 59 AGA 1110 11 60 AGG Аргинин 1110 10 61 GGU 1010 00 62 GGC 1010 01 63 GGA 1010 11 64 GGG Глицин 1010 10 Результат представления триплетов их двоичным эквивалентом, а также оп- тимизация полученных двоичных слов приведены в таблице. В левой части указа- ны все триплеты генетического кода, соответствующие определенным аминокис- лотам, и их двоичный эквивалент. В правой части таблицы приведены те же ами- нокислоты и соответствующий им непрефиксный вырожденный бинарный код. Данный код является непрефиксным, потому что некоторые символы, например серин, лейцин и фенилаланин, записываются соответственно 000, 0000, 00000, что не отвечает требованиям, предъявляемым к префиксному коду. И он является вы- рожденным, потому что некоторые символы записываются двумя кодирующими словами (серин, лейцин, аргинин и изолейцин). Следует отметить, что с помощью кодирующих слов, приведенных в левой и правой части таблицы, нельзя записывать одни и те же аминокислоты. Результат чтения двоичной последова- тельности будет отличаться. Проверка работы алгоритма Для иллюстрации рассмотрим следующий пример. Пусть у нас имеется про- извольная двоичная последовательность 010000 011100 111110100101101001. Прочитав ее с помощью двоичных аналогов триплетов, получим следующий результат: лейцин гистидин лизин аланин глицин CUU CAU AAG GCC GGC 010000 011100 111110 100101 101001. Понятно, что если мы захотим записать последовательность лейцин–гистидин– лизин–аланин–глицин двоичным кодом или с помощью триплетов, то мы можем сделать это множеством способов, так как некоторые аминокислоты могут коди- роваться несколькими триплетами. Поэтому указанная двоичная последователь- ность, соответствующая последовательности аминокислот, не может быть одно- значно восстановлена. Прочитав эту же последовательность с помощью вырож- денного непрефиксного кода, приведенного в правой части таблицы, получим следующий результат: лейцин лейцин серин глутамин глицин пролин глицин Остаток битовой последовательности 010 0000 1110 01111 1010 0101 1010 01. Теперь по полученной аминокислотной последовательности восстановим би- товый поток. Вначале запишем остаток — 01, затем следует глицин (записываем 110 ISSN 0572-2691 справа налево). Общая последовательность: 101001. Дальше в порядке убывания идут пролин, глицин и глутамин. Запись этих символов не вызывает проблем, и общий записанный поток принимает вид 0111110100101101001. Теперь нужно записать серин. Так как глутамин начинается с нуля, то серин в этом случае за- пишется как 1110. Лейцин при условии, что серин начинается с единицы, прини- мает значение 0000 и второй раз лейцин, при условии, что он же начинается с ну- ля, принимает значение 010. Таким образом, вся первоначальная битовая после- довательность записана однозначно: 010000 011100 111110 100101 101001. Заключение На основании изложенного следует, что с помощью описанного алгоритма можно записать информацию и затем однозначно ее считать. В качестве примера алгоритм применен к генетическому коду, когда с помощью непрефиксного вы- рожденного кода можно однозначно считывать и записывать без ошибок битовый поток по прочитанной аминокислотной последовательности. Следует также отметить, что указанный в правой колонке таблицы код не яв- ляется вырожденным в обычном понимании этого термина. От рецензента. Работа носит поисковый характер, и идея использования непрефиксного вырожденного кода может быть осуществлена при решении практических задач. В качестве примера алгоритм применен к генетическому ко- ду. Заметим, что этот пример не совсем удачен, поскольку в живой природе за- действован универсальный генетический код, поэтому изменить его невозможно. К.В. Дядьков ВИКОРИСТАННЯ НЕПРЕФІКСНОГО ВИРОДЖЕНОГО КОДУ ПРИ ЧИТАННІ ТА ЗАПИСУ ІНФОРМАЦІЇ Описано алгоритм читання і запису інформації за допомогою непрефіксного ви- родженого коду. Алгоритм побудовано на ідеї використання першого біта сим- вола, наступного за поточним символом, як префіксного. Як приклад викорис- тання алгоритму розглянуто випадок читання і запису довільного бітового по- току, при цьому структура коду, за допомогою якого здійснювалося читання і запис інформації, збіглася зі структурою генетичного коду. K.V. Dyadkov USAGE OF NON-PREFIX DEGENERATE CODE AT INFORMATION READING AND WRITING This article presents a description of information reading and writing algorithm by means of non-prefix degenerate code. The algorithm is based on the idea of usage of the first bit of a symbol following the current symbol as a prefix one. As an example of the algorithm application the case of reading and writing of a random bit stream is considered. Therewith code structure by means of which information reading and writing were carried out concurred with the genetic code structure. 1. Кричевский Р.Е. Сжатие и поиск информации. — М. : Радио и связь. — 168 с. 2. Шеннон К. Работы по теории информации и кибернетике. — М. : Изд-во иностр. лит., 1963. — 830 с. 3. Фано Р. Передача информации. Статистическая теория связи. — М. : Мир, 1965. — 438 с. 4. Большая советская энциклопедия. — М. : Сов. энциклопедия, 1969–1978. 5. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архива- торов, сжатие изображений и видео. — М. : ДИАЛОГ-МИФИ, 2003. — 384 с. Получено 15.06.2012 После доработки 11.09.2012

Использование непрефиксного вырожденного кода при чтении и записи информации

Репозитарії

Схожі ресурси