Полноразрядное кодирование что это


Кодирование (медицина) — Википедия

Материал из Википедии — свободной энциклопедии

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 2 мая 2019; проверки требуют 10 правок. Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 2 мая 2019; проверки требуют 10 правок. У этого термина существуют и другие значения, см. Кодирование.

«Кодирование», в наркологии, — обобщенный термин, обозначающий наукообразно оформленные методы внушения с целью лечения табачной, алкогольной и наркотической зависимости «за один сеанс»[1][2]. Эти методы применяются в России и на постсоветском пространстве и связаны с внушением больному угрозы смерти, в том случае, если он злоупотребит алкоголем или наркотиком[3]. Они не имеют какого-либо научного обоснования, однако 14 % врачей-наркологов в России считают их эффективными или относительно эффективными[3].

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

Начало термину «кодирование» положил А. Р. Довженко (номер патента SU 1165392 А «Способ лечения хронического алкоголизма»). Цитата из патента А. Р. Довженко:

Способ лечения хронического алкоголизма - создание отрицательного условного рефлекса на алкоголь, отличающийся тем, что, с целью сокращений сроков лечения и предотвращения интоксикации организма, через 2-2,5 ч после начала создания отрицательного условного рефлекса больному производят раздражение блуждающего и тройничного нервов путём механического надавливания на точки Валле в течение 2-5 с, затем орошают поверхность зева и полость рта хлорэтилом в количестве 0,2 −0,3 мл в течение 1-2 с.

Е. М. Крупицкий выделяет следующие виды наукообразного шарлатанства в российской наркологии[1]:

  1. Фармакологическое: «Торпедо», «Эспераль», «Блок» и т. п.
  2. Инструментальное: магнитно-резонансная терапия, транскраниальная стимуляция и т. п.
  3. Психотерапевтическое: кодирование, видеокассеты и т. д.

Механизм действия состоит в том, что врач убедительно говорит своему пациенту: «Если выпьешь — умрёшь»[источник не указан 20 дней]. Данные методы используют «неведение людей» и их «веру», для поддержания страха, который заставляет людей воздерживаться от употребления алкоголя[5]. «Подшивка» действует не в теле больного, а в терапевтическом сообществе, которое функционирует наподобие религиозной секты, индоктринирующей верования, необходимые для контроля, через организованный социальный ритуал. Контроль этот имеет обманчиво-добровольный характер, так как основан на иллюзии контрактных отношений. Его механизм состоит в профессионально организованном воздействии на тело пациента, а также его семью, финансы и образ жизни. Главным, самым парадоксальным и одновременно самым типическим в этом манипулятивном механизме является угроза смерти, которую через посредничество врача-профессионала применяет к самому себе пациент[6].

Российское общество в целом не информировано о том, что практики так называемого «кодирования», «подшивки» и прочих разновидностей «плацебо-лечения» являются шарлатанскими манипуляциями, основанными на нарушении врачебной этики и прав пациента, его запугивании, и непредоставлении пациенту достоверной информации о его заболевании и о научно-обоснованных методах лечения[5]. Контент-анализ запатентованных методов лечения зависимости в СССР и России выявил преобладание вмешательств с однократным воздействием на ЦНС[7]. Значительная часть их представляет опасность для пациентов, причудлива и научно необоснованна[8]. Большая часть предложенных и запатентованных методов лечения зависимости в России псевдонаучны и представляют собой так называемую плацебо-терапию[9]. Подобные виды воздействия противоречат мировой практике лечения наркологических больных[10].

  1. 1 2 Крупицкий Е. М. Краткосрочное интенсивное психотерапевтическое вмешательство в наркологии с позиций доказательной медицины // Неврологический вестник — 2010, № 3. — С. 25—27.
  2. Плоткин Ф. Б. Комментарии к „комментариям“, или приведет ли неоднократное повторение апологетами „кодирования по А. Р. Довженко“ его достоинств к появлению новых прозелитов? // Психиатрия, психотерапия и клиническая психология. — Минск: Профессиональные издания, 2010. — № 1. — С. 121-128.
  3. 1 2 M. N. Torban R. Heimer, R. D. Ilyuk, E. M. Krupitsky. Practices and Attitudes of Addiction Treatment Providers in the Russian Federation // J Addict Res Ther. — 2011. — Т. 2, № 1. — ISSN 2155-6105. — doi:10.4172/2155-6105.1000104.
  4. ↑ А. А. Александров, К. Ю. Королев, О. Р. Айзберг. «Код Да’Вженко», или ещё раз к вопросу о так называемой стрессопсихотерапии. // Психиатрия: научно-практический журнал. — 2008. № 2. — С. 121—127. (неопр.) (недоступная ссылка). Дата обращения 5 февраля 2013. Архивировано 4 марта 2016 года.
  5. 1 2 Райхель Е. Применение плацебо в постсоветском периоде: гносеология и значение в лечении алкоголизма в России. Часть I // Неврологический вестник — 2010 — Т. XLII, № 3 — С. 9—24
  6. О. Чепурная, А. Эткинд. Инструментализация смерти. Уроки антиалкогольной терапии // Отечественные записки. — № 2 (29) 2006.
  7. ↑ Сошников С. С., Владимиров С. К., Сосунов Р. А., Власов В. В., Граница А. С., Смирнов А. А. Контент-анализ запатентованных методов лечения наркологических расстройств в России. // Неврологический вестник — 2011 — Т. XLIII, № 4 С. 3 — 7.
  8. ↑ Примеры патентов.
  9. ↑ Запатентованные методы лечения наркоманий в России.
  10. Райхель Е. Применение плацебо в постсоветском периоде: гносеология и значение в лечении алкоголизма в России. Часть II // Неврологический вестник — 2010 — Т. XLII, № 4 — С. 49—57.

ru.wikipedia.org

Свёрточный код — Википедия

Свёрточный код — это корректирующий ошибки код, в котором

  1. на каждом такте работы кодера k{\displaystyle k} символов входной полубесконечной последовательности преобразуются в n>k{\displaystyle n>k} символов выходной последовательности
  2. в преобразовании также участвуют m{\displaystyle m} предыдущих символов
  3. выполняется свойство линейности (если двум кодируемым последовательностям x{\displaystyle \mathbf {x} } и y{\displaystyle \mathbf {y} } соответствуют кодовые последовательности X{\displaystyle \mathbf {X} } и Y{\displaystyle \mathbf {Y} }, то кодируемой последовательности ax+by{\displaystyle a\mathbf {x} +b\mathbf {y} } соответствует aX+bY{\displaystyle a\mathbf {X} +b\mathbf {Y} }).

Свёрточный код является частным случаем древовидных и решетчатых кодов.

В 1955 году Л. М. Финком, который в то время являлся заведующим кафедрой Ленинградской академии связи, был предложен первый рекуррентный код.

В 1959 году западный специалист Хегельбергер (Hegelbeger), не имевший представления о работе советских ученых в области кодирования, «вновь открыл» рекуррентный код и назвал его своим именем.

Сам Финк в своей монографии «Теория передачи дискретных сообщений»[1] писал: «В этом коде последовательность кодовых символов не разделяется на отдельные кодовые комбинации. В поток информационных символов включаются корректирующие символы так, что между каждыми двумя информационными символами помещается один корректирующий. Обозначая информационные символы через ai{\displaystyle a_{i}}, а корректирущие через bi{\displaystyle b_{i}} получаем такую последовательность символов:

a1b1a2b2a3b3…akbkak+1bk+1…{\displaystyle a_{1}b_{1}\,a_{2}b_{2}\,a_{3}b_{3}\,\dots \,a_{k}b_{k}\,a_{k+1}b_{k+1}\,\dots }

Информационные символы определяются переданным сообщением, а корректирующие формируются по следующему правилу:

bi=(ak−s+ak+s+1)mod2{\displaystyle b_{i}=\left(a_{k-s}+a_{k+s+1}\right)\mod 2} (1.1)

где s{\displaystyle s} — произвольное целое число, называемое шагом кода (s=0,1,2…{\displaystyle s=0,1,2\dots }). Очевидно, что при ошибочном приеме некоторого корректирующего символа bi соотношение (1.1) в принятой последовательности не будет выполнено для i=k{\displaystyle i=k}. В случае же ошибочного приема информационного символа ai{\displaystyle a_{i}} соотношение (1.1) не будет выполняться при двух значениях ki{\displaystyle k_{i}}, а именно при k1=i−s−1{\displaystyle k_{1}=i-s-1} и при k2=i+s{\displaystyle k_{2}=i+s}. Отсюда легко вывести правило исправления ошибок при декодировании. В принятой кодовой последовательности для каждого bk{\displaystyle b_{k}} проверяется соотношение (1.1). Если оно не выполняется при двух значениях k{\displaystyle k} (k=k1{\displaystyle k=k_{1}} и k=k2{\displaystyle k=k_{2}}), и при этом

k2−k1=2s+1{\displaystyle k_{2}-k_{1}=2s+1} (1.2)

то информационный элемент ak1+s+1{\displaystyle a_{k_{1}+s+1}} должен быть заменен на противоположный.

Очевидно, что избыточность кода равна 1/2{\displaystyle 1/2}. Он позволяет исправлять все ошибочно принятые символы, кроме некоторых неудачных сочетаний. Так, если s=0{\displaystyle s=0}, он обеспечивает правильное декодирование, когда между двумя ошибочно принятыми символами имеется не менее трех (а в некоторых случаях двух) правильно принятых символов (при этом учитываются как информационные, так и проверочные символы).»

Схема кодера нерекурсивного свёрточного кода представлена на Рис.1. Он состоит из k{\displaystyle k} q{\displaystyle q}-ичных регистров сдвига с длинами m1.m2,...,mk{\displaystyle m_{1}.m_{2},...,m_{k}}. Некоторые (может и все) входы регистров и выходы некоторых ячеек памяти соединены с несколькими n{\displaystyle n} сумматорами по модулю q{\displaystyle q}. Число сумматоров больше числа регистров сдвига: n>k{\displaystyle n>k}

Рис.1. Общая схема кодирования свёрточным кодом

На каждом такте работы кодера на его вход поступает k{\displaystyle k} информационных символов, они вместе с хранящимися в регистрах сдвига символами поступают на входы тех сумматоров, с которыми имеется связь. Результатом сложения является n{\displaystyle n} кодовых символов, готовых к передаче. Затем в каждом регистре сдвига происходит сдвиг: все ячейки сдвигаются вправо на один разряд, при этом крайние левые ячейки заполняются входными символами, а крайние правые стираются. После этого такт повторяется. Начальное состояние регистров заранее известно (обычно нулевое).

  • Суммарная длина m=∑i=1kmi{\displaystyle m=\sum _{i=1}^{k}m_{i}} всех регистров сдвига называется кодовым ограничением, а максимальная длина w=max{m1,...,mk}{\displaystyle w=\max\{m_{1},...,m_{k}\}} — задержкой.
  • Значения регистров сдвига в каждый момент времени называется состоянием кодера.

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

Свёрточный кодер — это устройство, принимающее на каждом такте работы в общем случае k входных информационных символов, и выдающее на выход каждого такта n выходных символов. Число R=kn{\displaystyle R={\frac {k}{n}}} называют относительной скоростью кода. k — число информационных символов, n — число передаваемых в канал связи символов за один такт поступления на кодер информационного символа. Выходные символы рассматриваемого такта зависят от m информационных символов, поступающих на этом и предыдущих тактах, то есть выходные символы свёрточного кода однозначно определяются его входными символами и состоянием, которое зависит от m — k предыдущих информационных символов. Основными элементами свёрточного кода являются: регистр сдвига, сумматор по модулю 2, коммутатор.

