МИНИСТЕРСТВО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Курганский государственный университет
Кафедра алгебры, геометрии и методики преподавания математики
Курсовая работа
СИСТЕМЫ СЧИСЛЕНИЯ И СПОСОБЫ ДВОИЧНЫХ КОДИРОВОК
Дисциплина Математика
Студент группы №2338 Томрычева Н.С./
Специальность 050202 информатика с дополнительной специальностью математика
Руководитель
Ст.преподаватель Тыщук Л.Н./
Комиссия /……………….…../
/……………….…../
/……………….…../
Дата защиты________________г.
Оценка_____________________
Курган 2010г.
СОДЕРЖАНИЕ
Введение
1. Системы счисления
1.1 История развития различных систем счисления
1.2 Непозиционные и позиционные системы счисления
1.2.1 Непозиционная система счисления
1.2.2 Позиционная система счисления
1.3 Десятичная система счисления и ее происхождения
1.4 Системы счисления с другими основаниями, их происхождение и применение
1.5 Арифметические операции в различных системах счисления
1.6 Перевод из одной системы счисления в другую
2. Использование систем счисления в компьютерной технике и информационных технологиях
2.1 Двоичное кодирование информации в компьютере
2.2 Представление чисел в компьютере
2.3 Способы построения двоичных кодов
Заключение
Список литературы
ВВЕДЕНИЕ
Современный человек в повседневной жизни постоянно сталкивается с числами и цифрами: запоминает номера автобусов и телефонов, в магазине подсчитывает стоимость покупок, ведет свой семейный бюджет в рублях и копейках и т.д. Числа и цифры с нами везде! Интересно, что знал человек о числах две тысячи лет назад? А пять тысяч лет назад?
Историки доказали, что и пять тысяч лет тому назад люди могли записывать числа, могли производить над ними арифметические действия. При этом записывали они числа совершенно по другим принципам, нежели мы в настоящее время. В любом случае число изображалось с помощью одного или нескольких символов. В математике и информатике приняты символы, участвующие в записи числа, называть цифрами.
Что же понимается под словом «число»?
Первоначально понятие отвлеченного числа отсутствовало, число было «привязано» к тем предметам, которые пересчитывали. Отвлеченное понятие натурального числа появляется вместе с развитием письменности.
Появление дробных чисел было связано с необходимостью производить измерения (сравнения с другой величиной того же рода, выбираемой в качестве эталона). Но поскольку единица измерения не всегда укладывалась целое число раз в измеряемой величине, то возникла практическая потребность, ввести более «мелкие» числа, чем натуральные. Дальнейшее развитие понятия числа было обусловлено уже развитием математики.
Понятие числа – фундаментальное понятие, как математики, так и информатики. Под числом мы будем понимать его величину, а не его символьную запись.
Сегодня человечество для записи чисел использует в основном десятичную систему счисления. Что же такое – система счисления? Это мы узнаем в ходе изучения материала и в решении различного рода задач.
Цель исследования
: Выявить и систематизировать материалы по теме: «Системы счисления и основы двоичных кодировок».
Задачи Исследования:
· Изучить литературу по теме исследования;
· Систематизировать теоретический материал;
· Рассмотреть практические применения теоретического материала.
1.
СИСТЕМЫ СЧИСЛЕНИЯ
1.1
История возникновения различных систем счисления
Первобытному человеку считать почти не приходилось. "Один", "два" и "много" - вот все его числа. Но нам - современным людям - приходится иметь дело с числами буквально на каждом шагу. Нам нужно уметь правильно назвать и записать любое число, как бы велико оно ни было. Если бы каждое число называлось особым именем и обозначалось в письме особым знаком, то запомнить все эти слова и знаки было бы никому не под силу. Как же справиться с этой задачей? Нас выручает хорошая система обозначений.
Совокупность немногих названий и знаков, позволяющих записать любое число и дать ему имя, называется системой счисления или нумерацией.
Практически на всем земном шаре алфавитом в языке чисел служат 10 цифр, от 0 до 9. Девять из них используются для обозначения первых девяти натуральных чисел, а десятый - нуль - не обозначает никакого числа, он представляет собой так называемую "позиционную пробку". Этот язык называется десятичной системой счисления.
Однако не во все времена и не везде люди пользовались десятичной системой. С точки зрения чисто математической она не имеет специальных преимуществ перед другими системами счисления, и своим повсеместным распространением эта система обязана вовсе не общим законам математики, а причинам совсем иного характера.
В последнее время с десятичной системой серьезно конкурируют двоичная и, отчасти, троичная системы, которыми "предпочитают" пользоваться современные вычислительные машины.
Как люди считали и как называли числа до изобретения письменности, мы точно не знаем. Об этом можно только догадываться. Несомненно, одно: человечество овладевало счетом очень медленно. Однако ко времени изобретения письменности люди уже умели неплохо считать.
Четыре тысячи лет назад наиболее развитые народы (египтяне, халдеи) умели писать и пользоваться не только целыми, но и простейшими дробными числами. Более того, тогда уже существовали школы, в которых обучали искусству счета.
В первобытном письме букв не было. Каждая вещь, каждое действие изображалось картинкой. Постепенно картинки упрощались. Наряду с изображением предметов и действий появились особые фигуры, обозначающие различные свойства вещей, а так же значки для слов, соответствующих нашим предлогам и союзам.
Так возникла письменность, называемая иероглифами; при иероглифической записи каждому значку соответствует не звук, как у нас, а целое слово.
Специальных знаков (цифр) для записи чисел тогда не было. Но словам "один", "два", ... "семнадцать" и так далее соответствовали определенные иероглифы. Их было не так уж много, так как больших чисел люди тогда не знали.
В некоторых странах (например, Китае и Японии) иероглифическое письмо сохранилось и до наших дней. Вот, для примера, несколько иероглифов:
У славян порядок цифр при записи числа был такой же, как в его устном названии. Мы говорим, например, "пятнадцать" (по-славянски - "пять на десять"), называя вперед цифру единиц, потом десяток. Славяне так и писали, то есть впереди писали пятерку, а за нею десяток. Наоборот, в числе "двадцать три" мы сначала называем десятки, потом единицы, у славян сначала три потом двадцать это отображалось в письме.
Чтобы отличить числа от букв, над ними ставили особый значок - титло. Оно ставилось только над одной из цифр. Место цифры, ее положение в записи числа не имело значения.
С помощью этих знаков легко записывались большие числа. Знак титлообозначал тысячи. С помощью повторения этого знака можно было записывать очень большие числа
Числа до тысячи в Древней Руси назывались почти так же, как сейчас. Существовала небольшая разница в произношении (например, "один" называли "един" и тому подобное). Десять тысяч называлось "тьма", и число это считалось столь огромным, что тем же словом обозначалось всякое, не поддающееся учету множество.
В более позднее время (XVI - XVII вв.) появилась своеобразная система наименования чисел, так называемое "великое славянское число", в этой системе числа до 999999 назывались почти так же, как теперь. Слово "тьма" обозначает уже миллион. Кроме того, появляются следующие названия: "тьма тем", или "легион" (то есть миллион миллионов, или триллион, равен 10); "легион легионов", или "модр" (септиллион, 1024
); наконец, "модр модров", или "ворон" (то есть 1048
).
Позиционная нумерация возникла, по - видимому, в древнем Вавилоне (примерно четыре тысячи лет назад). О ней будет сказано чуть позднее. В Индии она приняла форму позиционной десятичной нумерации с применением нуля. У индусов эту систему чисел заимствовали арабы, ставшие в VIII - IX вв. одним из самых культурных народов мира. От арабов переняли ее европейцы (отсюда название - "арабские цифры").
Особый интерес представляет вавилонская математика. Вавилонская нумерация просуществовала полторы тысячи лет (с XVIII до III в. до нашей эры) и пользовалась широким распространением на всем Ближнем Востоке. Она оказала влияние на китайскую, индийскую и греческую математику.
Вавилоняне писали палочками на пластинках из мягкой глины и обжигали потом свои "рукописи". Получались прочные кирпичные "документы", частично уцелевшие до нашего времени, их нередко находят при раскопках в Месопотамии (теперь Ирак). Поэтому изучить вавилонскую историю и математику в частности удалось довольно хорошо.
На рубеже XIX - XVIII вв. до нашей эры произошло слияние двух народов: сумерийцев и аккадян. Каждый из этих народов имели достаточно развитую торговлю, весовые и денежные единицы, однако разработанной нумерации ни один из этих народов не имел.
У аккадян основная единица - "мекель" - была примерно в 60 раз меньше единицы у сумерийцев - "мины" (примерно пол килограмма). Денежной единицей служила мина серебра.
После слияния этих народов "имели хождение" обе системы единиц: минами и мекелями пользовались так, как мы теперь пользуемся килограммами и граммами (рублями и копейками) с той лишь разницей, что более крупная единица равнялась не 100, а 60 мелким единицам. Со временем появилась более крупная единица - "талант": 1 талант = 60 мин, 1 мина = 60 мекелей.
Как же вавилоняне записывали числа? Они писали палочками, вдавливая их в глину, поэтому основными графическими элементами были у них клинья. Первый обозначал единицы, второй - десятки.
Эти знаки очень наглядны, количество клинышков бросается в глаза, так что пересчитывать их не приходится. Но клинописное письмо очень неудобно для оценки величины промежутков между числами, а необходимость переписывать все от руки приводила к частым опискам. Знак разделения был необходим, и он появился. Начиная с некоторого времени, на вавилонских кирпичиках появляется значок ^ , соответствующий нашему нулю
Однако, введя "позиционную пробку" в середине чисел, вавилоняне так и не додумались ставить ее на конце. И до самого падения вавилонской культуры числа 1, 60, 3000 записывались одинаково.
Только индусы, заимствовавшие у них позиционную нумерацию, научились правильно использовать знак нуля, и, введя вместо 60 основание 10, дали счислению его современную форму.
Три тысячи лет назад индусы уже пользовались современной нумерацией, хотя в памятниках того времени и не упоминаются числа, большие 100000. В более поздних источниках встречаются значительно большие числа - до ста квадриллионов (1017
). В одной из сравнительно молодых легенд о Будде говорится, что он знал названия чисел до 1054
. Впрочем, индусы, по - видимому, не представляли себе бесконечности натурального ряда, они полагали, что существует какое -то наибольшее число, известное только богам.
Доказательство бесконечности числового ряда — заслуга древнегреческих ученых.
1.2 Непозиционные и позиционные системы счисления
Система счисления (Нумерация) - это способ представления числа символами некоторого алфавита, которые называются цифрами.
Путем длительного развития человечество пришло к двум видам систем счисления: позиционной и не позиционной.
1.2.1 Непозиционная система счисления
В самой древней нумерации употреблялся лишь знак "|" для единицы, и каждое натуральное число записывалось повторением символа единицы столько раз, сколько единиц содержится в этом числе. Сложение в такой нумерации сводилось к приписыванию единиц, а вычитание - к их вычеркиванию. Для изображения сколько – нибуть больших чисел этот способ нумерации непригоден из - за своей громоздкости.
При начальном обучении в школе, когда счет ведется в пределах одного - двух десятков, этот способ нумерации успешно применяется (счет на палочках).
В непозиционных системах счисления смысл каждого знака сохраняется и не зависит от его места в записи числа.
К более современным непозиционным системам относят египетскую иероглифическую систему нумерации, в которой имелись определенные знаки для чисел: единица - I, десять - n, сто - ρ и так далее; эти числа называются узловыми. Все остальные натуральные числа, называемые алгоритмическими числами, записываются единообразно при помощи единственной арифметической операции - сложения. Например ,число 243 запишется в виде ρρ nnnnIII, 301 - в виде ρρρ I.
К непозиционным системам относят римскую нумерацию. За узловые числа в этой системе принимают числа: единица - I, пять - V, десять - X, пятьдесят - L, сто - С, пятьсот - D, тысяча - М. Все алгоритмические числа получаются при помощи двух арифметических операций: сложения и вычитания. Вычитание производится тогда, когда знак, соответствующий меньшему узловому числу, стоит перед знаком большего узлового числа, например, VI - шесть (5+1= 6), ХС – девяносто(100-10=90), 1704 - МОССIV, 193 -СХСШ, 687 - DCLXXXII.
В римской нумерации заметны следы пятеричной системы счисления, так как в ней имеются специальные знаки для чисел 5, 50 и 500.
При записи чисел использовался не только принцип сложения, но и принцип умножения.
Например, в старо — китайской системе счисления числа 20 и 30 изображались схематически, как 2,10 и 3,10. числа 10, 100, 1000 имели определенные специальные обозначения. Число 528 записывалось так: 5,100,2,10,8.
Наиболее удобными среди непозиционных систем счисления являются алфавитные системы нумерации. Примерами таких систем могут служить ионийская система (Древняя Греция), славянская, еврейская, грузинская и армянская.
Во всех алфавитных системах существенным является обозначение специальными символами - буквами в алфавитном порядке всех чисел от 1 до 9, всех десятков от 10 до 90 и всех сотен от 100 до 900. Чтобы отличать запись чисел от слов над буквами, обозначающими цифры, в греческой и славянской нумерации ставилась черта.
В греческой системе счисления число 543 записывалось: φμγ (φ - 500, μ- 40, γ- 3). В римской системе счисления это число записывается в виде DXLIII, в египетской иероглифической - в виде ρρρρρ nnnIII.
Из этого примера видно преимущество алфавитной нумерации, в которой используется цифровой принцип обозначения единиц, десятков, сотен.
В записи больших чисел в алфавитной системе уже виден переход к позиционной системе записи. Например, 32543 записывалось так
Наиболее удобными системами счисления оказались позиционные или поместные системы.
1.2.2 Позиционные системы счисления
Позиционная система счисления - это совокупность определений и правил, позволяющих записывать любое натуральное число с помощью некоторых значков или символов, каждый из которых имеет определенный смысл в зависимости от его места в записи числа (от его позиции). Чаще всего применяют позиционную систему счисления с фиксированным основанием. Основанием системы может быть любое натуральное число ρ, ρ>1
Систематической записью натурального числа N по основанию ρназывают представление этого числа в виде суммы:
N = аn
ρn
+...+а1
ρ, + а0
где аn
, ..., а1
, а0
- числа принимающие значения 0, 1, ..., ρ - 1, причем, аn
≠0.
Позиционная система счисления с основанием ρ называется ρ — ичной (двоичной, троичной и так далее). На практике чаще всего применяется десятичная ρ= 1
0).
Для обозначения чисел 0, 1, ..., ρ - 1 в ρ - ичной системе счисления используют особые знаки, называемые цифрами. Древнеиндийские математики открыли нуль - особый знак, который должен был показать отсутствие единиц определенного разряда.
Для ρ - ичной системы счисления нужно ρ цифр. Если ρ < 10, то применяются те же обозначения цифр, что и в десятичной системе счисления (только берутся цифры, меньше основания системы).
В системах с основанием ρ >
10 для чисел, больших или равных 10, не вводят специальных символов, а используют десятичную запись этих чисел, заключая эту запись в скобки. Например, в четырнадцатеричной системе имеется четырнадцать цифр: 0, 1, 2, 3 ... 9, (10), (11), (12), (13).
В системе счисления с основанием ρ, так же как и в десятичной системе счисления, место, занимаемое цифрой, считая, справа налево, называется разрядом.
Число N= аn
ρn
+ . . . +a1
ρ +а0
содержит а0
единиц первого разряда, а1
единиц второго разряда, а2
единиц третьего разряда и так далее. Единица следующего разряда в ρ раз больше единицы предыдущего разряда.
Позиционные системы счисления удовлетворяют требованию возможности и однозначности записи любого натурального числа.
Теорема. Любое натуральное число N может быть записано в системе с основание ρ и притом единственным образом.
Доказательство:
1. Докажем существование представления любого натурального числа в виде
N=an
ρn
+an
-1
ρn
-1
+ ... +аρ+а0
(1)
Доказательство проведем методом полной математической индукции.
Представление числа N в виде (1) возможно для первых р-1 натуральных чисел 1, 2,..., ρ-1, так как n=1 и число совпадает с данным числом. Представление числа в виде (1) для чисел 1, 2, . . . ,ρ-1, очевидно, возможны только единственным способом: 1=1, 2=2,. . . ,ρ-1=ρ-1.
Предположим, что все натуральные числа N≤k (к≥1) представимы в виде (1). Докажем что число к+1 так же представимо в виде (1). Для этого разделим с остатком число к+1 на ρ:
K+l=sρ
+r, 0<г<ρ-1 (2)
где s - неполное частное и г - остаток.
Так как число s≤k, то оно по предположению индукции представимо в виде (1):
s = аn
ρn
+ . . . +a1
ρ +а0
(3)
где 1≤аn
≤ρ -1, 0≤ ai
≤ρ -l, (i=0,1,..,n-1)
Подставим выражения (2) и (3), получим:
k+l= (an
ρ+ ... +аi
ρ +а0
) ρ + г = аn
ρ +... + ai
ρ +a0
ρ +г (4)
где 1 ≤an
≤ρ -1, 0≤aj
≤ ρ -1, 0 ≤ г ≤ ρ -1 0=0,1,. . ,n-1)
Это выражение (4) дает представление числа к+1 в виде (1):
К+1=bn
+1
ρ n
+1
+ bn
ρ n
+ ... + b1
ρ +b0
где b0
=r, bi+1
- ai
(i=0,l,.. ,n-l)
2. Докажем единственность представления любого натурального числа в виде (1).
Доказательство проведем методом математической индукции.
Для чисел 1, 2,... , ρ -1 представление в виде (1) единственно.
Предположим что для всех натуральных N≤k (к≥1) представление в виде (1) единственно. Докажем, что число к+1 может быть представлено в виде (1) только одним способом. Для этого разделим с остатком число к+1 на ρ:
K+l=sρ
+r, 0<г< ρ -1 (5)
Предположим, что к+1 имеет два различных способа представления:
к+1=а n
ρ n
+ аn
-1
ρ n
-1
+ ....+ а1
ρ +а()
(6)
к+1 =bm
ρ m
+ bm
-1
ρ m
-1
+ ... + b1
ρ +b0
(7)
Представим: равенства (6) и (7) в виде:
k+1= (а n
ρ n
-1
+ an
-1
ρ n
-2
+ ... + а1
)ρ+а0
(6*)
k+1 = (bm
ρ m
-1
+ bm
-1
ρ m
-2
+ ... + b)ρ+b0
(7*
)
Так как 0 ≤ а0
≤ρ -1 и 0 ≤ b0
≤ρ -1, то из (6*) и (7*) следует, что неполное частное s и остаток г в формуле (5) будут:
S= аn
ρn-1
+ аn-1
ρn-2
+ ... + a1
=bm
ρm-1
+ bm-1
ρm-2
+ ... + b1.
r = a0
= b0
Так как s ≤ k, из индуктивного предположения следует, что число s имеет единственно представление в виде (1), то есть
n-l = m-l, ai
=bi
, (i=0,1, . . ,n-1).
Из последнего равенства имеем а0
=bо
. Таким образом, n=m, ai
=bi(i=0,l, . . ,n-l), но это противоречит допущению, что число k+1. имеет два различных представления (6) и (7). Следовательно, число к+1 представляется в виде (1) единственным образом. На основании принципа математической индукции утверждение справедливо для любого N . Теорема доказана.
1.3 Десятичная система счисления, ее происхождение и применение.
Представьте, что вы пересчитываете большое число одинаковых предметов, например, спичек. Удобнее всего будет разложить эти предметы как кучки по десять в каждой. Получится некоторое количество десятков (и, может быть, останутся несколько предметов, не вошедших в целые десятки). Далее придется пересчитывать кучки (десятки). Если кучек (десятков) будет очень много, можно их тоже сгруппировать в десятки, и так далее.
Таким путем мы приходим к основной идее нашей системы счисления — к мысли о единицах различных разрядов. Десять единиц образуют один десяток, то есть десять единиц первого разряда образуют одну единицу второго разряда, десять единиц второго - единицу третьего и так далее.
Несмотря на свою кажущуюся простоту, такая система счисления прошла очень долгий путь исторического развития. В ее создании принимали участие многие народы.
Возникает вопрос - почему стали раскладывать предметы на десятки, а не на пятки или дюжины? Почему единицы каждого разряда в десять, а не в восемь или три раза больше единиц предыдущего разряда?
Счет десятками получил широкое распространение потому, что люди располагают естественной "счетной машиной", связанной с числом десять -десятью пальцами на руках.
Десятичная нумерация "изобретена" индусами; в Европу ее занесли арабы, вторгшиеся в Испанию в VIII в. нашей эры. Арабская нумерация распространилась по всей Европе, и, будучи проще и удобнее остальных систем счисления, быстро их вытеснила. До сих пор наши цифры принято называть арабскими. Впрочем, за тысячу лет все цифры, кроме 1 и 9, сильно изменились. Вот, для сравнения, наши (называемые арабскими) и настоящие арабские цифры:
Названия первых шести разрядов (единицы, десятки, сотни, тысячи и так далее) очень древние и у разных народов звучат по-разному.
Слово "миллион" сравнительно недавнего происхождения. Придумал его известный венецианский путешественник Марко Поло, которому не хватало обыкновенных чисел, чтобы рассказать о необычайном изобилии людей и богатств далекой Небесной Империи (Китай). По-русски слову "миллион" могло бы соответствовать несуществующее слово "тысячища".
Для построения числовых наименований более высоких порядков используются латинские числительные (биллионы, триллионы). Построенные таким образом названия мало удобны, латынь знают не все. Да и вообще такие числа встречаются только в сборниках математических курьезов, да в некоторых отделах теории чисел. Нет необходимости придумывать им рациональные названия. Здесь на помощь приходит понятие степени. Число, изображаемое единицей с нулями, является степенью десятки: 100= 102
, 1000= 103
, 10...00...00= 10n
.
Эти соображения позволяют нам очень коротко и удобно записывать все числа, которые даются нам наукой и жизнью. Например, масса Земного шара - 6 000 000 000 000 000 000 000 тонн. Мы можем записать: 6 • 1021
тонн, и назвать "шесть на десять в двадцать первой степени", это коротко и удобно.
В практической жизни при счете предметов, которых очень много, например, жителей страны, при измерении различных величин, удается определить только первые несколько цифр результата. Любое число, данное практически, удается записать как произведение не более чем восьмизначного (чаще трех - четырехзначного) числа на "единицу с нулями". Например, поверхность Земли - 509 000 000 км2
. Можно записать так: 509 • 106
км2
.
Классическим примером числового гиганта является награда, которую, если верить старинной легенде, потребовал себе изобретатель шахматной доски: за первую клетку доски — одно зерно риса, за вторую — два, за третью - четыре и так далее, за каждую последующую - в два раза больше, чем за предыдущую. Эта скромная на вид просьба оказалась невыполнимой: все житницы мира не смогут вместить риса, затребованного хитрым изобретателем.
Таким образом, для обозначения и записи чисел мы пользуемся позиционной десятичной нумерацией. Позиционной она называется потому, что значение цифры зависит от ее положения - места в ряду других цифр в записи числа; десятичной - потому, что из двух написанных рядом цифр левая обозначает единицы в десять раз большие, чем правая. Для обозначения и записи чисел в пределах миллиарда эта система очень удобна. При записи очень больших чисел пользуются понятием степени числа.
1.4 Системы счисления с другими основаниями, их происхождение и применение
Кроме десятичной системы счисления возможны позиционные системы счисления с любым другим натуральным основанием. В разные исторические периоды многие народы широко использовали различные системы счисления.
Двенадцатеричная система счисления - ее происхождение тоже связано со счетом на пальцах: так как четыре пальца руки (кроме большого) имеют в совокупности двенадцать фаланг, то по этим фалангам, перебирая их по очереди большим пальцем, и ведут счет от одного до двенадцати. Затем двенадцать принимается за единицу следующего разряда и так далее. В устной речи остатки двенадцатеричной системы сохранились и до наших дней: вместо того, чтобы сказать "двенадцать" часто говорят "дюжина". Многие предметы (ножи, вилки, тарелки) очень часто считают именно дюжинами, а не десятками; сервизы бывают, как правило, на двенадцать или шесть персон. Другой пример: двенадцать месяцев в году, двенадцать цифр на циферблате часов.
Восьмеричная система счисления - позиционная система счисления с основанием 8. Для представления чисел в ней используются арабские цифры. Используется всего восемь цифр - 0, 1, 2, 3, 4, 5, 6, 7.Восьмеричная система часто используется в областях, связанных с цифровыми устройствами. Характеризуется лёгким переводом восьмеричных чисел в двоичные и обратно, путём замены восьмеричных чисел на триады двоичных. Широко использовалась в программировании в 1950-70-ые гг. и вообще в компьютерной документации, однако в настоящее время почти полностью вытеснена шестнадцатеричной.
Шестидесятеричная система счисления существовала и возникла в Древнем Вавилоне. Мнения историков по поводу того, как именно возникла эта система, расходятся. Одна из гипотез, состоит в том, что произошло слияние двух племен, одно из которых пользовалось шестеричной системой счисления, я второе - десятичной. Шестидесятеричная система возникла как компромисс между этими двумя системами. Другая гипотеза состоит в том, что вавилоняне считали продолжительность года равной 360 суткам, что, естественно, связывалось с числом 60. однако это предположение тоже нельзя считать достаточно обоснованным: астрономические познания древних вавилонян были довольно значительны, поэтому следует думать, что погрешность, с которой они определяли продолжительность года, была значительно меньше, чем пять суток.
Пятеричная система счисления была распространена у ряда африканских племен. Связь этой системы со строением человеческой руки - первоначальной "счетной машины" - достаточно очевидна. В Китае принято считать пятками, причем пятки группируются в пары; получается своеобразная система счисления, в которой каждая единица четного порядка в пять, а нечетного - в два раза больше предыдущей. Однако эта система счисления с двойным основанием, отражающая счет с помощью двух рук, довольно сложна. Гораздо чаще используется чистая пятеричная система, то есть позиционная система с основанием пять.
Двадцатеричная система счисления была принята у ацтеков и майя -народов, населявших в течение многих столетий обширные области американского континента и создавших там высокую культуру, почти полностью уничтоженную испанскими завоевателями в XVI - XVII вв. Та же двадцатеричная система была принята и у кельтов, населявших Западную Европу, начиная со II в. до нашей эры.
Из пяти перечисленных выше систем счисления, сыгравших, наряду с десятичной, заметную роль в развитии человеческой культуры, все, кроме шестидесятеричной, источники которой не ясны, связаны с тем или иным способом счета по пальцам рук (или и рук, и ног), то есть имеют несомненное "анатомическое" происхождение.
Все позиционные системы с любым натуральным основанием устроены одинаково. В любой позиционной системе счисления основание записывается в виде десяти, поскольку оно есть единица второго разряда. Все натуральные числа, меньше основания, должны быть однозначными и изображаться разными знаками. Поэтому количество цифр, используемых в данной позиционной системе, совпадает с основанием системы.
1.5 Арифметические операции в различных системах счисления
1.5.1 Сложение и вычитание
В системе с основанием я для обозначения нуля и первых ρ-
1 натуральных чисел служат цифры 0, 1, 2, ..., ρ - 1. Для выполнения операции сложения и вычитания составляется таблица сложения однозначных чисел.
| +
|
0
|
1
|
2
|
· | · | · | q-1
|
| 0
|
0
|
1
|
2
|
***
|
***
|
***
|
q-1
|
| 1
|
1
|
2
|
3
|
***
|
***
|
***
|
10
|
| 2
|
2
|
3
|
4
|
***
|
***
|
***
|
11
|
| ***
|
***
|
***
|
***
|
***
|
***
|
***
|
***
|
| q-1
|
q-1
|
10
|
11
|
***
|
***
|
***
|
1(q-2)
|
Например, таблица сложения в шестеричной системе счисления:
| +
|
0
|
1
|
2
|
3
|
4
|
5
|
| 0
|
0
|
1
|
2
|
3
|
4
|
5
|
| 1
|
1
|
2
|
3
|
4
|
5
|
10
|
| 2
|
2
|
3
|
4
|
5
|
10
|
11
|
| 3
|
3
|
4
|
5
|
10
|
11
|
12
|
| 4
|
4
|
5
|
10
|
11
|
12
|
13
|
| 5
|
5
|
10
|
11
|
12
|
13
|
14
|
Сложение любых двух чисел, записанных в системе счисления с основанием ρ, производится так же, как в десятичной системе, по разрядам, начиная с первого разряда, с использованием таблицы сложения данной системы. Складываемые числа подписываются одно за другим так, чтобы цифры одинаковых разрядов стояли по вертикали. Результат сложения пишется под горизонтал
Например,
Можно обосновать указанное правило сложения чисел, используя представление чисел в виде
Разберем один из примеров:
3547
=3*72
+5*71
+4*70
2637
=2*72
+6*71
+3*70
Имеем:
(3*72
+5*71
+4*70
) + (2*72
+6*71
+3*70
) =
=(3+2)*72
+(5+6)*7+(3+4)
=5*72
+1*72
+4*7+7
=6*72
+4*7+7
=6*72
+5*7+0
=6507
Последовательно выделяем слагаемые по степени основания 7, начиная с низшей, нулевой, степени.
Вычитание производится также по разрядам, начиная с низшего, причем если цифра уменьшаемого меньше цифры вычитаемого, то из следующего разряда уменьшаемого "занимается" единица и из полученного двузначного числа вычитается соответствующая цифра вычитаемого; при вычитании цифр следующего разряда в этом случае нужно мысленно уменьшить цифру уменьшаемого на единицу, если же эта цифра оказалась нулем (и тогда уменьшение ее невозможно), то следует "занять" единицу из следующего разряда и затем произвести уменьшение на единицу. Специальной таблицы для вычитания составлять не нужно, так как таблица сложения дает результаты вычитания.
Например,
1.5.2 Умножение и деление
Для выполнения действий умножения и деления в системе с основанием ρ составляется таблица умножения однозначных чисел.
| *
|
0
|
1
|
2
|
· | · | · | q
-1 |
| 0
|
0 | 0 | |||||
| 1
|
0 | q-1 | |||||
| 2
|
0 | 1(q-1) | |||||
| ***
|
*** | *** | |||||
| q
-1 |
0 | 1(q-2) |
Например, таблица умножения в шестеричной системе счисления:
| *
|
0
|
1
|
2
|
3
|
4
|
5
|
| 0
|
0 | 0 | 0 | 0 | 0 | 0 |
| 1
|
0 | 1 | 2 | 3 | 4 | 5 |
| 2
|
0 | 2 | 4 | 10 | 12 | 14 |
| 3
|
0 | 3 | 10 | 13 | 20 | 23 |
| 4
|
0 | 4 | 12 | 20 | 24 | 32 |
| 5
|
0 | 5 | 14 | 23 | 32 | 41 |
Умножение двух произвольных чисел в системе с основанием ρ производится так же, как в десятичной системе - "столбиком", то есть множимое умножается на цифру каждого разряда множителя (последовательно) с последующим сложением этих промежуточных результатов.
Например,
При умножении многозначных чисел в промежуточных результатах индекс основания не ставится:
Деление в системах с основанием ρ производится углом, так же, как в десятичной системе счисления. При этом используется таблица умножения и таблица сложения соответствующей системы. Сложнее дело обстоит, если результат деления не является конечной ρ-ичной дробью (или целым числом). Тогда при осуществлении операции деления обычно требуется выделить непериодическую часть дроби и ее период. Умение выполнять операцию деления в ρ-ичной системе счисления полезно при переводе дробных чисел из одной системы счисления в другую.
Например:
1.6 Перевод чисел из одной системы счисления в другую
Существует много различных способов перевода чисел из одной системы счисления в другую.
Способ деления.
Пусть дано число N=an
an
-1
. . . a1
а0
р
.
Для получения записи числа N в системе с основанием h следует представить его в виде:
N=bm
hm
+bm-1
hm-1
+... +b1
h+b0
(1)
где1<bm
<h-1, 0 ≤ bi
≤ h-l (i=0, 1,... ,m-l), тогда
N=bm
bm
-1
... b1
bo
h (2)
Из (1) получаем:
N= (bm
hm
-1
+...+b)*h +b0
= N1
h+b0
, где 0≤ b0
≤h (3)
To есть цифра b0
является остатком от деления числа N на число h. Неполное частное Nl
= bm
hm
-1
+ . . . +
b1
представим в виде:
Nl
= (bm
hm
-2
+ ... + b2
)h + b1
= N2
h+b1
, где 0≤ b2
≤h (4)
Таким образом, цифра bi
в записи (2) числа N является остатком от деления первого неполного частного N1
на основание h новой системы счисления. Второе неполное частное N2
представим в виде:
N2
= (bm
hm
-3
+ ... +b3
)h+b2
, где 0≤ b2
≤h (5)
то есть цифра b2
является остатком от деления второго неполного частного N2
на основание h новой системы. Так как не полные частные убывают, то этот процесс конечен. И тогда мы получаем Nm
= bm
, где bm
<h, так как:
Nm-1
= bm
h+bm
.1
= Nm
h+bm
.1
Таким образом, последовательность цифр bm
, bm
-1
. . ,b1
,b0
в записи числа N в системе счисления с основанием h есть последовательность остатков последовательного деления числа N на основание h, взятая в обратной последовательности.
Рассмотрим пример: Выполнить перевод числа 123 в шестнадцатеричную систему счисления:
Таким образом, число 12310
=7(11)16
либо можно записать как 7B16
Запишем число 340227
в пятеричной системе счисления:
Таким образом, получаем, что 340227
=2333315
Перевод с использованием десятичной системы счисления
.
Любое число в любой системе счисления представимо в виде:
N = an
pn
+...+a1
p+a0
Таким образом, имея запись числа в таком виде, мы легко можем перевести его в привычную нам десятичную систему счисления. Например
22095
=2*53
+2*52
+0*51
+9*50
=30910
Так же, число, представленное в десятичной системе счисления, мы можем расписать по степеням любого другого основания:
2208097
=2*75
+2*74
+0*73
+8*72
+0*71
+9*70
=388177
Таким способом можно перевести числа из одной системы в другую. Например: переведем число 6257
в 3-ичную систему счисления.
6257
=6*
72
+2*71
+5*70
=6*49+2*7+5=31310
31310
=1*35
+0*34
+2*33
+1*32
+2*31
+1*30
=1*243+2*27+1*9+2*3+1=1021203
Ответ: 625т=1021203
Систематические дроби. Перевод дробей в различные системы счисления.
Известно, что десятичная дробь отличается от целого числа только наличием запятой, отделяющей целую часть от дробной, и такое сходство не случайно.
Можно сказать, что запись дробного числа в виде десятичной дроби представляет собой перенесение общего принципа записи чисел в позиционной десятичной системе счисления на дробные числа.
В самом общем случае смешанное число, содержащее целую и дробную части, представляется в виде суммы степеней десятки и
Десятичные дроби являются частным случаем систематических дробей, которые можно строить аналогичным образом для любой позиционной системы счисления.
Например, дробь 5-1
+ 6-2
+ 3-3
назвать восьмеричной и записать в виде: 0,5638
.
Правила арифметических действий над ρ -
ичными дробями (основание системы - q) такие же, как и над десятичными, но при действиях с однозначными числами нужно пользоваться таблицами сложения и умножения для данной системы.
Следует заметить, что не всякая простая дробь может быть записана в виде конечной десятичной дроби. Это явление наблюдается и в других позиционных системах счисления. При этом одно и то же число может в одной системе счисления записываться в виде конечной дроби, а в другой - в виде бесконечной.
Например:
При переводе дробей из одной позиционной системы счисления в другую необходимо иметь в виду возможность получения бесконечных дробей.
Общее правило перевода числа в систему счисления с основанием n:
Для перевода целого числа в систему счисления с основанием n его надо последовательно делить на n (отбрасывая остатки), при переводе дроби, меньшей единицы – последовательно умножить на n (отбрасывая целые). Цифрами числа в n – ичной системе счисления в первом случае будут остатки, записанные в обратном порядке, а во втором – целые части, записанные в порядке их получения. Целые и дробные части в смешанном числе переводятся отдельно.
Пример: 378,835937510
перевести в систему счисления с основанием q=8
Итак, 378,835937510
=572,6548
Быстрый перевод чисел из двоичной системы счисления в восьмеричную и шестнадцатеричную и обратно.
Перевод чисел между системами счисления, основания которых являются степенями числа 2, может производиться более простым алгоритмом.
Для записи двоичных чисел используют две цифры, то есть в каждом разряде числа возможны два варианта записи. Для записи восьмеричных чисел используется восемь цифр, то есть возможны восемь вариантов. А для записи шестнадцатеричных чисел используется 16 цифр, то есть 16 возможных вариантов.
Таким образом, для перевода целого двоичного числа в восьмеричное его нужно разбить на группы по три цифры, справа налево, а затем преобразовать каждую группу в восьмеричную цифру. Если в последней, левой, группе окажется меньше трех цифр, то нужно его дополнить нулями слева.
Пример:
100 101 000 0102
4 5 0 28
111 111 101 000 010 000 1002
7 7 5 0 2 0 48
А для перевода целого двоичного числа в шестнадцатеричное, число разбивают на группы по 4 цифры и следуют тому же алгоритму, что и с
восьмеричной системой счисления.
Например:
1001 0000 1100 0111 00012
9 0 С 7 116
Например:
1111 1001 1101 0002
F 9 D 016
Данное правило работает и наоборот, то есть любое целое число можно перевести из восьмеричной в двоичную и из шестнадцатеричной в двоичную.
Например:
| 1 | 2 | 3 | 4 | 5 | 6 | 78
|
| 001 | 010 | 011 | 100 | 101 | 110 | 1112
|
| А | B | C | D | E | F | 1 | 2 | 3 | 4 | 5 |
| 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | 0001 | 0010 | 0011 | 0100 | 0101 |
| 6 | 7 | 8 | 916
|
| 0110 | 0111 | 1000 | 10012
|
2. ИСПОЛЬЗОВАНИЕ СИСТЕМ СЧИСЛЕНИЯ В КОМПЬЮТЕРНОЙ ТЕХНИКЕ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЯХ
Столь привычная для нас десятичная система оказалась неудобной для ЭВМ. Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент с множеством состояний (колесо с девятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях. Наиболее просто реализуется элементы с двумя состояниями - триггеры. Поэтому естественным был переход на двоичную систему, т.е. системы по основанию 2. В этой системе всего две цифры - 0 и 1 . Каждая цифра называется двоичной (от английского binarydigit - двоичная цифра). Сокращение от этого выражения привело к появлению термина бит, ставшего названием разряда двоичного числа.
Бит - это минимальная единица измерения информации (0 mini). За битом следует байт, состоящий из восьми бит, затем килобайт (кбайт) - 1024 байта, мегабайт (мбайт) - 1024 кбайта, гигобайт (гбайт) - 1024мбайт.
2.1
Двоичное кодирование информации в компьютере
Для обмена информацией с другими людьми человек использует естественные языки (русский, английский, китайский и т.д.), те есть информация представляется с помощью естественных языков. В основе языка лежит алфавит, то есть набор символов (знаков, которые человек различает по их начертанию. Последовательности символов алфавита в соответствии с правилами грамматики образуют основные объекты языка -слова. Правила, согласно которым образуются предложения из слов данного языка называются синтаксисом. Необходимо от метить, что в естественных языках грамматика и синтаксис языка формируются с помощью большого количество правил, из которых существуют исключения, так как такие правила складывались исторически.
Наряду с естественными языками были разработаны формальные языки (системы счисления, язык алгебры, языки программирования и др.). Основное отличие формальных языков от естественных состоит в наличии жестких правил грамматики и синтаксиса. Эти языки были разработаны людьми, для упрощения каких-либо действий. Как, например, системы счисления были придуманы для упрощения подсчетов чего-либо.
Создатели первых компьютеров столкнулись с проблемой представления и обработки информации. Так как компьютер это всего лишь машина у которой нет ни интеллекта, ни логики, и мыслить она не способна, разработчикам пришлось найти такой способ представления информации, который был бы максимально прост для восприятия компьютером. Столь привычная для нас десятичная система оказалась неудобной для ЭВМ. Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент с множеством состояний (колесо с девятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях. Наиболее просто реализуется элементы с двумя состояниями - триггеры. Поэтому естественным был переход на двоичную систему, т.е. системы по основанию 2. В этой системе всего две цифры - 0 и 1 . Каждая цифра называется двоичной (от английского binarydigit - двоичная цифра). Сокращение от этого выражения привело к появлению термина бит, ставшего названием разряда двоичного числа.
Бит - это минимальная единица измерения информации (0 или1). За битом следует байт, состоящий из восьми бит, затем килобайт (кбайт) - 1024 байта, мегабайт (мбайт) - 1024 кбайта, гигобайт (гбайт) - 1024мбайт.
Таким образом, в компьютере для представления информации используется двоичное кодирование, так как удалось создать надежные работающие технические устройства, которые могут со стопроцентной надежностью сохранять и распознавать не более двух различных состояний (цифр). Все виды информации в компьютере кодируются на машинном языке, в виде логических последовательностей нулей и единиц.
Таким образом, информация представляется в виде конечной последовательности 0 и 1. Например целое неотрицательное число А2
=Т 111100002
будет храниться в ячейке следующим образом:
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Значит, мы можем записать все числа от 0 до 255 в двоичной системе счисления в 1 ячейке памяти.
2.2 Представление чисел в компьютере
Целые числа в компьютере хранятся в ячейках памяти, в этом случае каждому разряду ячейки памяти соответствует всегда один и тот же разряд числа.
Для хранения целых неотрицательных чисел отводится одна ячейка памяти состоящая из восьми бит.
Например, число 1910
будет выглядеть:
| 0 | о | 0 | 1 | 0 | 0 | 1 | 1 |
Для хранения целых чисел со знаком (отрицательных) отводиться две ячейки памяти (16 битов), причем старший (левый) разряд отводиться под знак числа (если число положительное, то в знаковый разряд записывается 0, если отрицательное - 1).
Например, число -9810
будет выглядеть:
| 1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
Представление целых чисел в компьютере в формате «знак - величина» называется прямым кодом числа. Например, число 200210=111110100102
будет представлено в шестнадцатиразрядном представлении следует следующим образом:
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
Для представления отрицательных чисел используется дополнительный код. Дополнительный код позволяет заменить арифметическую операцию
вычитания операцией сложения, что существенно упрощает работу процессора и увеличивает его быстродействие. Дополнительный код представляет собой дополнение модуля отрицательного числа А до О,
2n
-|А|+|А| =0
поскольку в компьютерной 2n
=0.
Алгоритм построения такого кода довольно прост:
1. Записать модуль числа в прямом коде.
2. Получить обратный код числа (то есть заменить все нули на единицы, а все единицы на нули).
3. К полученному результату прибавить единицу.
Запишем дополнительный код отрицательного числа -2002 для 16-разрядного представления:
Запишем дополнительный код отрицательного числа -16320 для 16-разрядного представления:
2.3 Способы построения двоичных кодов
Начиная с конца 60-х годов, компьютеры все больше использовать для обработки текстовой информации и в настоящее время большая часть компьютеров в мире занято именно обработкой текстовой информации.
Традиционно для кодирования одного символа используется количество информации равное 1 байту, то есть 8 бит. Если рассматривать символы как возможные события, то получаем, что количество различных символов, которые можно закодировать, будет равно 256. Такое количество символов вполне достаточно для представления текстовой информации, включая прописные и строчные буквы русского и латинского алфавитов, а так же цифры, знаки препинания и математических операций, графические символы и так далее.
Но способов построения таких кодов очень много, рассмотрим некоторые из них:
Алфавитное неравномерное двоичное кодирование
При алфавитном способе двоичного кодирования символы некоторого первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (т.е. 0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Оптимизировать кодирование можно за счет суммарной длительности сообщения.
Суммарная длительность сообщения будет меньше, если применить следующий подход: чем буква первичного алфавита, встречается чаще, то присваиваем ей более короткой по длине код. Следовательно, коды букв, вероятность появления которых в сообщении выше, следует строить из возможно меньшего числа элементарных сигналов.
Возможны различные варианты двоичного кодирования, однако, не все они будут пригодны для практического использования - важно, чтобы закодированное сообщение могло быть однозначно декодировано,
т.е. чтобы в последовательности 0
и 1, которая представляет собой многобуквенное кодированное сообщение, всегда можно было бы различить обозначения отдельных букв.
Рассмотрим пример построения двоичного кода для символов русского алфавита:
Неравномерный код с разделителями
Для того что бы было проще декодировать сообщения был придуман код с разделителями.
Проще всего достичь однозначного декодирования, если коды будут разграничены разделителем -
некоторой постоянной комбинацией двоичных знаков. Условимся, что разделителем отдельных кодов букв будет последовательность 00(признак конца знака), а разделителем слов - 000(признак конца слова - пробел). Довольно очевидными оказываются следующие правила построения кодов:
— код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться 00);
— коды букв не должны содержать двух и более нулей подряд в
середине (иначе они будут восприниматься как конец знака);
— код буквы (кроме пробела) всегда должен начинаться с 1;
— разделителю слов (000)всегда предшествует признак конца знака;
при этом реализуется последовательность 00000(т.е. если в конце кода встречается комбинация ...
000или ...
0000,они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0
или 00
(до признака конца знака).
Длительность передачи каждого отдельного кода 4 очевидно, может быть найдена: ti
= ki
• τ, где ki
- количество элементарных сигналов (бит) в коде символа L
.
Алфавитное неравномерное двоичное кодирование. Префиксный код
Рассмотрев один из вариантов двоичного неравномерного кодирования, попробуем найти ответы на следующие вопросы: возможно ли такое кодирование без использования разделителя знаков? Существует ли наиболее оптимальный способ неравномерного двоичного кодирования?
Суть первой проблемы состоит в нахождении такого варианта кодирования сообщения, при котором последующее выделение из него каждого отдельного знака (т.е. декодирование) оказывается однозначным без специальных указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды,
которые удовлетворяют следующему условию (условию Фано):
ииииииииииии
Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом какого-либо иного более длинного кода.
Например, если имеется код ПО, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой.
Пример: Пусть имеется следующая таблица префиксных кодов:
| а | л | м | р | у | ы |
| 10 | 010 | 00 | 11 | 0110 | 0111 |
Требуется декодировать сообщение: 00100010000111010101110000110. Декодирование производится циклическим повторением следующих действий:
1. отрезать от текущего сообщения крайний левый символ, присоединить к рабочему кодовому слову;
2. сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (1);
3. декодировать рабочее кодовое слово, очистить его;
4. проверить, имеются ли еще знаки в сообщении; если «да», перейти к (1).
Применение данного алгоритма дает:
| Шаг | Рабочее слово | Текущее сообщение | Распознанный знак | Декодированное сообщение |
| 0 | пусто | 00100010000111010101110000110 | - | -
|
| 1 | 0 | 0100010000111010101110000110 | нет | - |
| 2 | 00 | 100010000111010101110000110 | м | М |
| 3 | 1 | 00010000111010101110000110 | нет | М |
| 4 | 10 | 0010000111010101110000110 | а | МА |
| 5 | 0 | 010000111010101110000110 | нет | МА |
| 6 | 00 | 10000111010101110000110 | м | Мам |
| • • •
|
Доведя процедуру до конца, получим сообщение: «мама мыла раму».
Код Хаффмана
Способ оптимального префиксного двоичного кодирования был предложен Д.Хаффманом. Построение кодов Хаффмана мы рассмотрим на следующем примере: пусть имеется первичный алфавит А, состоящий из шести знаков a1
…а6
с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Создадим новый вспомогательный алфавит Аb
объединив два знака с наименьшими вероятностями (а5
и а6
) и заменив их одним знаком (например, а(1)
); вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что число таких
шагов будет равно N - 2, где N - число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей. Всю процедуру построения представим в виде таблицы:
Теперь в обратном направлении поведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой - роли не играет; условимся, что верхний знак будет иметь код 0, а нижний - 1). В нашем примере знак а1
(4)
алфавита А(4)
, имеющий вероятность 0,6 , получит код 0, а а2
(4)
с вероятностью 0,4 - код 1. В алфавите A(3)
знак а1
(3)
с вероятностью 0,4 сохранит свой код (1); коды знаков a2
(3)
и a3
(3)
, объединенных знаком a1
(4)
с вероятностью 0,6 , будут уже двузначным: их первой цифрой станет код связанного с ними знака (т.е. 0), а вторая цифра -как условились - у верхнего 0, у нижнего - 1; таким образом, а2
(3)
будет иметь код 00, aa3
(3)
- код 01. Полностью процедура кодирования
представлена в следующей таблице:
Из самой процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода при этом оказывается: К(2)
= 0,3-2+0,2-2+0,2-2+0,15-3+0,1-4+0,05-4 = 2,45
Для сравнения можно найти I1
{
A
)
-она оказывается равной 2,409. что соответствует избыточности кода Q = 0,0169, т.е. менее 2%.
Код Хаффмана важен в теоретическом отношении, поскольку он является самым экономичным из всех возможных, т.е. ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана. Можно заключить, что существует метод построения оптимального неравномерного алфавитного кода. Метод Хаффмана и его модификация - метод адаптивного кодирования (динамическое кодирование Хаффмана) - нашли применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.
Равномерное алфавитное двоичное кодирование. Байтовый код
В этом случае двоичный код первичного алфавита строится цепочками равной длины, т.е. со всеми знаками связано одинаковое количество информации равное 10
. Передавать признак конца знака не требуется, поэтому для определения длины кодовой цепочки можно воспользоваться формулой: К(2)
> log2
N. Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует). Правда, при этом недопустимы сбои, например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи или иными способами. С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи, поскольку факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.
Пример:
| Символ | Код |
| А | 00000001 |
| Б | 00000010 |
| В | 00000011 |
| Г | 00000100 |
| Д | 00000101 |
| Е | 00000110 |
| Ё | 00000111 |
| Ж | 00001000 |
ЗАКЛЮЧЕНИЕ
В кокой системе счисления лучше записывать числа - это вопрос удобства и традиций. С технической точки зрения, в ЭВМ удобно использовать двоичную систему, так как в ней для записи числа используется всего две цифры 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 с.