Математические модели для расчета количественных характеристик оптимального квантования информации

Полный текст

Введение

Часть (порция) информации называется квантом. Процесс представления определённого количества информации в виде совокупности квантов называется квантованием информации. Информационные процессы могут сопровождаться своими издержками. Например, при звуковой трансляции текстов, музыки по радио, телевидению временные издержки связаны с необходимостью введения пауз, позволяющих воспринимать их на слух. Письменное представление содержания книги связано с неизбежными издержками на размер шрифта, интервалы между словами, строками. За введение любых издержек, позволяющих улучшить качество восприятия, передачи, хранения информации приходится платить. Минимизировать величину издержек и их стоимость необходимо и в теории информации, особенно в условиях современного информационного бума. По мере увеличения объемов информации, участвующих в процессе хранения, обработки и передачи, растет значимость проблемы оптимального квантования информации.

Первые основополагающие результаты решения класса задач оптимального квантования случайной величины были получены в [1, 2]. В процессе решения практических задач, в которых применяется оптимальное в смысле заполнения квантование информации, разработчику математических моделей систем необходимо рассматривать специфические прикладные вопросы, дополняющие и расширяющие количественные характеристики предложенной математической модели [1]. К таким вопросам можно отнести, например, влияние ошибок на операцию квантования, определение количества используемой информации, учёт контроля элементов квантов, приближённое решение интегрального уравнения, определения плотности вероятности и распределения величины оптимального кванта, нахождение численных значений фракталов распределения. Могут также ставиться и решаться и другие вопросы, не предусмотренные в данной статье [3-8].

Основная математическая модель оптимального квантования

В данной статье используется модель Андронова А.М., Бокоева Т.Н. [1]. Она представляется в следующем виде:

$\text{Ψ}\left(x\right)=(x+c)\underset{0}{\overset{\infty }{\int }}\left(E\right(z/x)+1)dF\left(z\right)$ (1)

где $\Psi \left(x\right)$ – математическое ожидание квантуемой величины распределения $F\left(x\right)$, $x$ – величина кванта, $c$ – величина пробела между квантами, E – наибольшая целая часть числа, заключённого в скобках. Авторы [1] применяют обозначение $M\left(x\right)=\Psi \left(x\right)$. Целью статьи является рассмотрение дополнительных вопросов на основе конкретного распределения вероятностей – нормального распределения. В качестве примера берётся нормальное распределение со следующими значениями параметров $m=120h\text{, σ}=20h\text{,}$ $f\left(x\right)=dnorm(x,m,\text{σ})$ – плотность вероятности, где h является условной единицей времени. Решение (1) представлено в виде графика на Рис. 1. Оптимальная величина кванта, при которой минимальное значение квантованной величины равно $M\left(31\right)=\mathrm{134,139}h.$

 

Рис. 1. Зависимость математического ожидания от величины кванта

 

Рассмотрим указанные во введении вопросы при следующих исходных данных:

нормальное распределение и величина пробела между квантами  $m=120h\text{, σ}=20h\text{, }f\left(x\right)=dnorm(x,m,\text{σ})\text{;}$ $c=5h$ вероятность сохранения элемента кванта исправным, $p=\mathrm{0,95}$ затраты времени на восстановление неисправного элемента кванта $\text{τ}=\mathrm{2,5}h.$

Влияние ошибок элементов кванта на операцию квантования

1. Предположим, что средняя величина времени на исправление всех ошибок в кванте равна $\text{τ}\cdot x(1-p^x)$. Тогда выражение для определения величины оптимального кванта и связанных с новым значением пробела $c+\text{τ}\cdot x(1-p^x)$ информационных затрат на квантование будет определяться из выражения:

$M1\left(x\right)=⌈x+c+\text{τ}\cdot x(1-p^x)⌉\cdot \underset{0}{\overset{\infty }{\int }}\left(trunc\left(\frac{z}{x}\right)+1\right)\cdot f\left(z\right)dz$. (2)

2. Предположим, что $\text{τ}1=5ha$ а среднее время на исправление ошибок кванта, определённое при условии применения биномиального распределения ошибок кванта будет определяться по формуле (3).

