Коды переменной длины

КОДИРОВАНИЕ И СЖАТИЕ ИНФОРМАЦИ

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

Коды переменной длины

Первое правило построения кодов переменной длины, состоит в том, что короткие коды следует присваивать часто встречающимся символам, а длинные – редко встречающимся. При этом коды следует назначать так, чтобы из можно было декодировать однозначно, а не двусмысленно. Например, рассмотрим четыре символа a 1 , a 2 , a 3 , a 4 . Если они появляются в сообщении с равной вероятностью (p = 0,25), то присвоим им четыре двухбитовых кода: 00, 01, 10, 11. Все вероятности равны, поэтому коды переменной длины не сожмут данные. Для каждого символа с коротким кодом найдётся символ с длинным кодом и среднее число битов на символ будет не меньше 2. Избыточность данных равновероятными символами равна 0, и строку таких символов невозможно сжать с помощью кодов переменной длины (или какого-либо другого метода).

Пусть теперь эти четыре символа появляются с разными вероятностями (см. табл. 12.1). В этом случае имеется избыточность, которую можно удалить с помощью кодов переменной длины и сжать данные так, чтобы потребуется меньше 2 бит на символ. Наименьшее среднее число бит на символ равно 1,57, то есть энтропии этого множества символов.

В таблице 12.1 предложен код Код_ 1, который присваивает самому часто встречающемуся символу самый короткий код. Среднее число бит на символ равно 1,77. Это число близко к теоретическому минимуму.

Таблица 12.1

Рассмотрим последовательность из 20 символов

a 1 a 3 a 2 a 1 a 3 a 3 a 4 a 2 a 1 a 1 a 2 a 2 a 1 a 1 a 3 a 1 a 1 a 3 a 1 ,

в которой четыре символа появляются, примерно, с одинаковыми частотами. Этой строке будет соответствовать кодовое слово длины 37 бит:

1|010|01|1|010|010|001|01|1|1|01|01|1|1|010|1|1|01|010|1.

Среднее число бит на символ составляет 1,85, что не слишком далеко от вычисленной минимальной средней длины. Однако если попытаться декодировать последовательность, то окажется, что Код _1 имеет существенный недостаток. Первый бит кодового слова равен 1, поэтому первым символом последовательности может быть только a 1 , так как код никакого другого символа не начинается с 1. Следующий символ равен 0, но коды для символов a 2 , a 3 , a 4 все начинаются с 0, поэтому декодер должен считать следующий символ. Он равен 1, но коды для a 2 и a 3 оба имеют в начале 01. Поэтому декодер не знает, как действовать дальше: декодировать строку как 1|010|01…, то есть a 1 a 3 a 2 …, или как 1|01|001…, то есть a 1 a 2 a 4 .... Дальнейшие биты последовательности не могут исправить положения. Поэтому Код­ _1 является двусмысленным. От этого недостатка свободен Код _2.

Код _2 обладает так называемым префиксным свойством, которое можно сформулировать так: если некоторая последовательность битов выбрана в качестве кода какого-либо символа, то ни один код какого-либо другого символа не должен иметь в начале эту последовательность (код символа не может быть префиксом кода другого символа). Если строка 01 является кодом для a 2 , то другие коды не должны начинаться с 01. Поэтому коды для a 3 и a 4 должны начинаться с 00. Естественно для этого выбрать 000 и 001.

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

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

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

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

Блок А

Постоянные затраты

Переменные затраты

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

Также, в соответствии с критерием оптимальности структуры выпуска по Парето выпуск будет эффективным, если он будет одновременно максимизировать полезность покупателей и не будет выходить за пределы имеющихся ресурсов (т.е. будет лежать на кривой производственных возможностей). Структура выпуска эффективна, если произ-ли и потреб-ли одновременно находятся в состоянии равновесия.

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

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

МД = Выручка от продаж – переменные затраты

МД= Постоянные затраты + Прибыль от продаж

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

