8 Вычисление n1

в массиве B

готов n - блок

9

1 Выдача n - блока 0

да

1

n1 = n1 - 1

1

да

Рис. 6. Алгоритм декодирования

Считается заданным длина n-блоков, на которые разбита последовательность двоичных символов перед применением КТ. Пусть было принято очередное кодовое слово (блок А2). Зная n , в соответствия с (22) определяем количество разрядов в кодовом слове, отводимое под k. Отсчитываем от начала кодового слова это количество и полученное двоичное число и есть k (блок АЗ).

Зная n и k , в соответствии с (22) (второе слагаемое) определяем количество двоичных разрядов, отводимое под номер S. Затем получаем истинное значение S.

S=S + k(k+1)/2-1

Все это выполняется в блоке А4.

Оставшиеся разряды кодового слова содержат номер b – блок А5. В блоке А6 происходит зануление В — одномерного массива разрядности n - бит, в котором, по окончании декодирования будет находиться исходный n-блок. В блоке А7 присваиваются исходные значения служебным переменным k1 и S1. Их смысл поясним далее.

Начиная с блока А8, происходят восстановление номеров позиций k единиц с суммой S. Операция — обратная вычислению b(n,k,s). Поясним принцип этой операции при помощи Таблицы 1. На основе известных номеров (четыре левых колонки) вычислялся номер b (правая колонка). Теперь же нам известен номер b, и нужно определять номера позиций единиц. Видно, что все возможные номера b(n,k,s) можно разбить на группы при помощи сравнения номеров и значений r(10,4,25), r(9,4,25), r(8,4,25) и т.д. Причем значения r(10,4,25) =14, r(9,4,25) = 6 и т.д., задают наименьшие номера этих групп, т.е. определяют границы групп. Можно заметить, что 4 и 25 это значения, соответственно k и S, а первый параметр первого коэффициента первой группы n1 (в таблице это 10) определяется по формуле:

n1 = min (n, s1-(k1-1) k1/2) – 1, (23)

где исходные значения k1 и S1 задаются в А7.

Формула аналогична (21). А смысл ее в поиске n1 наибольшего возможного номера при заданных значениях n,k,S без единицы, что соответствует i_k - 1 в формуле (22). Пусть, например, b=16. n1 =min(11,25 – 4x3/2) – 1 = 10, (блок А8). Вычисляем b1 = r(10,4,25) =14, (блок А9). Сравниваем b и b1 (блок A10). Поскольку 16 > 14, b входит в первую группу, а i₄ = 11 (блок В1) в соответствующий разряд В заносится 1 (блок В2).

Далее нужно перейти ко второму слагаемому формулы (22). Формируем новое значение k1 (блок В3) и проверяем все ли номера позиций определены (блок В4) и если нет - вычисляются новые значения b,S1,n (блоки В5, 6, 7) с переходом на А8 и т .д.

В нашем случае: k1 = 3 >1, b = 16-14 = 2, S1 = 25— 11 = 14. Далее выполняется описанная выше последовательность действий для нового номера b. Вычисляем n1 (блок А8). Затем, вычисляем b1 = r(9, 3, 14) = 8 (блок А9) Сравниваем b и b1 (блок А10). Поскольку 8 > 2 переходим на блок А11 с возвратом на А9 и т.д.

В итоге, в массиве В будет находиться исходный n - блок (блок В9). В блоке В10 происходят его выдача и в случае необходимости (блок В11) возврат на А1.

Для наглядности рассмотрим кодирование конкретного n - блока, пусть n= 50. Возьмем n -блок:

50 49 48 47 46...11 10 9 8 7 6 5 4 3 2 1

А = 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0

После приема первого бита (блок А6), I становятся равным 1. Поскольку А (I) = 0, переходим на В5. Так как I<n переходим на А6. I = 2 , А(I) = 1. В блоке В3 вычисляем значение r(1,1,2) = 0.

В блоке В4 прибавляем вычисленное значение к текущему значению b. Поскольку I<n переходим на А6 и т.д.

Далее вычисляем значения: r(2,2,5) = 0; r(З,З,9) =0 ; r(8,4,18) = 8.