$b\left(x\right)=\text{τ}1\cdot \sum _{k=0}^x\left[\frac{x!}{(k-1)!\cdot (x-k)1}\cdot {(1-p)}^k\cdot p^{x-k}\right]$. (3)

 

Рис. 2. Математические ожидания рассчитанных квантованных функций

 

На Рис. 2 представлены для сравнения математические ожидания трёх рассчитанных квантованных функций $M\left(x\right)\text{, }M1\left(x\right)\text{, }M2\left(x\right)$.

Оптимальные значения квантов и математические ожидания квантованных величин равны:

$M\left(31\right)=\mathrm{157,032,}M1\left(31\right)=\mathrm{426,155,}$ $M2\left(31\right)=\mathrm{191,223.}$

Следует отметить, что оптимальная величина кванта сохраняется постоянной, равной $x_0=31$ во всех трёх случаях, а затраты квантования изменяются, что указывается в правых частях трёх равенств. Величина пробелов зависит от величины тактического значения $c$ и величины времени для исправления ошибок квант, которая добавляется к $c$. Средняя величина времени для исправления ошибок зависит от вида распределения ошибок в кванте, вероятности ошибки элемента кванта и затрат на исправление одиночной ошибки в нём. На Рис. 3 и 4 показаны уточнение Рис. 2 и затраты на исправление (восстановление) в рассмотренных двух примерах $d\left(x\right)=\left[\text{τ}\cdot x\cdot (1-p^x)\right]$ и $b\left(x\right)$, определяемого формулой (3).

 

Рис. 3. Математические ожидания рассчитанных квантованных функций с учетом затраты на восстановление

 

Рис. 4. Зависимость затрат на исправление ошибок

Определение количества информации и её максимума при квантовании

1. Предположим, что за единицу времени (скорость) передаётся $I=10ед./h$ информации. Тогда математическое ожидание количества информации определяется выражением:

$M3\left(x\right)=(x\cdot I+c)\cdot \underset{0}{\overset{\infty }{\int }}\left(trunc\right(\frac{z}{x})+1)\cdot f\left(z\right)dz$. (4)

2. При условии 1, но с учётом задержки на восстановление ошибок в кванте

$b\left(x\right)=\text{τ}1\cdot \sum _{k=0}^x\left[\frac{x!}{(k-1)!\cdot (x-k)1}\cdot {(1-p)}^k\cdot p^{x-k}\right]$. (5)

$M4\left(х\right)=\left(х·I+c+b\left(x\right)\right)·\underset{0}{\overset{\infty }{\int }}\left(trunc\right(\frac{z}{x})+1)·f\left(z\right)dz$. (6)

На Рис. 5 представлены графики для выражений (4) и (6).

Из Рис. 5 следуют оптимальные величины квантов равны $x_{30}=31h\text{, }{x}_{40}=110h$ и значения количеств информации при них соответственно $\mathrm{1,374}\text{x}{10}^3\text{ед}\mathrm{.,}\mathrm{1,916}\text{x}{10}^3\text{ед}.$

 

Рис. 5. Зависимость математического ожидания количество информации от величины кванта и задержек на восстановление

Контроль элементов кванта в процессе квантования

Исходные данные:

$m=120h\text{, σ}=20h\text{, }f\left(x\right)=dnorm(x,m,\text{σ})\text{, }q=\mathrm{1,}c=5h\text{, }q1=\mathrm{0,5.}$

где $q\text{, }q1$ – вероятности ошибок элементов кванта.

На Рис. 6 и 7 представлены следующие значения математических ожиданий квантованного распределения:

$MK\left(x\right)=(x\cdot q^x+c)\cdot \underset{0}{\overset{\infty }{\int }}\left(trunc\left(\frac{z}{x}\right)+1\right)\cdot f\left(z\right)dz,$ $MK1\left(x\right):=(x\cdot q{1}^x+c)\cdot \underset{0}{\overset{\infty }{\int }}\left(trunc\left(\frac{z}{x}\right)+1\right)\cdot f\left(z\right)dz,$

$MK2\left(x\right)=(x\cdot q^x+c)\cdot \underset{0}{\overset{\infty }{\int }}\left(trunc\left(\frac{z}{x\cdot q^x}\right)+1\right)\cdot f\left(z\right)dz,$