Регистр сдвига (англ. Shift register) — это динамическое запоминающее устройство, хранящее двоичные символы 0 и 1. Память кода определяет число триггерных ячеек m в регистре сдвига. Когда на вход регистра сдвига поступает новый информационный символ, то символ, хранящийся в крайнем правом разряде, выводится из регистра и сбрасывается. Остальные символы перемещаются на один разряд вправо и, таким образом, освобождается крайний левый разряд куда будет поступать новый информационный символ.

Сумматор по модулю 2 осуществляет сложение поступающих на него символов 1 и 0. Правило сложения по модулю 2 таково: сумма двоичных символов равна 0, если число единиц среди поступающих на входы символов четно, и равно 1, если это число нечетно.

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

Систематический свёрточный код — это код, содержащий в своей выходной последовательности кодовых символов породившую её последовательность информационных символов. Иначе код называют несистематическим.

Параметры и характеристики свёрточных кодов[править | править код]

При свёрточном кодировании преобразование информационных последовательностей в выходные и кодовые происходит непрерывно. Кодер двоичного свёрточного кода содержит сдвигающий регистр из m разрядов и сумматоры по модулю 2 для образования кодовых символов в выходной последовательности. Входы сумматоров соединены с определёнными разрядами регистра. Коммутатор на выходе устанавливает очередность посылки кодовых символов в канал связи. Тогда структуру кода определяют нижеследующие характеристики.

  1. Число информационных символов, поступающих за один такт на вход кодера — k.
  2. Число символов на выходе кодера — n, соответствующих k, поступившим на вход символам в течение такта.
  3. Скорость кода определяется отношением R=k/n и характеризует избыточность, вводимую при кодировании.
  4. Избыточность кода ϑ=1−R{\displaystyle \vartheta =1-R}
  5. Память кода (входная длина кодового ограничения или информационная длина кодового слова), определяется максимально степенью порождающего многочлена в составе порождающей матрицы G(X):l=kmaxi,jbdeg⁡gi,j(x)+1c{\displaystyle l=k{\underset {i,j}{\max }}{\mathcal {b}}\deg g_{i,j}(x)+1{\mathcal {c}}}
  6. Маркировка сверточного кода обозначается в большинстве случаев (n, k, l), но возможны и вариации.
  7. Вес w двоичных кодовых последовательностей определяется числом «единиц», входящих в эту последовательность или кодовые слова.
  8. Кодовое расстояние d{\displaystyle d} показывает степень различия между i-й и j-й кодовыми комбинациями при условии их одинаковой длины. Для любых двух двоичных кодовых комбинаций кодовое расстояние равно числу несовпадающих в них символов. В общем виде кодовое расстояние может быть пределено как суммарный результат сложения по модулю 2 одноимённых разрядов кодовых комбинаций
    di,j=∑k=1Lki,k⊕kj,k{\displaystyle d_{i,j}=\sum _{k=1}^{L}k_{i,k}\oplus k_{j,k}}, где ki,j{\displaystyle k_{i,j}} и kjk{\displaystyle k_{jk}} — k-е символы кодовых комбинаций i и j; L- длина кодовой комбинации.
  9. Минимальное кодовое расстояние dmin{\displaystyle d_{min}} — это наименьшее расстояние Хемминга для набора кодовых комбинаций постоянной длины. Для его нахождения необходимо перебрать все возможные пары кодовых комбинаций. Тогда получаем dmin=mindij{\displaystyle d_{min}=\min d_{ij}}.

Но! Это определение справедливо для блочных кодов, имеющих постоянную длину. Сверточные коды являются непрерывными и характеризуются многими минимальными расстояниями, определяемыми длинами начальных сегментов кодовых последовательностей, между которыми берется минимальное расстояние. Число символов в принятой для обработки длине сегменты L определяет на приемной стороне число ячеек в декодирующем устройстве.

Общий вид двоичного сверточного кодера[править | править код]

Пусть регистр сдвига содержит m ячеек, то есть память кода равна m, коммутатор производит один цикл опроса, проходя значения 1≤k<m{\displaystyle 1\leq k<m} информационных символов, где m кратно k, при этом за один цикл он опрашивает n≥{\displaystyle \geq }2 выходов кодера. Количество выходных кодовых символов, на которые оказывает влияние изменение одного входного информационного символа, равно Iall=mnk{\displaystyle I_{all}={\frac {mn}{k}}}. Величина Iall называется полной длиной кодового ограничения.

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

Связь j-го сумматора по модулю 2 описывается j-ой порождающей последовательностью:

gj=(gj0, gj1,gj2,…,gjm-1), (4.1)