Суммарный номер (блок В4) будет равен: b = 0 + 0 + 0 + 8 = 8. Как только I будет равно 50 (блок В5), перейдем на В6. К этому моменту k = 4, S = 18, b = 8. В блоке В6, S будет преобразовано: S = S – k (k+1)/2 + 1 = 9.

Далее вычисляем значение r (50,4,18) = 17. Теперь мы можем определить количество разрядов, отводимое в кодовом слове для каждого из трех параметров (см. (9)).

L=]log ₂ 51[+ ]log ₂ 185[+]log ₂ 17[ =6 + 8 + 5 = 19.

Кодовое слово будет выглядеть:

W = 000100 00001001 01000

k = 4 S = 9 b = 8

Таким образом, в результате кодирования, вместо 50 символов, требуется 19.

В блоке В8 происходит выдача 19 символов, соответствующих кодовому слову. В случае необходимости, переходим на А2.

Рассмотрим пример декодирования.

Для наглядности рассмотрим декодирование конкретного кодового слова, полученного в приведенном ранее примере.

Вычисляем ]log ₂ 51[= 6. Отсчитываем в кодовом слове слева это количество разрядов и получаем k = 000100 = 4 (блок АЗ). Таким образом, в исходном n —блоке есть 4 единицы. Далее вычисляем ]log ₂ (4(50 – 4) + 1)[= 8. Отсчитываем 8 разрядов (начиная с 7—го) и получаем S = 00001001 = 9. Получаем истинное значение S = 9 + 4x5/2 – 1 = 18 (блок А4). Следовательно, исходный блок содержит 4 единицы с суммой позиций 18.

Номер конкретного n – блока из всех имеющих данные k и S записан в последних 5 разрядах.

b = 01000 = 8 (блок А5).

В соответствии с (23) (блок А8):

n1 = min (50, 18 – 3x4/2) - 1 = 11.

Далее вычисляем b1 = r(12,4,18) = 20, (блок А9). Сравниваем b и b1: 8 < 20, поэтому n = 11 (блоки АI0 , А11) и переход на А9:

b1 = r (11, 4, 18) = 19 и т.д.

b1 = r (10, 4, 18) = 18

b1 = r (9, 4, 18) = 11

Далее:

b1 = r (8, 4, 18) = 8.

Условие блока АI0 выполняется: I = 9 (блок В1) и b(9) = 1 (блок В2). k1 = k1 – 1 = 3 > 1 (блоки ВЗ, В4), b = 8 – 8 = 0, S1 = 18 – 9 = 9, n = 49 блоки (В5, В6, В7) и переход на А8.

n1 = min (49, 9 – 2x3/2) – 1 = 5 (А8):

b1 = r (6, 3, 9) = З.

Сравниваем b и b1: 0 < 3, n1 = 5

b1 = r (5, 3, 9) = 2

b1 = r (4, 3, 9) = 1

И наконец:

b1 = r (3, 3, 9) = 0

i = 4 (B1), b (4) = 1, k1 = 2 > 1, b = b – b1 = 0,

S1 = 9 – 4 = 5, n = 48, переход на А8:

n1 = min (48, 5 – 1x2/2) – 1 = 4,

b1 = r (4, 2, 5) = 2 > b

b1 = r (3, 2, 5) = 1 > b

b1 = r (2, 2, 5) = 0 = b → i = 3, b (3) = 1, k1 = 1;

b = 0, S1 = 5 – 3 = 2, n = 47, переход на А8.

n1 = min (47, 2 – 0x1/2) – 1 = 1

b1 = r (1, 1, 2) = 0 = b

i = 1 + 1 = 2, b (2) = 1, k1 = 0 <1, переход на В9.

В результате, в массиве блока В9 должен находиться исходный n - блок. Мы получили, что b(9), b(4), b(3) и b(2) равны 1, остальные 0 (блок А6).

50 49 48 47........10 9 8 7 6 5 4 3 2 1

В= 0 0 0 0..........0 1 0 0 0 0 1 1 1 0

Сопоставив значение содержимого В с n – блоком примера кодирования можно убедиться, что декодирование проведено верно.

Далее рассмотрим вопросы практической реализации КТ.

Трудоемкость реализации, определяемая (в теории кодирования) эквивалентным объемом памя­ти и числом операций сложения, требуемых для реализации КТ, характеризуется степенной зависимостью от длины исходных блоков (1 n 3).

На рис. 7 представлены графики зависимости коэффициента сжатия от длины исходного блока для различных значений p.

2 0, 0

P=0,001

1/H (p)=12,35

1

P=0, 01

0, 0

9, 0

8 , 0

7 , 0

6, 0

P=0,001

5 , 0

4 . 0

3

P=0, 01

, 0

1/H (p) =2, 13

2

P=0, 1

, 0

P=0, 1

1/H (p) =1, 00

1, 0

P=0, 5

0 , 8

0 , 7

0 , 6

0 , 5

0 , 4

16 32 40 50 64 70 80 90 100 110 128 140 n

Рис. 7. Зависимости коэффициентов сжатия от n для различных значений p

В частности, коэффициент сжатия исходных блоков длиной 128 бит находится в пределах от 2 до 20 для вероятностей появ­ления единицы в пределах от 0,1 до 0,001. При этом для реализации требуется порядка 10⁴ бит. Современные достижения в области микроэлектроники и интеграции: чипы флэш памяти, ЭВМ на одном кристалле, использование нанотехнологий, позволяют реализовать на практике разбиения на блоки порядка 10000 бит (цифра раннее немыслимая). При самом «быстром», табличном способе реализации – требуется 4,8 гигабайт памяти, что соответствует объему современной флэшки, а сжатие лежит в диапазоне от 2 до 80, практически достигая теоретического максимума.

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

Возможны следующие варианты реализации КТ:

1. Программный подход, при помощи ЭВМ.

2. Аппаратно программный способ, при помощи одноплатного компьютера, например калифорнийской компании «Gamstix Technology» (размером с пластинку жвачки). Или при помощи ЭВМ на одном кристалле, например фирмы INTEL (single-chip) на базе процессора Intel XScale и памяти Strata Flash.

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

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

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

Сжатые данные

.

«Источник данных» (блок В1) и «Внешний генератор» (блок С1) являются внешними по отношению к микросхеме. Предполагается, что данные представляют собой бинарную последовательность, каждый бит которой поступает по импульсу внешнего генератора. Выходная кодовая бинарная последовательность (блок А8) выдается по синхроимпульсам внутреннего генератора (блок А2).

Процесс приема, кодирования и выдачи управляется контроллером (блок А7), в частности он определяет начало и конец выдачи каждого параметра кодового слова, поскольку кодовые слова имеют переменную длину. В блоках флэш-памяти (А3,4,5) заранее записаны параметры необходимые для формирования кодового слова для заданной длины исходного блока n.

Вентиль (блок А2) пропускает импульсы внутреннего генератора только, если источник данных выдает «единицу». Соответствующие счетчики и сумматоры (блоки В2, С2, D2, C5), а так же КЭШ (блок D3) формируют параметры необходимые для служебного регистра адреса (блок А6) с последующим обращением к соответствующим массивам памяти для извлечения из них данных необходимых для формирования кодового слова.

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

В качестве примера, рассмотрим микросхему фирмы SAMSUNG, с ячейками памяти NAND – K9LAG08U0M 16 Гбит (2048М х 8 бит) NAND Flash. Микросхема размещена в корпусе типа TSOP (прямоугольник длиной 12 мм, шириной 20 мм, толщиной 0,5 мм). Диапазон напряжения питания от 2,7 В до 3,6 В.

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

Напомним, что в период формирования направления «Универсальное кодирования» (60 – 80 годы прошлого столетия) основным препятствием реализации теоретических разработок являлась высокая (по тем временам) трудоемкость кодирования. Никто даже представить не мог, что возможно создание микросхем объемом 16 Gb. Система команд и объем памяти такой микросхемы позволяет реализовать кодирование для длины исходных блоков порядка сотен и тысяч бит (цифры ранее казавшиеся немыслимыми). Это позволяет достигать практически теоретического максимума сжатия двоичных данных в условиях неизвестной статистики с возможностью последующего полного восстановления.

Рис. 9. Блок – схема микросхемы памяти K9LAG08U0M

Схема содержит блоки:

• Buffers Latches & Decoders – буферы с «заслонками» и дешифраторы адресов строк и столбцов массива памяти.

• Flash ARRAY – массив ячеек памяти.

• Data Register & S/A – регистр данных и селектор адреса.

• Cache Register – «кэш – регистр» позволяющий распараллелить выбор и работу с ячейками.

• Y – Gating – шлюз «пропускающий» входные данные в массив памяти и «выпускающий» их оттуда.

• I/O Buffers & Latches – входные / выходные буферы и «заслонки».

• Command Register – регистр команд.

• Control Logic & High Voltage Generator – управляющий контроллер и встроенный высоковольтный генератор для программирования.

• Global Buffers – «глобальные» буферы - регистры общего назначения, содержимое которых (адреса, данные) определяется контроллером.

• Output Driver – порты для связи с внешним миром.

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

Операция чтения выполняются постранично, в то время как операция стирания выполняется только поблочное. Стирание отдельных битов невозможно. Операция записи выполняется за 300 мкс на страницу. Операция стирания выполняется за 2 мс на блок. Байт данных считывается со страницы за 50 нс.

Ножки ввода - вывода соединены с портами для обращения к микросхеме, через них осуществляются операции ввода/вывода команд/адресов/данных.

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

У микросхемы реализована система обеспечения проверки информации с исправлением ошибок и выбраковкой ошибочных данных в реальном времени.

Микросхема имеет 8 мультиплексных  адресных вводов - выводов. Ввод команд, адреса и данных производятся при низком уровне на выводе CE, по спаду сигнала WE, через одни и те же ножки ввода/вывода. Вводимая информация защёлкивается в регистрах по фронту сигнала WE.

Сигналы разрешения защёлкивания команды (CLE), и разрешения защёлкивания адреса (ALE), используются, чтобы мультиплексировать команду и адрес соответственно, через одни и те же ножки ввода/вывода.

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

Оптимальным решением было бы создание оригинальной микросхемы, на основе флэш-технологий, реализующей алгоритм на рис. 2 и блок-схему на рис. 3.

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

Далее рассмотрим пример конкретного применения КТ в медицине.

Беспроводная капсульная эндоскопия — новый метод исследования желудочно-кишечного тракта. В отличие от известных до его изобретения методов, он единственный позволяет полностью осмотреть тонкую кишку без хирургического вмешательства. Суть его заключается в следующем: пациент проглатывает миниатюрную капсулу "Ландыш", запивая небольшим количеством воды, и в течение примерно восьми часов капсула фотографирует его желудочно-кишечный тракт. Съемка производится два раза в секунду. Изображения затем передаются с помощью беспроводной связи на внешнее устройство, которое пациент в течение всего исследования носит на поясе. По окончании процедуры капсула выводится из организма естественным путём. Важно отметить, что при капсульной эндоскопии пациент вообще не испытывает неприятных ощущений.

За время, в течение которого капсула проходит весь ЖКТ, на носителе накапливается порядка 57 тысяч изображений. После завершения исследования эти изображения передаются на стационарный компьютер, где происходит их обработка: распознавание патологий, если таковые имеются, и улучшение качества изображений в случае необходимости.

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

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

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

Рассмотрим в общих чертах процесс обмена информацией внутри системы.

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

Область применения устройста накладывает жесткие ограничения на схему сжатия, а именно:

1. Низкое энергопотребление, ведь капсула работает на батарее, и таким образом высокие потребляемые мощности сократят время ее работы.

2. Массив памяти обновляется каждые 0,5 секунд, следовательно, время сжа­тия не должно превышать этого ограничения.

3. Размеры капсулы составляют 1,5-2 см, что накладывает ограничение на размер микросхемы. Оптимальным вариантом станет размещение на кристалле размером 5*5мм.

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

1. КТ обрабатывает входной блок за меньшее количество тактов, чем другие методы.

2. КТ имеет больший коэффициент сжатия.

3. Для реализации КТ при длине блока в 48 бит требуется меньшее количество памяти.

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

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

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

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