Бухгалтерская прибыль = Совокупный доход предприятия- Бухгалтерские (Явные) издержки

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

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

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

Блок Б

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

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

Варианты расчета себестоимости взаимооказываемых работ соответствующих трансфертных цен.

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

Где R ni – сумма первичных затрат мест; q i – объем услуг, предоставленных подразделению; n – место затрат i -му подразделению (i = 1, ... n ); k i , k j – коэффициенты распределения затрат j -го места издержек.

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

Где К – коэффициент распределения; R пм – затраты первичных мест; Q пм – объем услуг, потребленных в сумме всеми подразделениями основного производства предприятия.

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

Где R fix , R var – постоянные и переменные расходы, распределенные предыдущим центром затрат; Q пм – объем первичных услуг, переданных следующему подразделению предприятия.

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

Блок С

1. От чего зависит и как измеряется загрузка производственных мощностей предприятия?

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

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

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

2. Какие расходы зависят от степени загрузки производственных мощностей предприятия ?

Производственные мощности или возможности предприятия - не однородная, а гомогенная величина, состоящая из производственных мощностей отдельных подразделений (цехов, участков) предприятия. В силу разных, в том числе объективных, причин эти мощности не полностью сопряжены друг с другом, например, из-за разной производительности станков, машин и другого оборудования. Отсюда ясно, что затраты материальных и трудовых ресурсов должны учитываться исходя из определенного уровня использования производственных мощностей, как правило, меньшего, чем 100%. Недоиспользованные мощности означают неиспользованные возможности увеличения производства и снижения себестоимости продукции. Отсюда следует, что уровень загрузки ПМ влияет на размер переменных затрат.

3. Что представляет собой размер общей суммы расходов предприятия?

Размер общей суммы расходов предприятия – валовые издержки предприятия (?), представляющие собой совокупность постоянных, не изменяющихся, издержек и переменных издержек, зависящих от объема производимой и реализуемой продукции.

Плюсы

Система калькуляции по нормативным затратам позволяет существенно сократить объем учетной работы;

Обеспечивает твердую основу для выявления существенных отклонений при сопоставлении затрат;

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

Нормативные затраты служат лучшим критерием для оценки фактических затрат;

Обеспечивает пользователей информацией об ожидаемых затратах на производство и продажу продукции;

Позволяет установить цены на основе заранее определенной себестоимости единицы продукции;

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

Минусы

Много внимания фокусируется на стоимости и производительности труда;

Не обеспечивает предприятие достаточной информацией для поиска путей усовершенствования его деятельности;

Охватывает далеко не все аспекты повышения эффективности производства;

Применяется для периодически повторяемых затрат;

Успешность применения зависит от состава и качества нормативной базы;

Невозможность установить нормы по отдельным видам затрат.

Блок Д

Блок А

В чем различие между постоянными и переменными расходами предприятия?

Критерием разделения затрат на постоянные и переменные является их зависимость от объема производства.

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

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

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

Переменные затраты возрастают или уменьшаются в абсолютной сумме в зависимости от изменения объема производства и делятся на пропорциональную и непропорциональную части.

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

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

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

Условно переменные разделим на входные (то, что дано), выходные (результат: то, что нужно получить) и промежуточные, необходимые в процессе вычислений. Например, для программы вычисления наибольшего общего делителя (алгоритм Евклида), входные переменные m и n, промежуточная переменная r. Выходная переменная тоже n. Эти переменные должны иметь тип «натуральные числа». Но такого типа в Паскале нет. Поэтому придется использовать какой-то целый тип. От размера типа зависит диапазон чисел, для которых можно использовать программу. Если описать переменные так:

то самым большим числом на входе можно взять 32767 = 2 16 – 1.

Важно! Значение переменных, описанных в разделе Var , не определено. Иногда можно встретить определение переменной как ячейки памяти, в которой содержится значение переменной. Подразумевается, что описание переменной связывает адрес этой ячейки с именем переменной, то есть имя используется как адрес ячейки памяти, где содержится значение. Но само значение еще не определено.