где gij={1,if stage i of register tied with XOR gate0,in other cases{\displaystyle g_{ij}={\begin{cases}1,&{\text{if stage i of register tied with XOR gate}}\\0,&{\text{in other cases}}\end{cases}}} (4.2)

Типичные параметры сверточных кодов: k, n= 1,2,…,8; R=k/n=1/4,…,7/8; m=2,…,10.

Свёрточный код удобно задавать с помощью порождающих многочленов, которые определяются видом формулы (4.1) по аналогии с тем, как это осуществляется для линейных блоковых циклических кодов.[2]

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

A(X)=a0+a1X+a2X2+…,{\displaystyle A(X)=a_{0}+a_{1}X+a_{2}X^{2}+\dots ,}

где Xi — символ оператора задержки на i тактов работы сдвигающего регистра, ai = {0, 1} — информационные двоичные символы. Многочлены, описывающие n последовательностей кодовых символов, поступающих на вход коммутатора кодера, а затем в канал связи, имеют вид

Bj(X)=b0j+b1jX+b2jX2+…,{\displaystyle B_{j}(X)=b_{0}^{j}+b_{1}^{j}X+b_{2}^{j}X^{2}+\dots ,}

где bij={0;1}{\displaystyle b_{i}^{j}=\left\{{0;1}\right\}} двоичные кодовые символы на j-м входе коммутатора кодера.

j-й порождающий многочлен свёрточного кода имеет вид Gj(X)=g0+g1X+g2X2+⋯+gm−1Xm−1{\displaystyle G_{j}(X)=g_{0}+g_{1}X+g_{2}X^{2}+\dots +g_{m-1}X^{m-1}}, где gi=0;1{\displaystyle g_{i}={0;1}} — двоичные коэффициенты, равные 1, если i-я ячейка сдвигающего регистра через схему суммирования связана с j-м коммутатором кодера, и равны 0 в противном случае. Причём, в силу линейности свёрточного кода и принятых обозначений получаем Bj(X)=Gj(X)A(X){\displaystyle B_{j}(X)=G_{j}(X)A(X)}.

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

В общем случае последовательность коэффициентов j-го производящего многочлена будет иметь вид Gj=g0j,g1j,…,gm−1j{\displaystyle G^{j}={g_{0}^{j},g_{1}^{j},\dots ,g_{m-1}^{j}}} и совпадает с порождающей последовательностью кода (4.1). Тогда, если A=a0,a1,a2,…{\displaystyle A={a_{0},a_{1},a_{2},\dots }} — последовательность кодируемых символов, а Bj=b0j,b1j,b2j,…{\displaystyle B_{j}={b_{0}^{j},b_{1}^{j},b_{2}^{j},\dots }} — последовательность кодовых символов на j-м входе коммутатора кодера, то для любого из них, появляющегося в μ{\displaystyle \mu }-й момент времени (μ=0,1,2,…{\displaystyle \mu =0,1,2,\dots }), можно записать

bμj=∑i=0m−1aμ−igij.{\displaystyle b_{\mu }^{j}=\sum _{i=0}^{m-1}a_{\mu -i}g_{i}^{j}.}

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

Свёрточные коды используются для надежной передачи данных: видео, мобильной связи, спутниковой связи. Они используются вместе с кодом Рида — Соломона и другими кодами подобного типа. До изобретения турбо-кодов такие конструкции были наиболее действенными и удовлетворяли пределу Шеннона. Также свёрточное кодирование используется в протоколе 802.11a на физическом MAC-уровне для достижения равномерного распределения 0 и 1 после прохождения сигнала через скремблер, вследствие чего количество передаваемых символов увеличивается в два раза и, следовательно, мы можем добиться благоприятного приема на принимающем устройстве.

  • Галлагер Р. Теория информации и надёжная связь. — М.: Советское радио, 1974. — 720 с.
  • Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.
  • Финк Л. М. Теория передачи дискретных сообщений. — М.: Сов. радио, 1963. — 576 с.
  • Никитин Г. И. Сверточные коды: Учебное пособие. — СПб.: Сов. радио, 2001. — 78 с.
  • Сагалович Ю. Л. Введение в алгебраические коды — 3-е изд., перераб. и доп. — М.: ИППИ РАН, 2014. — 310 с. — ISBN 978-5-901158-24-1
  • Никитин Г. И. Сверточные коды Учебное пособие
  • Банкет, В. Л. "Сигнально-кодовые конструкции в телекоммуникационных системах." О.: Феникс (2009).
  • Колесник В. Д., Полтырев Г. Ш. Курс теории информации. – " Наука," Глав. ред. физико-математической лит-ры, 1982.
  • Нгок Д. К. Исследование методов поиска оптимальных сверточных и перфорированных сверточных кодов : дис. – Диссертация на соискание ученой степени кандидата технических наук. СПб.: ЛЭТИ, 2014.

ru.wikipedia.org

Аналого-цифровой преобразователь — Википедия

Четырёхканальный аналого-цифровой преобразователь

Аналого-цифровой преобразователь[1][2][3] (АЦП, англ. Analog-to-digital converter, ADC) — устройство, преобразующее входной аналоговый сигнал в дискретный код (цифровой сигнал).

Обратное преобразование осуществляется при помощи цифро-аналогового преобразователя (ЦАП, DAC).

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

Разрешение АЦП — минимальное изменение величины аналогового сигнала, которое может быть преобразовано данным АЦП — связано с его разрядностью. В случае единичного измерения без учёта шумов разрешение напрямую определяется разрядностью АЦП.

Разрядность АЦП характеризует количество дискретных значений, которые преобразователь может выдать на выходе. В двоичных АЦП измеряется в битах, в троичных АЦП измеряется в тритах. Например, двоичный 8-разрядный АЦП способен выдать 256 дискретных значений (0…255), поскольку 28=256{\displaystyle 2^{8}=256}, троичный 8-разрядный АЦП способен выдать 6561 дискретное значение, поскольку 38=6561{\displaystyle 3^{8}=6561}.

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

  • Пример 1
    • Диапазон входных значений = от 0 до 10 вольт
    • Разрядность двоичного АЦП 12 бит: 212 = 4096 уровней квантования
    • Разрешение двоичного АЦП по напряжению: (10-0)/4096 = 0,00244 вольт = 2,44 мВ
    • Разрядность троичного АЦП 12 трит: 312 = 531 441 уровень квантования
    • Разрешение троичного АЦП по напряжению: (10-0)/531441 = 0,0188 мВ = 18,8 мкВ
  • Пример 2
    • Диапазон входных значений = от −10 до +10 вольт
    • Разрядность двоичного АЦП 14 бит: 214 = 16384 уровня квантования
    • Разрешение двоичного АЦП по напряжению: (10-(-10))/16384 = 20/16384 = 0,00122 вольт = 1,22 мВ
    • Разрядность троичного АЦП 14 трит: 314 = 4 782 969 уровней квантования
    • Разрешение троичного АЦП по напряжению: (10-(-10))/4782969 = 0,00418 мВ = 4,18 мкВ

На практике разрешение АЦП ограничено отношением сигнал/шум входного сигнала. При большой интенсивности шумов на входе АЦП различение соседних уровней входного сигнала становится невозможным, то есть ухудшается разрешение. При этом реально достижимое разрешение описывается эффективной разрядностью (англ. effective number of bits, ENOB), которая меньше, чем реальная разрядность АЦП. При преобразовании сильно зашумлённого сигнала младшие разряды выходного кода практически бесполезны, так как содержат шум. Для достижения заявленной разрядности отношение сигнал/шум входного сигнала должно быть примерно 6 дБ на каждый бит разрядности (6 дБ соответствует двукратному изменению уровня сигнала).

По способу применяемых алгоритмов АЦП делят на:

АЦП первых двух типов подразумевают обязательное применение в своем составе устройства выборки и хранения (УВХ). Это устройство служит для запоминания аналогового значения сигнала на время, необходимое для выполнения преобразования. Без него результат преобразования АЦП последовательного типа будет недостоверным. Выпускаются интегральные АЦП последовательного приближения, как содержащие в своем составе УВХ, так и требующие внешнее УВХ[источник не указан 1562 дня].

Линейные АЦП[править | править код]

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

Термин линейный применительно к АЦП означает, что диапазон входных значений, отображаемый на выходное цифровое значение, связан по линейному закону с этим выходным значением, то есть выходное значение k достигается при диапазоне входных значений от

m(k + b)

до

m(k + 1 + b),

где m и b — некоторые константы. Константа b, как правило, имеет значение 0 или −0.5. Если b = 0, АЦП называют квантователь с ненулевой ступенью (mid-rise), если же b = −0,5, то АЦП называют квантователь с нулём в центре шага квантования (mid-tread).

Нелинейные АЦП[править | править код]

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

Это тот же принцип, что и используемый в компандерах, применяемых в магнитофонах и различных коммуникационных системах, он направлен на максимизацию энтропии. (Не путать компандер с компрессором!)

Например, голосовой сигнал имеет лапласово распределение амплитуды. Это означает, что окрестность нуля по амплитуде несёт больше информации, чем области с большей амплитудой. По этой причине логарифмические АЦП часто применяются в системах передачи голоса для увеличения динамического диапазона передаваемых значений без изменения качества передачи сигнала в области малых амплитуд.

8-битные логарифмические АЦП с a-законом или μ-законом обеспечивают широкий динамический диапазон и имеют высокое разрешение в наиболее критичном диапазоне малых амплитуд; линейный АЦП с подобным качеством передачи должен был бы иметь разрядность около 12 бит.

Передаточная характеристика АЦП — зависимость числового эквивалента выходного двоичного кода от величины входного аналогового сигнала. Говорят о линейных и нелинейных АЦП. Такое деление условное. Обе передаточные характеристики — ступенчатые. Но для «линейных» АЦП всегда возможно провести такую прямую линию, чтобы все точки передаточной характеристики, соответствующие входным значениям δ⋅2k{\displaystyle \delta \cdot 2^{k}} (где δ{\displaystyle \delta } — шаг дискретизации, k лежит в диапазоне 0..N, где N — разрядность АЦП), были от неё равноудалены.

Имеется несколько источников погрешности АЦП. Ошибки квантования и (считая, что АЦП должен быть линейным) нелинейности присущи любому аналого-цифровому преобразованию. Кроме того, существуют так называемые апертурные ошибки, которые являются следствием джиттера (англ. jitter) тактового генератора, они проявляются при преобразовании сигнала в целом (а не одного отсчёта).

Эти ошибки измеряются в единицах, называемых МЗР — младший значащий разряд (англ.). В приведённом выше примере 8-битного двоичного АЦП ошибка в 1 МЗР составляет 1/256 от полного диапазона сигнала, то есть 0,4 %, в 5-тритном троичном АЦП ошибка в 1 МЗР составляет 1/243 от полного диапазона сигнала, то есть 0,412 %, в 8-тритном троичном АЦП ошибка в 1 МЗР составляет 1/6561, то есть 0,015 %.

Ошибки квантования[править | править код]

Ошибки квантования являются следствием ограниченного разрешения АЦП. Этот недостаток не может быть устранён ни при каком типе аналого-цифрового преобразования. Абсолютная величина ошибки квантования при каждом отсчёте находится в пределах от нуля до половины МЗР.

Как правило, амплитуда входного сигнала много больше, чем МЗР. В этом случае ошибка квантования не коррелирована с сигналом и имеет равномерное распределение. Её среднеквадратическое значение совпадает с среднеквадратичным отклонением распределения, которое равно 112LSB≈0.289 LSB{\displaystyle {1 \over {\sqrt {12}}}\mathrm {LSB} \approx 0.289\ \mathrm {LSB} }. В случае 8-битного АЦП это составит 0,113 % от полного диапазона сигнала.

Нелинейность[править | править код]

Всем АЦП присущи ошибки, связанные с нелинейностью, которые являются следствием физического несовершенства АЦП. Это приводит к тому, что передаточная характеристика (в указанном выше смысле) отличается от линейной (точнее от желаемой функции, так как она не обязательно линейна). Ошибки могут быть уменьшены путём калибровки[4].

Важным параметром, описывающим нелинейность, является интегральная нелинейность (INL) и дифференциальная нелинейность (DNL).

Апертурная погрешность (джиттер)[править | править код]

Пусть мы оцифровываем синусоидальный сигнал x(t)=Asin⁡2πf0t{\displaystyle x(t)=A\sin 2\pi f_{0}t}. В идеальном случае отсчёты берутся через равные промежутки времени. Однако в реальности время момента взятия отсчёта подвержено флуктуациям из-за дрожания фронта синхросигнала (clock jitter). Полагая, что неопределённость момента времени взятия отсчёта порядка Δt{\displaystyle \Delta t}, получаем, что ошибка, обусловленная этим явлением, может быть оценена как

Eap≤|x′(t)Δt|≤2Aπf0Δt{\displaystyle E_{ap}\leq |x'(t)\Delta t|\leq 2A\pi f_{0}\Delta t}.

Ошибка относительно невелика на низких частотах, однако на больших частотах она может существенно возрасти.

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

Δt<12qπf0{\displaystyle \Delta t<{\frac {1}{2^{q}\pi f_{0}}}},

где q{\displaystyle q} — разрядность АЦП.

Разрядность АЦП Максимальная частота входного сигнала
44,1 кГц 192 кГц 1 МГц 10 МГц 100 МГц
8 28,2 нс 6,48 нс 1,24 нс 124 пс 12,4 пс
10 7,05 нс 1,62 нс 311 пс 31,1 пс 3,11 пс
12 1,76 нс 405 пс 77,7 пс 7,77 пс 777 фс
14 441 пс 101 пс 19,4 пс 1,94 пс 194 фс
16 110 пс 25,3 пс 4,86 пс 486 фс 48,6 фс
18 27,5 пс 6,32 пс 1,21 пс 121 фс 12,1 фс
24 430 фс 98,8 фс 19,0 фс 1,9 фс 190 ас

Из этой таблицы можно сделать вывод о целесообразности применения АЦП определённой разрядности с учётом ограничений, накладываемых дрожанием фронта синхронизации (clock jitter). Например, бессмысленно использовать прецизионный 24-битный АЦП для записи звука, если система распределения синхросигнала не в состоянии обеспечить ультрамалой неопределённости.

Вообще качество тактового сигнала чрезвычайно важно не только по этой причине. Например, из описания микросхемы AD9218 (Analog Devices):

Any high speed ADC is extremely sensitive to the quality of the sampling clock provided by the user. A track-and-hold circuit is essentially a mixer. Any noise, distortion, or timing jitter on the clock is combined with the desired signal at the analog-to-digital output.

То есть любой высокоскоростной АЦП крайне чувствителен к качеству оцифровывающей тактовой частоты, подаваемой пользователем. Схема выборки и хранения, по сути, является смесителем (перемножителем). Любой шум, искажения, или дрожание фазы тактовой частоты смешиваются с полезным сигналом и поступают на цифровой выход.

Аналоговый сигнал является непрерывной функцией времени, в АЦП он преобразуется в последовательность цифровых значений. Следовательно, необходимо определить частоту выборки цифровых значений из аналогового сигнала. Частота, с которой производятся цифровые значения, получила название частота дискретизации АЦП.

Непрерывно меняющийся сигнал с ограниченной спектральной полосой подвергается оцифровке (то есть значения сигнала измеряются через интервал времени T — период дискретизации), и исходный сигнал может быть точно восстановлен из дискретных во времени значений путём интерполяции. Точность восстановления ограничена ошибкой квантования. Однако в соответствии с теоремой Котельникова — Шеннона точное восстановление амплитуды возможно, только если частота дискретизации выше, чем удвоенная максимальная частота в спектре сигнала.

Поскольку реальные АЦП не могут произвести аналого-цифровое преобразование мгновенно, входное аналоговое значение должно удерживаться постоянным, по крайней мере, от начала до конца процесса преобразования (этот интервал времени называют время преобразования). Эта задача решается путём использования специальной схемы на входе АЦП — устройства выборки-хранения (УВХ). УВХ, как правило, хранит входное напряжение на конденсаторе, который соединён со входом через аналоговый ключ: при замыкании ключа происходит выборка входного сигнала (конденсатор заряжается до входного напряжения), при размыкании — хранение. Многие АЦП, выполненные в виде интегральных микросхем, содержат встроенное УВХ.

Все АЦП работают путём выборки входных значений через фиксированные интервалы времени. Следовательно, выходные значения являются неполной картиной того, что подаётся на вход. Глядя на выходные значения, нет никакой возможности установить, как вёл себя входной сигнал между выборками. Если известно, что входной сигнал меняется достаточно медленно относительно частоты дискретизации, то можно предположить, что промежуточные значения между выборками находятся где-то между значениями этих выборок. Если же входной сигнал меняется быстро, то никаких предположений о промежуточных значениях входного сигнала сделать нельзя, а следовательно, невозможно однозначно восстановить форму исходного сигнала.

Если последовательность цифровых значений, выдаваемая АЦП, где-либо преобразуется обратно в аналоговую форму цифро-аналоговым преобразователем, желательно, чтобы полученный аналоговый сигнал был максимально точной копией исходного сигнала. Если входной сигнал меняется быстрее, чем делаются его отсчёты, то точное восстановление сигнала невозможно, и на выходе ЦАП будет присутствовать ложный сигнал. Ложные частотные компоненты сигнала (отсутствующие в спектре исходного сигнала) получили название alias (ложная частота, побочная низкочастотная составляющая). Частота ложных компонент зависит от разницы между частотой сигнала и частотой дискретизации. Например, синусоидальный сигнал с частотой 2 кГц, дискретизованный с частотой 1.5 кГц, был бы воспроизведён как синусоида с частотой 500 Гц. Эта проблема получила название наложение частот (aliasing).

Для предотвращения наложения спектров сигнал, подаваемый на вход АЦП, должен быть пропущен через фильтр нижних частот для подавления спектральных компонент, частота которых превышает половину частоты дискретизации. Этот фильтр получил название anti-aliasing (антиалиасинговый) фильтр, его применение чрезвычайно важно при построении реальных АЦП.

Вообще, применение аналогового входного фильтра интересно не только по этой причине. Казалось бы, цифровой фильтр, который обычно применяется после оцифровки, имеет несравненно лучшие параметры. Но, если в сигнале присутствуют компоненты, значительно более мощные, чем полезный сигнал, и достаточно далеко отстоящие от него по частоте, чтобы быть эффективно подавленными аналоговым фильтром, такое решение позволяет сохранить динамический диапазон АЦП: если помеха на 10 дБ сильнее сигнала, на неё впустую будет тратиться, в среднем, три бита разрядности.

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

Некоторые характеристики АЦП могут быть улучшены путём использования методики подмешивания псевдослучайного сигнала (англ. dither). Она заключается в добавлении к входному аналоговому сигналу случайного шума (белый шум) небольшой амплитуды. Амплитуда шума, как правило, выбирается на уровне половины МЗР. Эффект от такого добавления заключается в том, что состояние МЗР случайным образом переходит между состояниями 0 и 1 при очень малом входном сигнале (без добавления шума МЗР был бы в состоянии 0 или 1 долговременно). Для сигнала с подмешанным шумом вместо простого округления сигнала до ближайшего разряда происходит случайное округление вверх или вниз, причём среднее время, в течение которого сигнал округлён к тому или иному уровню, зависит от того, насколько сигнал близок к этому уровню. Таким образом, оцифрованный сигнал содержит информацию об амплитуде сигнала с разрешающей способностью лучше, чем МЗР, то есть происходит увеличение эффективной разрядности АЦП. Негативной стороной методики является увеличение шума в выходном сигнале. Фактически ошибка квантования размазывается по нескольким соседним отсчётам. Такой подход является более желательным, чем простое округление до ближайшего дискретного уровня. В результате использования методики подмешивания псевдослучайного сигнала мы имеем более точное воспроизведение сигнала во времени. Малые изменения сигнала могут быть восстановлены из псевдослучайных скачков МЗР путём фильтрации. Кроме того, если шум детерминирован (амплитуда добавляемого шума точно известна в любой момент времени), то его можно вычесть из оцифрованного сигнала, предварительно увеличив его разрядность, тем самым почти полностью избавиться от добавленного шума.

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

Однако с 2009 года, в связи с удешевлением 24-битных АЦП, имеющих даже без dither’а динамический диапазон более 120 дБ, что на несколько порядков превышает полный воспринимаемый человеком диапазон слуха, данная технология потеряла актуальность в звукотехнике. При этом она используется в ВЧ- и СВЧ-технике, где битность АЦП обычно мала из-за высокой частоты дискретизации.

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

Как правило, сигналы оцифровываются с минимально необходимой частотой дискретизации из соображений экономии, при этом шум квантования является белым, то есть его спектральная плотность мощности равномерно распределена во всей полосе. Если же оцифровать сигнал с частотой дискретизации, гораздо большей, чем по теореме Котельникова — Шеннона, а затем подвергнуть цифровой фильтрации для подавления спектра вне частотной полосы исходного сигнала, то отношение сигнал/шум будет лучше, чем при использовании всей полосы. Таким образом можно достичь эффективного разрешения большего, чем разрядность АЦП.

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

Ниже перечислены основные способы построения электронных АЦП:

АЦП прямого преобразования[править | править код]

  • Параллельные АЦП прямого преобразования (Direct-conversion (Flash) ADC), полностью параллельные АЦП, содержат по одному компаратору на каждый дискретный уровень входного сигнала. В любой момент времени только компараторы, соответствующие уровням ниже уровня входного сигнала, выдают на своём выходе сигнал превышения. Сигналы со всех компараторов поступают либо прямо в параллельный регистр, тогда обработка кода осуществляется программно, либо на аппаратный логический шифратор, аппаратно генерирующий нужный цифровой код в зависимости от кода на входе шифратора. Данные с шифратора фиксируются в параллельном регистре. Частота дискретизации параллельных АЦП, в общем случае, зависит от аппаратных характеристик аналоговых и логических элементов, а также от требуемой частоты выборки значений. Параллельные АЦП прямого преобразования — самые быстрые, но обычно имеют разрешение от 8 бит, как цифровые осциллографы, так как влекут за собой большие аппаратные затраты (2n−1=28−1=255{\displaystyle 2^{n}-1=2^{8}-1=255} компараторов). АЦП этого типа имеют очень большой размер кристалла микросхемы, высокую входную ёмкость, и могут выдавать кратковременные ошибки на выходе. Часто используются для видео или других высокочастотных сигналов, а также широко применяются в промышленности для отслеживания быстро изменяющихся процессов в реальном времени. Профессиональные модели могут иметь разрешение до 14 бит и выше[5].
  • Параллельно-последовательные АЦП прямого преобразования (Subranging Direct-conversion (Flash) ADC)[6] частично последовательные АЦП. Были предложены R. Staffin и R. Lohman R. в 1956 году (Staffin and R. Lohman, «Signal Amplitude Quantizer», U.S. Patent 2,869,079, Filed December 19, 1956, Issued January 13, 1959)[7]. Немного уменьшая быстродействие позволяют значительно уменьшить количество ОУ до k⋅(2n/k−1)+k−1{\displaystyle k\cdot (2^{n/k}-1)+k-1}, где n — число битов выходного кода, а k — число параллельных АЦП прямого преобразования. При 8 битах и 2 АЦП потребуется 31 ОУ. Используют два (k=2) или более шагов-поддиапазонов. При k=2 преобразователь называется Half-Flash (Subranging) ADC. Второй, третий и т. д. АЦП служат для уменьшения ошибки квантования первого АЦП путём оцифровки этой ошибки. На первом шаге производится грубое преобразование (с низким разрешением). Далее определяется разница между входным сигналом и аналоговым сигналом, соответствующим результату грубого преобразования (со вспомогательного ЦАП, на который подаётся грубый код). На втором шаге найденная разница умножается на 2n/k{\displaystyle 2^{n/k}} и подвергается следующему преобразованию. Полученный код объединяется с грубым кодом для получения полного выходного цифрового значения. АЦП этого типа медленнее параллельных АЦП прямого преобразования, имеют высокое разрешение и небольшой размер корпуса. Для увеличения скорости выходного оцифрованного потока данных в параллельно-последовательных АЦП прямого преобразования применяется конвейерная работа параллельных АЦП.
  • Конвейерная работа АЦП (Pipelined Subranging Direct-conversion (Flash) ADC)[8], применяется в параллельно-последовательных АЦП прямого преобразования, в отличие от обычного режима работы параллельно-последовательных АЦП прямого преобразования, в котором данные передаются после полного преобразования, при конвейерной работе данные частичных преобразований передаются по мере готовности до окончания полного преобразования. В 1966 году Kinniment и др. предложили архитектуру параллельно-последовательного АЦП прямого преобразования с рециркуляцией (Recirculating ADC Architecture)[9]. В этой архитектуре используется один поддиапазонный параллельный АЦП прямого преобразования.
  • Последовательные АЦП прямого преобразования (Subranging Direct-conversion (Flash) ADC), полностью последовательные АЦП (k=n), медленнее параллельных АЦП прямого преобразования и немного медленнее параллельно-последовательных АЦП прямого преобразования, но ещё больше (до n⋅(2n/n−1)+n−1=n⋅(21−1)+n−1=2n−1{\displaystyle n\cdot (2^{n/n}-1)+n-1=n\cdot (2^{1}-1)+n-1=2n-1}, где n — число битов выходного кода, а k — число параллельных АЦП прямого преобразования) уменьшают количество ОУ (при 8 битах потребуется 15 ОУ: 8 компараторов на ОУ и 7 вычитателей-умножителей на 2 на ОУ)[10]. Троичные АЦП этого вида приблизительно в 1,5 раза быстрее соизмеримых по числу уровней и аппаратных затрат двоичных АЦП этого же вида[11].

АЦП последовательного приближения[править | править код]

  • АЦП последовательного приближения или АЦП с поразрядным уравновешиванием содержит компаратор, вспомогательный ЦАП и регистр последовательного приближения. АЦП преобразует аналоговый сигнал в цифровой за N шагов, где N — разрядность АЦП. На каждом шаге определяется по одному биту искомого цифрового значения, начиная от СЗР (Старшего Значащего Разряда) и заканчивая МЗР (Младшим Значащим Разрядом). Последовательность действий по определению очередного бита заключается в следующем. На вспомогательном ЦАП выставляется аналоговое значение, образованное из битов, уже определённых на предыдущих шагах; бит, который должен быть определён на этом шаге, выставляется в 1, более младшие биты установлены в 0. Полученное на вспомогательном ЦАП значение сравнивается с входным аналоговым значением. Если значение входного сигнала больше значения на вспомогательном ЦАП, то определяемый бит получает значение 1, в противном случае 0. Таким образом, определение итогового цифрового значения напоминает двоичный поиск. АЦП этого типа обладают одновременно высокой скоростью и хорошим разрешением. Однако при отсутствии устройства выборки хранения погрешность будет значительно больше (представьте, что после оцифровки самого большого разряда сигнал начал меняться).

АЦП дифференциального кодирования[править | править код]

  • АЦП дифференциального кодирования (англ. delta-encoded ADC) содержат реверсивный счётчик, код с которого поступает на вспомогательный ЦАП. Входной сигнал и сигнал со вспомогательного ЦАП сравниваются на компараторе. Благодаря отрицательной обратной связи с компаратора на счётчик код на счётчике постоянно меняется так, чтобы сигнал со вспомогательного ЦАП как можно меньше отличался от входного сигнала. По прошествии некоторого времени разница сигналов становится меньше, чем МЗР, при этом код счётчика считывается как выходной цифровой сигнал АЦП. АЦП этого типа имеют очень большой диапазон входного сигнала и высокое разрешение, но время преобразования зависит от входного сигнала, хотя и ограничено сверху. В худшем случае время преобразования равно Tmax=(2q)/fс, где q — разрядность АЦП, fс — частота тактового генератора счётчика. АЦП дифференциального кодирования обычно являются хорошим выбором для оцифровки сигналов реального мира, так как большинство сигналов в физических системах не склонны к скачкообразным изменениям. В некоторых АЦП применяется комбинированный подход: дифференциальное кодирование и последовательное приближение; это особенно хорошо работает в случаях, когда известно, что высокочастотные компоненты в сигнале относительно невелики.

АЦП сравнения с пилообразным сигналом[править | править код]

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

АЦП с уравновешиванием заряда[править | править код]

  • АЦП с уравновешиванием заряда (к ним относятся АЦП с двухстадийным интегрированием, АЦП с многостадийным интегрированием и некоторые другие) содержат генератор стабильного тока, компаратор, интегратор тока, тактовый генератор и счётчик импульсов. Преобразование происходит в два этапа (двухстадийное интегрирование). На первом этапе значение входного напряжения преобразуется в ток (пропорциональный входному напряжению), который подаётся на интегратор тока, заряд которого изначально равен нулю. Этот процесс длится в течение времени TN, где T — период тактового генератора, N — константа (большое целое число, определяет время накопления заряда). По прошествии этого времени вход интегратора отключается от входа АЦП и подключается к генератору стабильного тока. Полярность генератора такова, что он уменьшает заряд, накопленный в интеграторе. Процесс разряда длится до тех пор, пока заряд в интеграторе не уменьшится до нуля. Время разряда измеряется путём счёта тактовых импульсов от момента начала разряда до достижения нулевого заряда на интеграторе. Посчитанное количество тактовых импульсов и будет выходным кодом АЦП. Можно показать, что количество импульсов n, посчитанное за время разряда, равно: n=UвхN(RI0)−1, где Uвх — входное напряжение АЦП, N — число импульсов этапа накопления (определено выше), R — сопротивление резистора, преобразующего входное напряжение в ток, I0 — значение тока от генератора стабильного тока, разряжающего интегратор на втором этапе. Таким образом, потенциально нестабильные параметры системы (прежде всего, ёмкость конденсатора интегратора) не входят в итоговое выражение. Это является следствием двухстадийности процесса: погрешности, введённые на первом и втором этапах, взаимно вычитаются. Не предъявляются жёсткие требования даже к долговременной стабильности тактового генератора и напряжению смещения компаратора: эти параметры должны быть стабильны лишь кратковременно, то есть в течение каждого преобразования (не более 2TN). Фактически принцип двухстадийного интегрирования позволяет напрямую преобразовывать отношение двух аналоговых величин (входного и образцового тока) в отношение числовых кодов (n и N в терминах, определённых выше) практически без внесения дополнительных ошибок. Типичная разрядность АЦП этого типа составляет от 10 до 18[источник не указан 2341 день] двоичных разрядов. Дополнительным достоинством является возможность построения преобразователей, нечувствительных к периодическим помехам (например, помеха от сетевого питания) благодаря точному интегрированию входного сигнала за фиксированный временной интервал. Недостатком данного типа АЦП является низкая скорость преобразования. АЦП с уравновешиванием заряда используются в измерительных приборах высокой точности.

АЦП с промежуточным преобразованием в частоту следования импульсов[править | править код]

  • АЦП с промежуточным преобразованием в частоту следования импульсов. Сигнал с датчика проходит через преобразователь уровня, а затем через преобразователь напряжение-частота. Таким образом на вход непосредственно логической схемы поступает сигнал, характеристикой которого является лишь частота импульсов. Логический счётчик принимает эти импульсы на вход в течение времени выборки, таким образом, выдавая к её окончанию кодовую комбинацию, численно равную количеству импульсов, пришедших на преобразователь за время выборки. Такие АЦП довольно медленны и не очень точны, но тем не менее очень просты в исполнении и поэтому имеют низкую стоимость.

Сигма-дельта АЦП[править | править код]

  • Сигма-дельта АЦП (называемые также «дельта-сигма АЦП») производит аналого-цифровое преобразование с частотой дискретизации, во много раз превышающей требуемую, и, путём фильтрации, оставляет в сигнале только нужную спектральную полосу.

Неэлектронные АЦП обычно строятся на тех же принципах.

Оптически

ru.wikipedia.org

Что делают, когда кодируют человека от алкоголизма

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

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

Что это такое?

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

Отказ от спиртного

Как работает кодировка?

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

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

Срок кодирования

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

Вшивание ампулы

Устранить симптоматику можно только путем введения антидота, поэтому если закодированный человек выпил, его немедленно необходимо отвести к врачу. Именно поэтому, если пациент кодируется впервые, зашиться от алкоголизма ему предложат на 6 месяцев или на год. Если за этот период пациент не сорвется и достаточно легко перенесет отказ от спиртного, в следующий раз его могут закодировать сразу на 3 года. Максимальный срок кодировки – 5 лет. Стоит учитывать, что эти сроки приблизительны. Сколько действует кодировка от алкоголя зависит не только от выбранного метода, но и от индивидуальных особенностей организма.

Медицинская практика показывает, что самая удачная схема – кодирование 3 раза подряд на срок по 1 году. Пациенты, которые кодируются 1 раз на 5 лет, переносят процедуру значительно тяжелее и часто срываются.

Определяясь с оптимальными сроками кодирования, стоит учитывать, что физическая и моральная тяга к спиртному – 2 разные вещи:

  • психическая зависимость от алкоголя полностью проходит спустя 1-5 лет. Срок зависит от изначального состояния пациента, его силы воли, стадии зависимости и психологического фона в семье;
  • физическое привыкание проходит значительно быстрее – не позднее, чем через 5 месяцев после кодировки. Этого времени достаточно, чтобы организм освободился от последней молекулы спирта.

Если к сроку окончания первого кодирования от алкоголизма пациент не уверен в собственных силах, процедура делается повторно. Повторное вшивание ампулы проводится примерно за 5 дней до окончания срока первой кодировки.

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

Плюсы и минусы кодировки

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

Сохранение семьи

Подобное лечение алкогольной зависимости обладает следующими преимуществами:

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

Что касается слабых сторон, то к минусам кодирования от алкоголизма можно отнести:

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

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

Противопоказания и последствия

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

Имеются противопоказания

Основные противопоказания при кодировании от алкоголизма:

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

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

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

  • нарушение работы желудочно-кишечного тракта, тошнота и рвота;
  • головокружение;
  • потеря координации;
  • тахикардия;
  • озноб;
  • тремор;
  • галлюцинации.

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

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

Гипноз

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

Подготовка к кодированию

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

Перед проведением процедуры нельзя пить. Сколько дней не пить перед кодированием решает доктор, отталкиваясь от состояния пациента и стадии зависимости. Обычно срок варьируется от 3 до 10 суток.

Методы кодирования от алкоголизма

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

  1. Медикаментозное лечение. Суть метода – введение лекарственных средств, которые постепенно нейтрализуют тягу к алкоголю. Как происходит кодировка при этом методе, зависит от типа препарата. Лечение может осуществляться путем вшивания ампул (торпеды), приема таблеток. Также пациенту могут инъекционно ввести ингибиторы этанола. Медикаментозное кодирование дает самый сильный результат, но стоит понимать, что оно одновременно считается самым опасным. Это обусловлено тем, что срывы при такой кодировке сопровождаются серьезными нарушениями в функционировании внутренних органов и систем.
  2. Гипноз. Гипнотерапия бывает индивидуальная или групповая. Положительный эффект достигается благодаря тому, что профессионал внушает пациенту отвращение к спиртному на подсознательном уровне. Если стоит вопрос, как закодировать от алкоголя в домашних условиях, то этот способ считается более предпочтительным.
  3. Психотерапия. Для воздействия на психическое состояние применяют разные методики. Самыми популярными считаются методика Малкина, методы Рожнова и Довженко.

Медикаментозное

Эффект от кодировки

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

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

Заключение

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

zdorovnet.ru

Код с малой плотностью проверок на чётность — Википедия

Код с малой плотностью проверок на чётность (LDPC-код от англ. Low-density parity-check code, LDPC-code, низкоплотностный код) — используемый в передаче информации код, частный случай блочного линейного кода с проверкой чётности. Особенностью является малая плотность значимых элементов проверочной матрицы, за счёт чего достигается относительная простота реализации средств кодирования.

Также называют кодом Галлагера, по имени автора первой работы на тему LDPC-кодов.

В 1948 году Шеннон опубликовал свою работу по теории передачи информации. Одним из ключевых результатов работы считается теорема о передаче информации для канала с шумами, которая говорит о возможности свести вероятность ошибки передачи по каналу к минимуму при выборе достаточного большой длины ключевого слова — единицы информации передаваемой по каналу[1].

Упрощённая схема передачи информации по каналу с шумами.

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

Теорема Шеннона утверждает, что при определённых условиях вероятность ошибки декодирования (то есть невозможность декодером исправить ошибку передачи) можно уменьшить, выбрав большую длину ключевого слова. Однако, данная теорема (и работа вообще) не показывает, как можно выбрать большую длину, а точнее как эффективно организовать процесс кодирования и декодирования информации с большой длиной ключевых слов. Если предположить, что в кодере и декодере есть некие таблицы соответствия между входным блоком информации и соответствующим кодовым словом, то такие таблицы будут занимать очень много места. Для двоичного симметричного канала без памяти (если говорить упрощённо, то на вход кодера поступает поток из нулей и единиц) количество различных блоков составляет 2n, где n — количество бит (нулей или единиц) которые будут преобразовываться в одно кодовое слово. Для 8 бит это 256 блоков информации, каждый из которых будет содержать в себе соответствующее кодовое слово. Причём кодовое слово обычно большей длины, так как содержит в себе дополнительные биты для защиты от ошибок передачи данных. Поэтому одним из способов кодирования является использование проверочной матрицы, которые позволяют за одно математическое действие (умножение строки на матрицу) выполнить декодирование кодового слова. Аналогичным образом каждой проверочной матрице соответствует порождающая матрица, аналогичным способом одной операцией умножения строки на матрицу генерирующей кодовой слово.

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

Первой работой на эту тему стала работа Роберта Галлагера «Low-Density Parity-Check Codes» 1963 года[2] (основы которой были заложены в его докторской диссертации 1960 года). В работе учёный описал требования к таким кодам, описал возможные способы построения и способы их оценки. Поэтому часто LDPC-коды называют кодами Галлагера. В русской научной литературе коды также называют низкоплотностными кодами или кодами с малой плотностью проверок на чётность.

Однако, из-за сложности в реализации кодеров и декодеров эти коды не использовались[3]. Лишь много позже, с развитием телекоммуникационных технологий, снова возрос интерес к передаче информации с минимальными ошибками. Несмотря на сложность реализации по сравнению с турбо-кодом, отсутствие преград к использованию (незащищённость патентами) сделало LDPC-коды привлекательными для телекоммуникационной отрасли, и фактически стали стандартом де-факто. В 2003 году LDPC-код, вместо турбо-кода, стал частью стандарта DVB-S2 спутниковой передачи данных для цифрового телевидения. Аналогичная замена произошла и в стандарте DVB-T2 для цифрового наземного телевизионного вещания[4].

LDPC-коды описываются низкоплотностной проверочной матрицей, содержащей в основном нули и относительно малое количество единиц. По определению, если каждая строка матрицы содержит ровно k<n{\displaystyle k<n} и каждый столбец ровно j<r{\displaystyle j<r} единиц, то код называют регулярным (в противном случае — нерегулярным). В общем случае количество единиц в матрице имеет порядок O(n){\displaystyle O\left(n\right)}, то есть растёт линейно с увеличением длины кодового блока (количества столбцов проверочной матрицы).

Обычно рассматриваются матрицы больших размеров. Например, в работе Галлагера в разделе экспериментальных результатов используются «малые» количества строк n=124, 252, 504 и 1008 строк (число столбцов проверочной матрицы немного больше). На практике применяются матрицы с большим количеством элементов — от 10 до 100 тысяч строк. Однако количество единиц в строке или в столбце остаётся достаточно малым, обычно меньшим 10. Замечено, что коды с тем же количеством элементов на строку или столбец, но с большим размером, обладают лучшими характеристиками.

Проверочная матрица LDPC-кода (9, 2, 3) с минимальным циклом длины 8

Важной характеристикой матрицы LDPC-кода является отсутствие циклов определённого размера. Под циклом длины 4 понимают образование в проверочной матрице прямоугольника, в углах которого стоят единицы. Отсутствие цикла длины 4 можно также определить через скалярное произведение столбцов (или строк) матрицы. Если каждое попарное скалярное произведение всех столбцов (или строк) матрицы не более 1, это говорит об отсутствии цикла длины 4. Циклы большей длины (6, 8, 10 и т. д.) можно определить, если в проверочной матрице построить граф, вершинами которого являются единицы, а рёбра — все возможные соединения вершин, параллельные сторонам матрицы (то есть вертикальные или горизонтальные линии). Минимальный цикл в этом графе и будет минимальным циклом в проверочной матрице LDPC-кода. Очевидно, что цикл будет иметь длину как минимум 4, а не 3, так как рёбра графа должны быть параллельны сторонам матрицы. Вообще, любой цикл в этом графе будет иметь чётную длину, минимальный размер 4, а максимальный размер обычно не играет роли (хотя, очевидно, он не более, чем количество узлов в графе, то есть n×k).

Описание LDPC-кода возможно несколькими способами:

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

Способ задания кода проверочной матрицей является общепринятым для линейных кодов, когда каждая строка матрицы является элементом некоторого множества кодовых слов. Если все строки линейно-независимы, строки матрицы могут рассматриваться как базис множества всех кодовых векторов кода. Однако использование данного способа создаёт сложности для представления матрицы в памяти кодера — необходимо хранить все строки или столбцы матрицы в виде набора двоичных векторов, из-за чего размер матрицы становится равен j×k{\displaystyle j\times k} бит.

Представление LDPC-кода в виде двудольного графа

Распространённым графическим способом является представление кода в виде двудольного графа. Сопоставим все k{\displaystyle k} строк матрицы k{\displaystyle k} нижним вершинам графа, а n{\displaystyle n} столбцов — верхним, и соединим верхние и нижние вершины графа, если на пересечении соответствующих строк и столбцов стоят единицы.

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

Представление (9, 2, 3) LDPC-кода в виде графа специального вида. Матрица кода приведена выше.

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

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

В настоящее время используются два принципа построения проверочной матрицы кода. Первый основан на генерации начальной проверочной матрицы с помощью псевдослучайного генератора. Коды, полученные таким способом, называют случайными (англ. random-like codes). Второй — использование специальных методов, основанных, например, на группах и конечных полях. Коды, полученные этими способами называют структурированными. Лучшие результаты по исправлению ошибок показывают именно случайные коды, однако структурированные коды позволяют использовать методы оптимизации процедур хранения, кодирования и декодирования, а также получать коды с более предсказуемыми характеристиками.

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

В 2003 году Джеймсом МакГованом и Робертом Вильямсоном был предложен способ удаления циклов из матрицы LDPC-кода, в связи с чем стало возможным в начале сгенерировать матрицу с заданными характеристиками (n, j, k), а затем удалить из неё циклы. Так происходит в схеме Озарова-Вайнера[5].

В 2007 году в журнале «IEEE Transactions on Information Threory» была опубликована статья об использовании конечных полей для построения квази-цикличных LDPC-кодов для каналов с аддитивным белым Гауссовым шумом и двоичных каналов со стиранием.

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

G⊙HT=0{\displaystyle G\odot H^{T}=0}

где G{\displaystyle G} — порождающая матрица, и H{\displaystyle H} — проверочная. Тогда для каждого принятого без ошибок кодового слова выполняется отношение

s=v⊙HT=0{\displaystyle s=v\odot H^{T}=0},

а для принятого кодового слова с ошибкой:

s=v⊙HT≠0{\displaystyle s=v\odot H^{T}\neq 0},

где v{\displaystyle v} — принятый вектор, s{\displaystyle s} — синдром. В случае, если после умножения принятого кодового слова на транспонированную проверочную матрицу получается ноль, блок считается принятым без ошибок. В противном случае используются специальные методы для определения местоположения ошибки и её исправления. Для LDPC-кода стандартные способы исправления оказываются слишком трудоёмкими — их относят к классу NP-полных задач, что, учитывая большую длину блока, не может применяться на практике. Вместо них применяют метод вероятностного итеративного декодирования, исправляющую большую долю ошибок за границей половины кодового расстояния[6].

Рассмотрим[7] симметричный канал без памяти со входом ±a{\displaystyle \pm a} и аддитивным гауссовым шумом σ2=1{\displaystyle \sigma ^{2}=1}. Для принятого кодового слова y{\displaystyle y} нужно найти соответствующий наиболее вероятный вектор x{\displaystyle x}, такой что

H⊙x=0mod2{\displaystyle H\odot x=0\mod 2}.
  1. Определим
    fn1=1/(1+exp⁡(−2ayn/σ2)){\displaystyle f_{n}^{1}={1/{\mathord {\left(1+\exp \left(-2ay_{n}/{\mathord {\sigma ^{2}}}\right)\right)}}}};
    fn0=1−fn1{\displaystyle f_{n}^{0}=1-f_{n}^{1}};
    где yn{\displaystyle y_{n}} — принятое значение n-го символа кодового слова (которое для данного канала имеет произвольное значение, обычно в рамках ±(a+3σ){\displaystyle \pm (a+3\sigma )}).
  2. Будем использовать слово «бит» для обозначения отдельных элементов вектора x{\displaystyle x}, и слово «проверка» для обозначения строк проверочной матрицы H{\displaystyle H}. Обозначим через N(m)≡{n:Hnm=1}{\displaystyle N\left(m\right)\equiv \{n:H_{nm}=1\}} набор битов, которые будут участвовать в m-ой проверке. Аналогично, обозначим M(n)≡{m:Hnm=1}{\displaystyle M\left(n\right)\equiv \{m:H_{nm}=1\}} набор проверок, в которых участвует бит n. (То есть перечислим индексы ненулевых элементов для каждой строки и для каждого столбца проверочной матрицы H{\displaystyle H}).
  3. Инициализируем матрицы qmn0{\displaystyle q_{mn}^{0}} и qmn1{\displaystyle q_{mn}^{1}} значениями fn0{\displaystyle f_{n}^{0}} и fn1{\displaystyle f_{n}^{1}} соответственно
  4. (Горизонтальный шаг)
    δqmn=qmn0−qmn1{\displaystyle \delta q_{mn}=q_{mn}^{0}-q_{mn}^{1}}
    δrmn=∏n′∈N(m)∖nδqmn′{\displaystyle \delta r_{mn}=\prod \limits _{n'\in N(m)\backslash n}{\delta q_{mn'}}}
    rmn0=12(1+δrmn){\displaystyle r_{mn}^{0}={1 \over 2}\left({1+\delta r_{mn}}\right)}
    rmn1=12(1−δrmn){\displaystyle r_{mn}^{1}={1 \over 2}\left({1-\delta r_{mn}}\right)}
  5. (Вертикальный шаг)
    qmn0=αmnfn0∏m′∈M(n)∖mrm′n0{\displaystyle q_{mn}^{0}=\alpha _{mn}f_{n}^{0}\prod \limits _{m'\in M\left(n\right)\backslash m}{r_{m'n}^{0}}}
    qmn1=αmnfn1∏m′∈M(n)∖mrm′n1{\displaystyle q_{mn}^{1}=\alpha _{mn}f_{n}^{1}\prod \limits _{m'\in M\left(n\right)\backslash m}{r_{m'n}^{1}}}
    где для каждого m{\displaystyle m} и n{\displaystyle n} выбранное αmn{\displaystyle \alpha _{mn}} даёт:
    qmn0+qmn1=1{\displaystyle q_{mn}^{0}+q_{mn}^{1}=1}
    Теперь также обновляем «псевдопостериорные вероятности» того, что биты вектора x{\displaystyle x} принимают значения 0 или 1:
    qn0=αnfn0∏m∈M(n)rmn0{\displaystyle q_{n}^{0}=\alpha _{n}f_{n}^{0}\prod \limits _{m\in M\left(n\right)}{r_{mn}^{0}}}
    qn1=αnfn1∏m∈M(n)rmn1{\displaystyle q_{n}^{1}=\alpha _{n}f_{n}^{1}\prod \limits _{m\in M\left(n\right)}{r_{mn}^{1}}}
    Также, как и ранее, αn{\displaystyle \alpha _{n}} выбирается таким образом, что
    qn0+qn1=1{\displaystyle q_{n}^{0}+q_{n}^{1}=1}

