Системы счисления

 

Доведя процедуру до конца, получим сообщение: «мама мыла раму».

 

Код Хаффмана

Способ оптимального префиксного  двоичного кодирования был предложен  Д.Хаффманом. Построение кодов Хаффмана мы рассмотрим на следующем примере: пусть имеется первичный алфавит А, состоящий из шести знаков a₁…а₆ с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Создадим новый вспомогательный алфавит А_b объединив два знака с наименьшими вероятностями (а₅ и а₆) и заменив их одним знаком (например, а⁽¹⁾); вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что число таких

шагов будет равно N - 2, где N - число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных  алфавита). В промежуточных алфавитах  каждый раз будем переупорядочивать  знаки по убыванию вероятностей. Всю  процедуру построения представим в  виде таблицы:

 

 

Теперь в обратном направлении  поведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой - роли не играет; условимся, что верхний знак будет  иметь код 0, а нижний - 1). В нашем  примере знак а₁⁽⁴⁾ алфавита А⁽⁴⁾, имеющий вероятность 0,6 , получит код 0, а а₂⁽⁴⁾ с вероятностью 0,4 - код 1. В алфавите A⁽³⁾ знак а₁⁽³⁾ с вероятностью 0,4 сохранит свой код (1); коды знаков a₂⁽³⁾ и a₃⁽³⁾, объединенных знаком a₁⁽⁴⁾ с вероятностью 0,6 , будут уже двузначным: их первой цифрой станет код связанного с ними знака (т.е. 0), а вторая цифра -как условились - у верхнего 0, у нижнего - 1; таким образом, а₂⁽³⁾ будет иметь код 00,  a a₃⁽³⁾ - код 01.  Полностью процедура кодирования представлена в следующей таблице:

Из самой процедуры  построения кодов легко видеть, что  они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода при этом оказывается: К⁽²⁾ = 0,3-2+0,2-2+0,2-2+0,15-3+0,1-4+0,05-4 = 2,45

Для сравнения можно найти  I₁^{A)-она оказывается равной 2,409. что соответствует избыточности кода Q = 0,0169, т.е. менее 2%.

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

Равномерное алфавитное двоичное кодирование. Байтовый код

В этом случае двоичный код  первичного алфавита строится цепочками  равной длины, т.е. со всеми знаками  связано одинаковое количество информации равное 1₀. Передавать признак конца знака не требуется, поэтому для определения длины кодовой цепочки можно воспользоваться формулой: К⁽²⁾ > log₂N. Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует). Правда, при этом недопустимы сбои, например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи или иными способами. С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи, поскольку факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.

Пример:

Символ	Код
А	00000001
Б	00000010
В	00000011
Г	00000100
Д	00000101
Е	00000110
Ё	00000111
Ж	00001000

 

                        3. Примеры задач и их решения  на тему «Системы  счисления»

1)Выполнить вычитание:

 
а)1100000011,011₍₂₎ -101010111,1₍₂₎ =110101011,111₍₂₎. 
б)1510,2₍₈₎ -1230,54₍₈₎ =257,44₍₈₎. 
в) 27D,D8₍₁₆₎ - 191,2₍₁₆₎ = EC,B8₍₁₆₎.

     1100000011,011          1510,2           27D,D8

    - 101010111,1           -1230,54         -191,2

     --------------          -------          ------

      110101011,111           257,44           EC,B8

 

2)Сложить числа:

 
а)10000000100₍₂₎ +111000010₍₂₎ =10111000110₍₂₎. 
б)223,2₍₈₎ +427,54₍₈₎ =652,74₍₈₎. 
в) 3B3,6₍₁₆₎ + 38B,4₍₁₆₎ = 73E,A₍₁₆₎.

    10000000100           223,2            3B3,6

   +  111000010         + 427,54          +38B,4

   ------------          -------           -----

    10111000110           652,74           73E,A

 

3)Выполнить деление: 
а) 100110010011000₍₂₎ : 101011₍₂₎=111001000₍₂₎; 
б) 46230₍₈₎ : 53₍₈₎=710₍₈₎; 
в) 4C98₍₁₆₎ : 2B₍₁₆₎=1C8₍₁₆₎.

Решение.

4)В какой системе счисления десятичное число 173 будет представлено как 445?