$MK3\left(x\right):=(x\cdot q{1}^x+c)\cdot \underset{0}{\overset{\infty }{\int }}\left(trunc\left(\frac{z}{x\cdot q1}\right)+1\right)\cdot f\left(z\right)dz.$

 

Рис. 6. Математические ожидания квантованного распределения с учетом ошибок с вероятностью q$MK\left(200\right)=\mathrm{205,002}$, $MK1\left(200\right)=\mathrm{205,002}$

 

Рис. 7. Математические ожидания квантованного распределения с учетом ошибок с вероятностью q1$MK2\left(200\right)=\mathrm{205,002}$, $MK3\left(200\right)=\mathrm{9,207}$

 

Из графиков кривых на рисунках следует, что увеличение вероятности ошибки элементов оптимального (и любого) кванта увеличиваются итоговые показатели квантованного с пробелами распределения вероятностей (в данном случае с 5 единиц до 9,207 единиц).

Применение квантования для последовательного определения значений фракталов распределений вероятностей

Для примера принимаются следующие исходные данные:

$x=\mathrm{0,1..200,}m=120h\text{, σ}=20h\text{, }f\left(x\right)=dnorm(x,m,\text{σ}).$

В рассматриваемом примере применим для ограничения числа определяемых фракталов распределения гипердельтную аппроксимацию [9-10] нормального распределения и ограничимся двумя начальными моментами. Тогда плотность вероятности представится в виде:

$f\left(x\right)\approx \frac{1}{2}\cdot \left(\Delta \right(x-m+\text{σ})+\Delta (x-m-\text{σ}\left)\right),$ (7)

где $∆\left(x\right)$– дельта-функция Дирака, равная $\Delta \left(x\right)=\frac{d}{dx}Ф\left(x\right).$

В нашем случае $f\left(x\right)\approx \frac{1}{2}\cdot \left(\Delta \right(x-120+20)+\Delta (x-120-20\left)\right).$

$\underset{0}{\overset{\infty }{\int }}E\left(\frac{z}{x}\right)\cdot f\left(z\right)dz-1=0.$ (8)

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

математического ожидания

$MM\left(x\right)=(x+c)\cdot \underset{0}{\overset{\infty }{\int }}\left(trunc\left(\frac{z}{x}\right)+1\right)\cdot \left[\frac{1}{2}\left(\Delta \left(z-m+\text{σ}\right)\right)+\Delta \left(z-m-\text{σ}\right)\right]dz,$ (9)

которое приводится к виду:

$MM\left(x\right)=\frac{1}{2}\cdot (x+c)\cdot \left(trunc\left(\frac{m-\text{σ}}{x}\right)+1\right)+\left(trunc\left(\frac{m+\text{σ}}{x}\right)+1\right);$ (10)

второго начального момента

$MB\left(x\right)=\frac{1}{2}\cdot {(x+c)}^2\cdot {\left(trunc\left(\frac{m-\text{σ}}{x}\right)+1\right)}^2+{\left(trunc\left(\frac{m+\text{σ}}{x}\right)+1\right)}^2;$ (11)

среднее квадратическое отклонение определяется по выражениям (10) и (11)

$\text{σσ}\left(x\right)=\sqrt{MB\left(x\right)-MM{\left(x\right)}^2}$. (12)

На Рис. 8-10 представлены графики функций 10, 11, 12.

 

Рис. 8. Математическое ожидание с учетом гипердельтной аппроксимации. $M\left(31\right)=\mathrm{157,032}$, $M\left(30\right)=\mathrm{157,5}$

 

Рис. 9. Второй начальной момент. $M\left(31\right)=\mathrm{2,657}{\text{x10}}^{\text{4}}$, $M{\left(30\right)}^2=\mathrm{2,481}\text{x}{10}^4$

 

Рис. 10. Среднее квадратическое отклонение. $\text{σσ}\left(31\right)=18$

 

В частности, коэффициент корреляции определяется с помощью выражений

$\text{ηη}\left(x\right)=\frac{\text{σσ}\left(x\right)}{MM\left(x\right)}\text{, ηη}\left(31\right)=\mathrm{0,111,}\frac{20}{120}=\mathrm{0,167,}\frac{18}{\mathrm{157,032}}=\mathrm{0,115.}$