Данные значения используются воссоздания вектора x. Если полученный вектор удовлетворяет H⊙x=0mod2{\displaystyle H\odot x=0\mod 2}, то алгоритм на этом прерывается, иначе повторяются горизонтальный и вертикальные шаги. Если же алгоритм продолжается до некоторого шага (например, 100), то он прерывается и блок объявляется принятым с ошибкой.

Известно, что данный алгоритм даёт точное значение вектора x{\displaystyle x} (то есть, совпадающее с классическими способами), если проверочная матрица H{\displaystyle H} не содержит циклов[8].

  1. Shannon C.E. A Mathematical Theory of Communication // Bell System Technical Journal. — 1948. — Т. 27. — С. 379-423, 623–656.
  2. Gallager, R. G. Low Density Parity Check Codes. — Cambridge: M.I.T. Press, 1963. — P. 90.
  3. David J.C. MacKay. Information theory, inference and learning algorithms. — CUP, 2003. — ISBN 0-521-64298-1.
  4. Dr. Lin-Nan Lee. LDPC Codes, Application to Next Generation Communication Systems // IEEE Semiannual Vehicular Technology Conference. — October, 2003. Архивировано 8 октября 2006 года.
  5. Ю.В. Косолапов. О применении схемы озарова-вайнера для защиты информации в беспроводных многоканальных системах передачи данных // Информационное противодействие угрозам терроризма : Научно-практический журнал. — 2007. — № 10. — С. 111-120. Архивировано 24 июня 2013 года.
  6. ↑ В. Б. Афанасьев, Д. К. Зигангиров «О некоторых конструкциях низкоплотностных кодов с компонентным кодом Рида-Соломона»
  7. ↑ David J.C. MacKay, Radford M. Neal Near Shannon Limit Performance of Low Density Parity Check Codes
  8. ↑ J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, 1988.