Решение 
Обозначим неизвестное основание за Х. Запишем следующее уравнение: 
173₁₀ =4*Х² +4*Х¹ +5*Х⁰ 
С учетом того, что любое положительное число в нулевой степени равно 1 перепишем уравнение (основание 10 не будем указывать). 
173=4*Х² +4*Х+5 
Конечно, подобное квадратное уравнение можно решить с помощью дискриминанта, но есть более простое решение. Вычтем из правой и левой части по 4. Получим 
169=4*Х² +4*Х+1   или   13² =(2*Х+1)^2.

Отсюда получаем 2*Х +1 = 13 (отрицательный корень отбрасываем). Или Х = 6. 
Ответ: 173₁₀ = 445₆

 
5)Укажите через запятую в порядке  возрастания все основания систем  счисления, в которых запись  числа 24 оканчивается на 3.

Решение 
24 – 3 =21 – это первое основание (13₂₁= 13*21¹+3*21⁰ = 24). 
21 делится на 3 и на 7. Число 3 не подходит, т.к. в системе счисления с основанием 3 нет цифры 3.  
Ответ: 7, 21

6) Решение неравенств.

Поставьте вместо звездочки  знак >, <, = А) 1111112 * 11118 Б) 5110 * 518 В) 1000102 * 2216 

7) Расположите числа, записанные  в различных системах счисления,  в порядке возрастания.

3510, 368, 100011012, 3C16

8) Равенство 41х=718 справедливо  в системах счисления с основанием  х: 

1) 13     2) 11       3) 14        4)16        5) 15

Решение:

 

9) В 8-ичной системе  счисления последняя цифра суммы  чисел 1732+АВD16+3334 равна: 1)4       2) 3        3) 1         4) 2          5) 6.

Решение:  

 

 

 

 

 

10. В классе 11112 девочек и 10102 мальчиков. Сколько учеников в классе?

Решение:    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

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

Изучая источники литературы по теме «Системы счисления» мы получили возможность провести исторический анализ, исследовать различные формы  записи чисел, систематизировать материал и выявить различные спектры  применения.

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

В ходе проведения исследования:

— исследовали историю  и развитие систем счисления,

— исследовали практический материал

— рассмотрели область  применения и выявили актуальность темы.

Нами решены задачи:

— арифметические действия в различных системах счисления,

— перевод из одной системы  счисления в другую.

 

СПИСОК ЛИТЕРАТУРЫ

 

1. Алгебра и теория  чисел: Учеб. пособие для студентов-заочников II курса физ.-мат. фак. пед. ин-тов (Н.А.Казачёк и др.) / Под ред. Н.Я. Виленкина - 2-е изд. М.: Просвещение, 1984. - 192 с.

2. Бендукидзе А.Д. О системах счисления // Квант - 1975 - №8 - с 59-61.

3.Берман Г.Н. Число и  наука о нем. Общедоступные  очерки по   арифметики натуральных  чисел. Изд. 3-е. М.: Физматгиз, 1960. - 164с.

4. Вайман А.А. Шумеро-вавилонская  математика. III - I тысячелетия до н.э. М.: Изд. вост. лит., 1961. - 278с.

5. Выгодский М.Я. Арифметика и алгебра в древнем мире. Изд. 2-е, испр. идоп. М.: Наука, 1967. - 367 с.

6. Глейзер Г.И. История  арифметике в школе: IV - VI кл. Пособие для учителей. - М.: Просвещение, 1981. - 239 с.

7. Гутер Р.С. Вычислительные машины и системы счисления // Квант-1971 -№2.

8. Депман И.Я. История арифметики, пособие для учителей. М.: Учпедгиз, 1959.-423с.

9. Депман И.Я., Виленкин Н.Я. За страницами учебника математики: Пособие для учащихся 5-6 кл. сред. шк. М.: Просвещение, 1989. -287с.

10. Детская энциклопедия: [В 10-ти т.] Для среднего и  старшего возраста. Гл.ред. Маркушевич А.И. Т.2. - Мир небесных тел; Числа и фигуры. -М.: Педагогика, 1972. - 480 с.

11. И. Дышинский Е.А. Игротека математического кружка. М.: Просвещение, 1972. - 144 с.

 

 

12. http://dipland.ru/

13. http://z-cs.ru/referat-na-temu-sistema-schisleniya.html