В алгоритме Евклида значение остатка r сравнивается с нулем. 0 – целая константа. Можно (но не обязательно) определить константу со значением 0, например, так:

В процессе компиляции в тексте программы идентификатор Zero будет заменен своим числовым значением.

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

Zero: integer = 0;

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

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

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

Рассмотрим четыре символа и . Если они появляются в последовательности данных с равной вероятностью ( каждая), то мы им просто присвоим четыре двухбитовых кода 00, 01, 10 и 11. Все вероятности равны, и поэтому коды переменной длины не сожмут эти данные. Для каждого символа с коротким кодом найдется символ с длинным кодом и среднее число битов на символ будет не меньше 2. Избыточность данных с равновероятными символами равна нулю, и строку таких символов невозможно сжать с помощью кодов переменной длины (или любым иным методом).

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

	Вероятность

Табл. 1.2. Коды переменной длины.

В табл. 1.2 предложен код Code1, который присваивает самому часто встречающемуся символу самый короткий код. Если закодировать данный с помощью Code1, то среднее число бит на символ будет равно . Это число весьма близко к теоретическому минимуму. Рассмотрим последовательность из 20 символов

в которой четыре символа появляются, примерно, с указанными частотами. Этой строке будет соответствовать кодовая строка кода Code1 длины 37 бит

которая для удобства разделена черточками. Нам понадобилось 37 битов, чтобы закодировать 20 символов, то есть, в среднем 1.85 бит/символ, что не слишком далеко от вычисленной выше средней величины. (Читатель должен иметь в виду, что эта строка весьма коротка, и для того чтобы получить результат, близкий к теоретическому, необходимо взять входной файл размером несколько тысяч символов).

Однако, если мы теперь попробуем декодировать эту двоичную последовательность, то немедленно обнаружим, что Code1 совершенно не годен. Первый бит последовательности равен 1, поэтому первым символом может быть только , так как никакой другой код в таблице для Code1 не начинается с 1. Следующий бит равен 0, но коды для и все начинаются с 0, поэтому декодер должен читать следующий бит. Он равен 1, однако коды для и оба имеют в начале 01. Декодер не знает, как ему поступить. То ли декодировать строку как , то есть, , то ли как , то есть . Причем заметим, что дальнейшие биты последовательности уже не помогут исправить положение. Код Code1 является двусмысленным. В отличие от него, код Code2 из табл. 1.2 дает при декодировании всегда однозначный результат.

Code2 имеет одно важное свойство, которое делает его лучше, чем Code1, которое называется свойством префикса. Это свойство можно сформулировать так: если некоторая последовательность битов выбрана в качестве кода какого-то символа, то ни один код другого символа не должен иметь в начале эту последовательность (не может быть префиксом, то есть, приставкой). Раз строка «1» уже выбрана в качестве целого кода для , то ни один другой код не может начинаться с 1 (то есть, они все должны начинаться на 0). Раз строка «01» является кодом для , то другие коды не должны начинаться с 01. Вот почему коды для и должны начинаться с 00. Естественно, они будут «000» и «001».

Значит, выбирая множество кодов переменной длины, необходимо соблюдать два принципа: (1) следует назначать более короткие коды чаще встречающимся символам, и (2) коды должны удовлетворять свойству префикса. Следуя эти принципам, можно построить короткие, однозначно декодируемые коды, но не обязательно наилучшие (то есть, самые короткие) коды. В дополнение к этим принципам необходим алгоритм, который всегда порождает множество самых коротких кодов (которые в среднем имеют наименьшую длину). Исходными данными этого алгоритма должны быть частоты (или вероятности) символов алфавита. К счастью, такой простой алгоритм существует. Он был придуман Давидом Хаффманом и называется его именем. Этот алгоритм будет описан в § 1.4.

Следует отметить, что не только статистические методы компрессии используют коды переменной длины при кодировании индивидуальных символов. Замечательным примером служат арифметические коды, о которых будет рассказано в § 1.7.