ru.wikipedia.org

Помехоустойчивое кодирование с иcпользованием различных кодов / Habr

Это продолженеие статьи о помехоустойчивом кодировании, которая очень долго лежала в черновиках. В прошлой части нет ничего интересного с практической точки зрения — лишь общие сведения о том, зачем это нужно, где применяется и т.п. В данной части будут рассматриваться некоторые (самые простые) коды для обнаружения и/или исправления ошибок. Итак, поехали.

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

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

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

k/(i+k), где
k — количество проверочных бит,
i — количество информационных бит.
Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит — избыточность составит 1/(3+1) = 1/4 (25%).
Код с проверкой на четность

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

В каждом пакет данных есть один бит четности, или, так называемый, паритетный бит. Этот бит устанавливается во время записи (или отправки) данных, и затем рассчитывается и сравнивается во время чтения (получения) данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно . Изменение этого бита (например с 0 на 1) сообщает о возникшей ошибке.
Ниже показана структурная схемы кодера для данного кода


и и декодера

Пример:

Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10110 (изменился второй бит)
Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка.

Как говорилось ранее, этот метод служит только для определения одиночной ошибки. В случае изменения состояния двух битов, возможна ситуация, когда вычисление контрольного бита совпадет с записанным. В этом случае система не определит ошибку, а это не есть хорошо. К примеру:
Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10010 (изменились 2 и 3 биты)
В принятых данных число единиц четно, и, следовательно, декодер не обнаружит ошибку.