Плотность вероятности и функция распределения оптимального кванта определяются из выражений: $x0=-\mathrm{100,}-\mathrm{99..120,}$ $f\left(x0\right)=dnorm\left(x\mathrm{0,}\mathrm{31,}\mathrm{27,}345\right),$ $ff\left(x\right)=dnorm\left(x\text{, }\mathrm{157,5,}18\right),$ $F0\left(x0\right)={\int }_{-100}^{x0}f0\left(z0\right)dz0,$ $F0\left(31\right)=\mathrm{0,5.}$

 

Рис. 11. Плотность вероятности

 

Рис. 12. Функция распределения оптимального кванта

Определение значений фракталов

Значения фракталов определяются из выражений [11]. Пусть задана плотность вероятности f(x) на полуинтервале [0, ∞), требуется представить её в виде убывающей фрактальной последовательности, составленной базовым, основным фракталом Ф₀ и множеством субфракталов СФ_i, i=1, 2, 3… Тогда можно принять следующую формулу для производства фрактализации:

$\underset{0}{\overset{\infty }{\int }}E\left(\frac{z}{x}\right)\cdot f\left(z\right)dz-1=\mathrm{0,}f\left(x\right)=\frac{1}{2}\cdot \left(\Delta \left(x-m+\text{σ}\right)+\Delta \left(x-m-\text{σ}\right)\right).$ (13)

В нашем случае получаем уравнение

$\underset{0}{\overset{\infty }{\int }}trunc\left(\frac{z}{x}\right)\cdot \left[\frac{1}{2}\cdot \left(\Delta \left(z-m+\text{σ}\right)+\Delta \left(x-m-\text{σ}\right)\right)\right]dz-1=0$ (14)

которое приводится к выражению:

$r\left(x\right)=\frac{1}{2}\cdot \left(trunc\left(\frac{m-\text{σ}}{x}\right)+trunc\left(\frac{m+\text{σ}}{x}\right)\right)-1=0.$ (15)

Решение $r\left(x\right)=0$ эквивалентно решению уравнения $\underset{0}{\overset{\infty }{\int }}E\left(\frac{z}{x}\right)\cdot f\left(z\right)dz-1=0.$

Содержательный смысл (13) состоит в том, что математическое ожидание E не должно превышать единичного значения, но и не быть отрицательным. Нужно принять равенство x=Ф₀ и решить полученное нелинейное уравнение относительно неизвестной величины Ф₀. При этом нужно как можно точнее вычислить эту величину. А затем проверить правильность достаточно строгого решения уравнения (13). Эта численная величина и будет представлять базовый, основной факториал. Можно убедиться, что точное решение уравнения (13) достигается при maxФ₀ и оно будет единственным. Оно представлено на Рис. 13, по максимальной
величине абсциссы означает, что нулевой фрактал будет равен Ф₀=100h.

 

Рис. 13. Определение базового фрактала

 

Следующим шагом процесса будет вычисление значения величины первого субфрактала Ф₁. Этот процесс будет аналогичен предыдущему процессу вычисления Ф₀. Но нелинейное уравнение необходимо изменить таким образом, чтобы оно приняло следующую форму:

$\frac{1}{{\displaystyle \underset{0}{\overset{\infty }{\int }}f\left(u\right)du}}\cdot \underset{{Ф}_0}{\overset{\infty }{\int }}E\left(\frac{z-{\text{Ф}}_0}{{\text{Ф}}_1}\right)\cdot f\left(z\right)dz-1=0.$ (16)

Уравнение (16) приводится к виду

$\underset{100}{\overset{\infty }{\int }}trunc\left(\frac{u}{{\text{Ф}}_1}\right)\cdot \left[\frac{1}{2}\cdot \left(\Delta \left(x-m+\text{σ}\right)+\Delta \left(x-m-\text{σ}\right)\right)\right]-1=\mathrm{0,}$ (17)

а (17) – к виду

$rr\left(x\right)=\frac{1}{2}\cdot \left(trunc\left(\frac{m-\text{σ}+100}{x}\right)+trunc\left(\frac{m-\text{σ}-100}{x}\right)\right)-1=0$. (18)