Так как около 90% всех нерегулярных ошибок происходит именно с одиночным разрядом, проверки четности бывает достаточно для большинства ситуаций.
Код Хэмминга

Как говорилось в предыдущей части, очень много для помехоустойчивого кодирования сделал Ричард Хэмминг. В частности, он разработал код, который обеспечивает обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительных проверочных бит. Для каждого числа проверочных символов используется специальная маркировка вида (k, i), где k — количество символов в сообщении, i — количество информационных символов в сообщении. Например, существуют коды (7, 4), (15, 11), (31, 26). Каждый проверочный символ в коде Хэмминга представляет сумму по модулю 2 некоторой подпоследовательности данных. Рассмотрим сразу на примере, когда количество информационных бит i в блоке равно 4 — это код (7,4), количество проверочных символов равно 3. Классически, эти символы располагаются на позициях, равных степеням двойки в порядке возрастания:
первый проверочный бит на 20 = 1;
второй проверочный бит на 21 = 2;
третий проверочный бит на 22 = 4;

но можно и разместить их в конце передаваемого блока данных (но тогда формула для их расчета будет другая).
Теперь рассчитаем эти проверочные символы:
r1 = i1 + i2 + i4
r2 = i1 + i3 + i4
r3 = i2 + i3 + i4

Итак, в закодированном сообщении у нас получится следующее:
r1 r2 i1 r3 i2 i3 i4

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