Решая (18), получаем максимальное $x_1=20h,$ для которого $rr\left(20\right)=\mathrm{0,}$ это означает что ${\text{Ф}}_1=20h.$ Максимум нуля наблюдается при 20h.

Таким образом, первый субфрактал определён. Это соответствует Рис. 14.

 

Рис. 14. Определение первого субфрактала

 

Следующим шагом процесса становится вычисление значения величины второго субфрактала Ф₂. Для этого необходимо использовать следующее нелинейное интегральное уравнение:

$\frac{1}{{\displaystyle \underset{{\text{Ф}}_0+{\text{Ф}}_1}{\overset{\infty }{\int }}f\left(u\right)du}}\cdot \underset{{Ф}_0+{Ф}_1}{\overset{\infty }{\int }}E\left(\frac{z-{\text{Ф}}_0-{\text{Ф}}_1}{x}\right)\cdot f\left(z\right)dz-1=\mathrm{0,}$

Исходные данные уравнения для нахождения второго субфрактала представляется в виде:

$x_0={\text{Ф}}_2\cdot z=u+\mathrm{120,}f\left(x\right)=\frac{1}{2}\cdot \left(\Delta \left(x-m+\text{σ}\right)+\Delta \left(x-m-\text{σ}\right)\right),\frac{1}{{\displaystyle \underset{120}{\overset{\infty }{\int }}f\left(z\right)dz}}=\mathrm{2,}$

$\underset{120}{\overset{\infty }{\int }}trunc\frac{z-120}{x}\cdot \left[\Delta \left(z-m+\text{σ}\right)+\Delta \left(z-m-\text{σ}\right)\right]dz-1=0.$

$kk\left(x\right)=\left(trunc\left(\frac{m-\text{σ}+120}{x}\right)+trunc\left(\frac{m+\text{σ}-120}{x}\right)\right)-1=0.$ (19)

На Рис. 15 представлено решение уравнения (19). 

 

Рис. 15. Определение второго субфрактала

 

Из рисунка следует,что ${\text{Ф}}_2=0$. Итак получены значения трёх фракталов ${\text{Ф}}_2=100h,$ ${\text{Ф}}_2=20h,$${\text{Ф}}_2=0.$ Напомним, что это связано с условием применения приближённого гипердельтного распределения для нормального закона распределения с учётом только двух начальных моментов.

Решение всех вычислительных задач выполнялось с помощью вычислительной среды [12].

Заключение

Потребности в решении проблемы оптимального квантования информации в процессах хранения, обработки и передачи больших объемов данных постоянно увеличиваются. Специалистам в области Big Data \ Data Science постоянно приходиться сталкиваться с данной проблемой [13-15]. Однако инженерных моделей и методов решения подобных задач в зарубежной и отечественной литературе встречается не так много. В процессе решения практических задач, в которых применяется оптимальное в смысле заполнения квантование информации, разработчику математических моделей систем необходимо рассматривать специфические прикладные вопросы, дополняющие и расширяющие количественные характеристики предложенной математической модели [1].

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

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

Об авторах

Владимир Александрович Смагин

Военно-космическая академия им. А.Ф. Можайского

Автор, ответственный за переписку.
Email: va_smagin@mail.ru
ORCID iD: 0000-0002-0120-6145
SPIN-код: 7284-5007

ЗДНРФ, доктор технических наук, профессор

Россия, Санкт-Петербург

Владимир Петрович Бубнов

Петербургский государственный университет путей сообщения Императора Александра I

Email: bubnov1950@yandex.ru
ORCID iD: 0000-0002-6742-3011
SPIN-код: 3114-6579
https://www.pgups.ru/sveden/employees/bubnov-vladimir-petrovich

доктор технических наук, профессор

Россия, Санкт-Петербург

Шохрух Холмурзаевич Султонов

Петербургский государственный университет путей сообщения Императора Александра I

Email: sultonovsh@yandex.ru
ORCID iD: 0000-0002-0462-8677
SPIN-код: 7241-7158

аспирант

Россия, Санкт-Петербург

Список литературы

Дополнительные файлы