и декодера

(может быть, довольно запутано, но лучше начертить не получилось)

e0,e1,e2 опрделяются как функции, зависящие от принятых декодером бит k1 — k7:

e0 = k1 + k3 + k5 + k7 mod 2
e1 = k2 + k3 + k6 + k7 mod 2
e2 = k4 + k5 + k6 + k7 mod 2

Набор этих значений e2e1e0 есть двоичная запись позиции, где произошла ошибка при передаче данных. Декодер эти значения вычисляет, и если они все не равны 0 (то есть не получится 000), то исправляет ошибку.
Коды-произведения

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

Передаваемая информация кодируется дважды: во внешнем и внутреннем кодерах. Между ними устанавливается буфер, работа которого показана на рисунке:

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

При выводе строк из буфера к ним добавляются проверочные символы внутреннего кода. В таком порядке информация передается по каналу связи или записывается куда-нибудь. Условимся, что и внутренний, и внешний коды – коды Хэмминга, с тремя проверочными символами, то есть и тот, и другой могут исправить по одной ошибке в кодовом слове (количество «кубиков» на рисунке не критично — это просто схема). На приемном конце расположен точно такой же массив памяти (буфер), в который информация заносится построчно, а выводится по столбцам. При возникновении пакетной ошибки (крестики на рисунке в третьей и четвертой строках), она малыми порциями распределяется в кодовых словах внешнего кода и может быть исправлена.

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

Использование кодов-произведений многократно увеличивает мощность помехоустойчивого кода при добавлении незначительной избыточности.

P.S.: Плотно занимался этой темой 3 года назад, когда писал дипломный проект, возможно что-то упустил. Все исправления, замечания, пожелания — пожалуйста через личные сообщения

habr.com

Арифметическое кодирование / Habr

Сейчас существует множество алгоритмов сжатия информации. Большинство из них широко известны, но есть и некоторые весьма эффективные, но, тем не менее, малоизвестные алгоритмы. Эта статья рассказывает о методе арифметического кодирования, который является лучшим из энтропийных, но тем не менее мало кто о нём знает.
Прежде чем рассказывать об арифметическом кодировании, надо сказать пару слов об алгоритме Хаффмана. Этот метод эффективен, когда частоты появления символов пропорциональны 1/2n (где n – натуральное положительное число). Это утверждение становится очевидным, если вспомнить, что коды Хаффмана для каждого символа всегда состоят из целого числа бит. Рассмотрим ситуацию, когда частота появление символа равна 0,2, тогда оптимальный код для кодирования это символа должен иметь длину –log2(0,2)=2,3 бита. Понятно, что префиксный код Хаффмана не может иметь такую длину, т.е. в конечном итоге это приводит к ухудшению сжатия данных.
Арифметическое кодирование предназначено для того, чтобы решить эту проблему. Основная идея заключается в том, чтобы присваивать коды не отдельным символам, а их последовательностям.
Вначале рассмотрим идею, лежащую в основе алгоритма, затем рассмотрим небольшой практический пример.
Как и во всех энтропийных алгоритмах мы обладаем информацией о частоте использования каждого символа алфавита. Эта информация является исходной для рассматриваемого метода. Теперь введём понятие рабочего отрезка. Рабочим называется полуинтервал [a;b) с расположенными на нём точками. Причём точки расположены т.о., что длины образованных ими отрезков равны частоте использования символов. При инициализации алгоритма a=0 b=1.
Один шаг кодирования заключается в простой операции: берётся кодируемый символ, для него ищется соответствующий участок на рабочем отрезке. Найденный участок становится новым рабочим отрезком (т.е. его тоже необходимо разбить с помощью точек).
Эта операция выполняется для некоторого количества символов исходного потока. Результатом кодирования цепочки символов является любое число (а также длина его битовой записи) с итогового рабочего отрезка (чаще всего берётся левая граница отрезка).
Звучит это довольно сложно. Давайте попробуем разобраться с помощью небольшого примера. Закодируем сообщение «ЭТОТ_МЕТОД_ЛУЧШЕ_ХАФФМАНА» с помощью описанного метода.

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

Берём первый символ из потока, это символ «Э». Соответствующий ему отрезок – отрезок [0,96;1). Если бы мы хотели закодировать один символ, то результатом кодирования было бы любое число из этого отрезка. Но мы не остановимся на одном символе, а добавим ещё один. Символ «Т». Для этого составим новый рабочий отрезок с a=0,96 и b=1. Разбиваем этот отрезок точками точно так же как мы сделали это для исходного отрезка и считываем новый символ «Т». Символу «Т» соответствует диапазон [0,24;0,36), но наш рабочий отрезок уже сократился до отрезка [0,96;1). Т.е. границы нам необходимо пересчитать. Сделать это можно с помощью двух следующих формул: High=Lowold+(Highold-Lowold)*RangeHigh(x), Low=Lowold+(Highold-Lowold)*RangeLow(x), где Lowold – нижняя граница интервала, Highold – верхняя граница интервала RangeHigh и RangeLow – верхняя и нижняя границы кодируемого символа.
Пользуясь этими формулами, закодируем первое слово сообщения целиком:

Результатом кодирования будет любое число из полуинтервала [0,97218816; 0,97223424).
Предположим, что результатом кодирования была выбрана левая граница полуинтервала, т.е. число 0,97218816.
Рассмотрим процесс декодирования. Код лежит в полуинтервале [0,96;1). Т.е. первый символ сообщения «Э». Чтобы декодировать второй символ (который кодировался в полуинтервале [0,96;1)) полуинтервал нужно нормализовать, т.е. привести к виду [0;1). Это делается с помощью следующей формулы: code=(code-RangeLow(x))/(RangeHigh(x)-RangeLow(x)), где code – текущее значение кода.
Применяя эту формулу, получаем новое значение code=(0,97218816-0,96)/(1-0,96)= 0,304704. Т.е. второй символ последовательности «Т».
Снова применим формулу: code=(0,304704-0,24)/(0,36-0,24)= 0,5392. Третий символ последовательности – «О».
Продолжая декодирование, по описанной схеме мы можем полностью восстановить исходный текст.

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

habr.com

Цифровые телефонные системы для чайников. Часть 1 — Кодирование голоса / Habr


Давным-давно, когда небо было голубым, а трава зеленой АТС были аналоговыми, работали они очень просто: нужно связать двух абонентов — нет проблем, взяли замкнули линию первого на линию второго, и все дела. Вариант, конечно, очень упрощенный, но в общих чертах так все и было. Примечательно в данном случае то, что между абонентами постоянно поддерживалась линия связи. Даже если они оба молчали, были заняты не только те линии, что ведут от абонентов к их АТС, но и линии между самими АТС.

Позднее, когда цифровые технологии стали развиваться все больше и больше, встал вопрос, а почему бы не использовать их для передачи телефонных разговоров? Внедрение цифровых АТС имело довольно много положительных моментов: аппаратура стала занимать меньше места, обслуживать цифровые АТС и проводить диагностику стало легче, значительно увеличилась гибкость настройки, масштабируемость, надежность. Но одни из главных новшеств — временное разделение каналов, а затем и пакетная передача данных. Преимуществом временного разделения каналов в том, что, грубо говоря, по одной линии между АТС в различные моменты времени (канальные интервалы) могут предаваться разговоры нескольких пар абонентов, таким образом, увеличивается количество соединении при неизменном количестве физических линий. При пакетной передаче для связи двух абонентов уже нет нужды в постоянном занятии линии между АТС, данные (разговор) передаются в пакетах и только тогда, когда они есть, в другое время канал можно использовать для передачи данных других абонентов. Также при использовании пакетной передачи облегчается возможность передачи и других данных по тем же сетям (например, интернет-трафика).

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

Итак, вопрос номер раз:

Как в цифровых системах передается разговор?

Тут на помощь пришла импульсно-кодовая модуляция (ИКМ, PCM, pulse-code modulation), известная, как утверждает Википедия, с начала XX века. Почитать о ней можно, например, все в той же Википедии.

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

Дискретизация — это получение мгновенных значений сигнала (отсчетов) через определенные промежутки времени (т.е. с определенной частотой — частотой дискретизации). На рисунке: (1) — сигнал, (2) — отсчеты.

Квантование — это «округление» полученных мгновенных значений до ближайших заранее заданных уровней. Например, если у нас есть 5 уровней с шагом 2: 0, 2, 4, 6, 8, а некоторые мгновенные значения равны 3.6, 7.1, 2, 0.5, 1.8, то они будут округлены до 4, 8, 2, 0, 2 соответственно.

Кодирование — это представление значений полученных уровней в виде какого-либо кода (например, двоичного).

Теперь рассмотрим, как вышеописанное происходит в цифровой телефонии.

Человеческая речь занимает полосу частот приблизительно 60-12000 Гц, однако для нормальной разборчивости достаточно полосы частот в 300-3400 Гц, т.е. верхняя граница составляет 3.4 кГц. Все, что выше 3.4 кГц «срезается» фильтром, для того чтобы избежать помех в будущем. Согласно теореме Котельникова, частота дискретизации для представления аналогового сигнала, ограниченного по спектру (помним о фильтре), в виде отсчетов должна превышать удвоенную верхнюю частоту сигнала. Для простоты расчетов, а также некоторого запаса, верхняя граница округляется до 4 кГц. Таким образом, частота дискретизации в нашем случае равна 8 кГц.

Квантование и кодирование практически всегда являются неотъемлемыми частями друг друга. Квантование в цифровой телефонии неравномерное, 256-уровневое. Неравномерность квантования выражается в том, что шаг квантования (расстояние между соседними уровнями в единицах измерения характеристики аналогового сигнала, которая квантуется; в данном случае — напряжение сигнала в вольтах) для малых амплитуд выбирается минимальным, для средних — бóльшим и для больших — самым большим. Это сделано для того, чтобы повысить точность передачи сигналов с низкой амплитудой. 256 уровней квантования можно «уместить» в одно 8-разрядное двоичное число, таким образом, один отсчет представляется в виде 8-разрядной кодовой комбинации. Все 256 уровней делятся на две группы: положительные и отрицательные. Для положительных сигналов первый бит в кодовой комбинации равен «1», для отрицательных — «0». Каждая группа делится на 8 сегментов. В пределах одного сегмента шаг квантования неизменный, в то время, как от сегмента к сегменту он меняется, увеличиваясь с возрастанием номера сегмента. Под номер сегмента отводятся следующие 3 бита. Последние 4 бита занимает номер уровня в сегменте, всего этих уровней 16. Итого имеем: 16 уровней × 8 сегментов × 2 группы = 256 уровней.

К примеру, число «10010101» представляет собой положительный сигнал (1), с уровнем 5 (0101) в 1-м сегменте (001).

Теперь можно посчитать скорость полученного цифрового сигнала:

B = 8000 отсчетов/сек × 8 бит/отсчет = 64000 бит/с = 64 кбит/с.

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

Спасибо за внимание.

P.S. Стоит ли писать продолжение?

habr.com

Арифметическое кодирование — Википедия

Арифметическое кодирование — один из алгоритмов энтропийного сжатия.

В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов.

Как правило, превосходит алгоритм Хаффмана по эффективности сжатия, позволяет сжимать данные с энтропией, меньшей 1 бита на кодируемый символ, но некоторые версии имеют патентные ограничения от компании IBM.[1]

Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти H{\displaystyle H} бит, где H{\displaystyle H} — информационная энтропия источника.

В отличие от алгоритма Хаффмана, метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например, для строки бит 010101…0101 длины s метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше.[2]

Пусть имеется некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.

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

Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.

Пример работы метода арифметического кодирования[править | править код]

Вероятностная модель[править | править код]

Используя метод арифметического кодирования, можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно теории энтропийного кодирования источника Шеннона оптимальное представление будет стремиться к числу −log2P бит на каждый символ, вероятность которого P). Алгоритмы сжатия данных, использующие в своей работе метод арифметического кодирования, перед непосредственным кодированием формируют модель входных данных на основании количественных или статистических характеристик, а также, найденных в кодируемой последовательности повторений или паттернов — любой дополнительной информации, позволяющей уточнить вероятность появления символа P в процессе кодирования. Очевидно, что чем точнее определена или предсказана вероятность символа, тем выше эффективность сжатия.

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

  • 60 % вероятность нейтрального значения сигнала или NEUTRAL.
  • 20 % вероятность положительного значения сигнала или POSITIVE.
  • 10 % вероятность отрицательного значения сигнала или NEGATIVE.
  • 10 % вероятность признака конца кодируемой последовательности или END-OF-DATA.

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

Следует также отметить, что в качестве алфавита вероятностной модели метода можно рассматривать любой набор символов, исходя из особенностей решаемой задачи. Более эвристические подходы, использующие основную схему метода арифметического кодирования, применяют динамические или адаптивные модели. Идея данных методов заключается в уточнении вероятности кодируемого символа за счёт учёта вероятности предшествующего или будущего контекста (то есть, вероятность появления кодируемого символа после определённого k-го числа символов слева или справа, где k — это порядок контекста).

Кодирование сообщения[править | править код]

Возьмём для примера следующую последовательность:

NEUTRAL POSITIVE NEGATIVE END-OF-DATA

Сначала разобьём отрезок от 0 до 1 согласно частотам сигналов. Разбивать отрезок будем в порядке, указанном выше: NEUTRAL — от 0 до 0,6; POSITIVE — от 0,6 до 0,8; NEGATIVE — от 0,8 до 0,9; END-OF-DATA — от 0,9 до 1.

Теперь начнём кодировать с первого символа. Первому символу — NEUTRAL соответствует отрезок от 0 до 0,6. Разобьём этот отрезок аналогично отрезку от 0 до 1.

Закодируем второй символ — NEGATIVE. На отрезке от 0 до 0,6 ему соответствует отрезок от 0,48 до 0,54. Разобьём этот отрезок аналогично отрезку от 0 до 1.

Закодируем третий символ — END-OF-DATA. На отрезке от 0,48 до 0,54 ему соответствует отрезок от 0,534 до 0,54.

Так как это был последний символ, то кодирование завершено. Закодированное сообщение — отрезок от 0,534 до 0,54 или любое число из него, например, 0,538.

Декодирование сообщения[править | править код]

На диаграмме представлено декодирование итогового интервального значения 0,538 согласно модели в приведённом примере. Область интервала разбивается на подинтервальные области согласно вероятностным характеристикам появления соответствующих символов. Затем, очередной выбранный интервал разбивается аналогичным способом.

Предположим, что нам необходимо раскодировать сообщение методом арифметического кодирования согласно описанной выше модели. Сообщение в закодированном виде представлено дробным значением 0,538 (для простоты используется десятичное представление дроби, вместо двоичного основания). Предполагается, что закодированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного восстановления первоначальных данных.

Начальное состояние процесса декодирования совпадает с процессом кодирования и рассматривается интервал [0,1). На основании известной вероятностной модели дробное значение 0,538 попадает в интервал [0, 0,6). Это позволяет определить первый символ, который был выбран кодировщиком, поэтому его значение выводится как первый символ декодированного сообщения.

ru.wikipedia.org

4. Эффективное (статистическое) кодирование. Основы передачи дискретных сообщений

Эффективное кодирование – это процедуры направленные на устранение избыточности.

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

Пусть имеется источник дискретных сообщений, алфавит которого .

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

Если вероятности появления всех сообщений источника равны, то энтропия источника (или среднее количество информации в одном сообщении) максимальна и равна .

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

Если при том же объеме алфавита сообщения не равновероятны, то, как известно, энтропия источника будет меньше

.

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

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

.

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

.

Пример

Для кодирования 32 букв русского алфавита, при условии равновероятности, нужна 5 разрядная кодовая комбинация. При учете ВСЕХ статистических связей реальная энтропия составляет около 1,5 бит на букву. Нетрудно показать, что избыточность в данном случае составит

,

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

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

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

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

, можно перефразировать данное высказывание.

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

Т.о. на одно сообщение будет затрачено в среднем меньшее единичных элементов , чем при равномерном.

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

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

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

Ответ на этот вопрос дал Шеннон.

Шеннон показал, что

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

2. Существует способ кодирования, при котором средняя длина кодового слова немногим отличается от энтропии источника

Остается выбрать подходящий способ кодирования.

Эффективность применения оптимальных неравномерных кодов может быть оценена:

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

- позволяет сравнить эффективность применения различных методов эффективного кодирования.

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

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

Веедем понятие кодового дерева для множества кодовых слов.

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

Рисунок 1. Пример двоичного кодового дерева

Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между “0” и “1” в качестве первого символа кодового слова: левая ветвь соответствует “0”, а правая – “1”. Две ветви, идущие из узлов первого порядка, соответствуют второму символу кодовых слов, левая означает “0”, а правая – “1” и т. д. Ясно, что последовательность символов каждого кодового слова определяет необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.

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

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

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

Метод Хаффмена

Одним из часто используемых методов эффективного кодирования является так называемый код Хаффмена.

Пусть сообщения входного алфавита имеют соответственно вероятности их появления .

Тогда алгоритм кодирования Хаффмена состоит в следующем:

1. Сообщения располагаются в столбец в порядке убывания вероятности их появления.

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

3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.

4. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно определить, приписывая правым ветвям объединения символ “1”, а левым - “0”. Впрочем, понятия “правые” и “левые” ветви в данном случае относительны.

На основании полученной таблицы можно построить кодовое дерево

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

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

Пример на однозначность декодирования и трек ошибок

Пусть передавалась следующая последовательность

1 0 0 1 1 1 0 0 0 1

a b c d

При возникновении ошибки в первом двоичном элементе, получим

0 0 0 1 1 1 0 0 0 1

g c d

Т.О. ошибка в одном разряде комбинации первого символа привела к неправильному декодированию двух символов. (Трек ошибок).

Контрольные вопросы по теме:

  1. Назначение и цели эффективного кодирования.
  2. Поясните за счет чего, обеспечивается достижение сжатия при эффективном кодировании.
  3. Чем определяется минимальная средняя длина кодовой комбинация при применении эффективном кодировании.
  4. Какие проблемы возникают при разделении неравномерных кодовых комбинаций.
  5. Что такое префиксные коды.
  6. В чем заключается алгоритм Хаффмана.
  7. Что такое трек ошибок, и каковы причины его возникновения.

siblec.ru

Сетевое кодирование — Википедия

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

Сеть «Бабочка»

Для объяснения принципов сетевого кодирования используют пример сети «бабочка», предложенной в первой работе по сетевому кодированию «Network information flow»[1]. Рассмотрим сеть, показанную на рисунке, в которой есть один или два источника, генерирующего пакеты A и B, поступающих на вход сети «бабочка». Первые узлы, отвечающие за передачу информации, передают по одному пакету (A слева и B справа) на вход конечным узлам получателям. Также они передают эти пакеты промежуточному узлу, который, вместо передачи двух пакетов по очереди (и потере времени) комбинирует эти пакеты, например, с помощью операции XOR и передаёт далее.

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

В отличие от статического сетевого кодирования, когда получателю известны все манипуляции, производимые с пакетом, также рассматривается вопрос о случайном сетевом кодировании, когда данная информация неизвестна. Авторство первых работ по данной тематике принадлежит Кёттеру, Кшишангу и Силве[2]. Также данный подход называют сетевым кодированием со случайными коэффициентами — когда коэффициенты, под которыми начальные пакеты, передаваемые источником, войдут в результирующие пакеты, принимаемые получателем, с неизвестными коэффициентами, которые могут зависеть от текущей структуры сети и даже от случайных решений, принимаемых на промежуточных узлах.

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

Пакет Битовое поле
A{\displaystyle A} 1 0
B{\displaystyle B} 0 1
A⊕B{\displaystyle A\oplus B} 1 1

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

Для неслучайного сетевого кодирования можно использовать стандартные способы защиты от помех и искажений, используемых для простой передачи информации по сети. Однако, как отмечено в статье «LDPC coding schemes for error»[3], пакеты, восстанавливаемые из линейных комбинаций, имеют большую вероятность быть принятыми с ошибкой, так как на них влияют как вероятность ошибки сразу в двух пакетах, используемых для восстановления информации.

Рассматривая сеть «бабочка», можно показать, что для первого получателя вероятность принять пакет A{\displaystyle A} без ошибок больше, чем для пакета B{\displaystyle B}, даже если предположить одинаковые, но отличные от нуля вероятности ошибок в принятых получателем пакетах A{\displaystyle A} и A⊕B{\displaystyle A\oplus B}.

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

Методы, используемые для декодирования в случайном сетевом кодировании, рассматривают все принятые пакеты как единый объект (часто — матрицу), построенной из принятых пакетов-строк. Если первая часть пакета представляет собой битовое поле, то операции с матрицей сводятся, во-первых, к приведению левой её части к диагональному виду (с помощью метода Гаусса), а затем к исправлению ошибок в правой части матрицы. Для исправления ошибок можно использовать ранговые коды, которые могут исправить не только ошибки в столбцах матрицы (из-за неправильно принятых битов данных), но и ошибки в строках матрицы (из-за ошибок передачи в битовом поле).

  1. ↑ Ahlswede, R.; Ning Cai; Li, S.-Y.R.; Yeung, R.W., «Network information flow», Information Theory, IEEE Transactions on, vol.46, no.4, pp.1204-1216, Jul 2000
  2. ↑ Статьи
    • Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding// IEEE International Symposium on Information Theory. Proc.ISIT-07.-2007.- P. 791—795.
    • Silva D., Kschischang F.R. Using rank-metric codes for error correction in random network coding // IEEE International Symposium on Information Theory. Proc. ISIT-07. — 2007.
    • Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding // IEEE Transactions on Information Theory. — 2008- V. IT-54, N.8. — P. 3579-3591.
    • Silva D., Kschischang F.R., Koetter R. A Rank-Metric Approach to Error Control in Random Network Coding // IEEE Transactions on Information Theory.- 2008- V. IT-54, N. 9.- P.3951-3967.
  3. ↑ Kang J., Zhou B., Ding Z., Lin S. LDPC coding schemes for error control in a multicast network

ru.wikipedia.org


Смотрите также