Учебное пособие по информатике 2014. Основы информатики
 Скачать 4.61 Mb.
|
|
Проверка Проверяемые разряды 1... 1,3,5,7,9,11,13,15... 2... 2,3,6,7, 10, 11, 14, 15, 18, 19,22,23... 3... 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23... 4... 8,9,10,11,12,13,14,15,24... Теперь нужно решить, какие из позиций целесообразнее применить для передачи информации, а какие — для ее контроля. Преимущество использования позиций 1, 2, 4, 8, ... для контроля в том, что данные позиции встречаются только в одной проверяемой группе символов. В таблице 3.13 представлены примеры кодирования информации по методу Хэмминга для семиразрядного кода. Как видно из таблицы 3.13, в этом случае n=7, m=4, k=3 и контрольными будут разряды 1, 2, 4. 94 Таблица 3.13 – Кодирование информации по методу Хэмминга для семиразрядного кода Разряды двоичного кода Кодируемая десятичная информация 1 k 1 2 k 2 3 m 1 4 k 3 5 m 2 6 m 3 7 m 4 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 2 1 0 0 0 0 1 1 3 1 0 0 1 1 0 0 4 0 1 0 0 1 0 1 5 1 1 0 0 1 1 0 6 0 0 0 1 1 1 1 7 1 1 1 0 0 0 0 8 0 0 1 1 0 0 1 9 1 0 1 1 0 1 0 10 0 1 1 0 0 1 1 11 0 1 1 1 1 0 0 12 1 0 1 0 1 0 1 13 0 0 1 0 1 1 0 14 1 1 1 1 1 1 1 15 По методу Хэмминга могут быть построены коды разной длины, этом чем больше длина кода, тем меньше относительная избыточность. Например, для контроля числа, имеющего 48 двоичных разрядов, потребуется только шесть дополнительных (избыточных) разрядов. Коды Хэмминга используют в основном для контроля передачи информации по каналам связи, что имеет место в вычислительных системах с телеобработкой данных или в системах коллективного пользования. 3.4 Системы счисления Системой счисления называется совокупность приемов наименования и записи чисел. В любой системе счисления для представления чисел выбираются некоторые символы (слова или знаки), называемые базисными числами, а все остальные числа получаются в результате каких-либо операций из базисных чисел данной системы исчисления. Символы, используемые для записи чисел, могут быть любыми, только они должны быть разными и значение каждого из них должно быть известно. В современном мире наиболее распространенным является представление чисел посредством арабских цифр 0, 1,2, 3, 4, 5, 6, 7, 8, 9 - специальных знаков, используемых для записи чисел. Системы счисления различаются выбором базисных чисел и правилами образования из них остальных чисел. Например, в римской системе счисления базисными являются числа 1, 5, 10, 50, 100, 500, 1000, которые обозначаются знаками I, V, X, L, С, D, М, а другие получаются путем сложения и вычитания базисных: если цифра справа меньше или равна цифре слева, то эти цифры складываются; если цифра слева меньше, чем цифра справа, то левая цифра вычитается из правой. Так, например, число 146 в римской системе счисления имеет вид CXLVI (С-100, XL-40, VI-6), 95 здесь «сорок» получается посредством вычитания из «пятидесяти» числа «десять», «шесть» - посредством сложения «пяти» и «единицы». Системы счисления, в которых любое число получается путем сложения или вычитания базисных чисел, называются аддитивными. При таком представлении чисел правила сложения для небольших чисел очевидны и просты, однако если возникает необходимость выполнять операции сложения над большими числами или операции умножения и деления, то «римская» система счисления оказывается неудобной. В этой ситуации преимущественнее оказываются позиционные системы счисления. Хотя в них, как правило, представления чисел далеко не так просты и очевидны, как в «римской» системе счисления, систематичность представления, основанная на «позиционном весе» цифр, обеспечивает простоту выполнения операций умножения и деления. В «римской» системе счисления каждый числовой знак в записи любого числа имеет одно и то же значение, т.е. значение числового знака не зависит от его расположения в записи числа. Таким образом, «римская» система счисления не является позиционной системой счисления. Для изображения (или представления) чисел в настоящее время используются в основном позиционные системы счисления. Привычной для всех является десятичная система счисления. В этой системе для записи любых чисел используется только десять разных знаков (цифр): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Эти цифры введены для обозначения первых десяти последовательных чисел, а следующее число 10 и т.д. обозначается уже без использования новых цифр. Однако введением этого обозначения сделан важный шаг в построении системы счисления: значение каждой цифры поставлено в зависимость от того места, где она стоит в изображении числа. Таким образом, система называется позиционной, если значение каждой цифры (ее вес) изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Десятичная позиционная система счисления основана на том, что десять единиц каждого разряда объединяются в одну единицу соседнего старшего разряда. Таким образом, каждый разряд имеет вес, равный степени 10. Например, в записи числа 343,32 цифра 3 повторена три раза, при этом самая левая цифра 3 означает количество сотен (ее вес равен 10 2 ); цифра 3, стоящая перед точкой, означает количество единиц (ее вес равен 10 0 ), а самая правая цифра 3 - количество десятых долей единицы (ее вес равен 10 -1 ), так что последовательность цифр 343,32 представляет собой сокращенную запись выражения: 3 10 2 +4 10 1 +3 10 0 +3 10 -1 +2 10 -2 Десятичная запись любого числа X в виде последовательности цифр: a n a n-1 …a 1 a 0 a -1 …a -m … (3.8) основана на представлении этого числа в виде полинома: X = a n 10 n + a n-1 10 n-1 +…+ a 1 10 1 + a 0 10 0 + a -1 10 -1 +…+ a -m 10 -m …, (3.9) где каждый коэффициент а i может быть одним из чисел, для обозначения 96 которых введены специальные знаки. Запись числа X в виде (3.9) представляет собой просто перечисление всех коэффициентов этого полинома. Точка или запятая, отделяющая целую часть числа от дробной, служит для фиксации конкретных значений каждой позиции в этой последовательности цифр и является началом отсчета. Число К единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления, а сама система счисления называется К-ичной. Например, основанием десятичной системы счисления является число 10; двоичной - число 2; троичной - число 3 и т.д. Для записи произвольного числа в K-ичной системе счисления достаточно иметь К разных цифр а i , i=1,...,К. Эти цифры служат для обозначения некоторых различных целых чисел, называемых базисными. Числа можно записать как суммы степеней не только числа 10, но и любого другого натурального числа, большего 1. Например, в Древнем Вавилоне использовалась система счисления с основанием 60. Деление часа на 60 минут, а минуты на 60 секунд заимствовано именно из этой системы счисления. А то, что человечество выбрало в качестве основания системы счисления число 10, вероятно, связано с тем, что природа наделила людей десятью пальцами. Запись произвольного числа X в K-ичной позиционной системе счисления основывается на представлении этого числа в виде полинома: K=a n K n + a n-1 K n-1 +…+ a 1 K 1 + a 0 K 0 + a -1 K -1 +…+ a -m K -m +…, (3.10) где каждый коэффициент а может быть одним из базисных чисел и изображается одной цифрой. Как и в десятичной системе счисления, число X, представленное в К-ичной системе счисления, можно кратко записать в виде (3.8) путем перечисления всех коэффициентов полинома (3.10) с указанием позиционной точки. Последовательность цифр, стоящая в (3.8), является изображением числа X в К-ичной системе счисления. Базисные числа должны быть выбраны так, чтобы любое число X могло быть представлено в виде полинома (3.10). Обычно в качестве базисных чисел берутся последовательные целые числа от 0 до К-1 включительно. Все известные позиционные системы счисления являются аддитивно- мультипликативными. Особенно отчетливо аддитивно-мультипликативный способ образования чисел из базисных выражен в числительных русского языка, например пятьсот шестьдесят восемь (т.е. пять сотен плюс шесть десятков плюс восемь). Арифметические действия над числами в любой позиционной системе счисления производятся по тем же правилам, что и в десятичной системе, так как все они основываются на правилах выполнения действий над соответствующими полиномами. При этом нужно только пользоваться теми таблицами сложения и умножения, которые имеют место при данном основании К системы счисления. Отметим, что во всех позиционных системах счисления с любым основанием К умножения на числа вида К m , где m - целое число, сводится просто к перенесению запятой у множимого на m разрядов вправо или влево 97 (в зависимости от знака m), так же как и в десятичной системе. Для указания того, в какой системе счисления записано число, условимся при его изображении основание системы счисления указывать в виде нижнего индекса при нем, например, 35.64 8 В современной вычислительной технике в устройствах автоматики и связи широко используется двоичная система счисления. Это система счисления с наименьшим возможным основанием. В ней для изображения числа используются только две цифры: 0 и 1. Произвольное число X в двоичной системе представляется в виде полинома: X = a n 2 n + a n-1 2 n-1 +…+ a 1 2 1 + a 0 2 0 + a -1 2 -1 +…+ a -m 2 -m …, (3.11) где каждый коэффициент а i может быть либо 0, либо 1. Так как в двоичной системе счисления для изображения любых чисел используются только две различные цифры, то при построении ЭВМ можно использовать элементы, которые могут находиться только в двух состояниях (например, высокое или низкое напряжение в цепи, наличие или отсутствие электрического импульса и т.п.). Это обстоятельство, а также простота выполнения арифметических операций являются причиной того, что большинство современных ЭВМ используют двоичную систему счисления. Неудобство использования двоичной системы счисления заключается в громоздкости записи чисел. Это неудобство не имеет существенного значения для ЭВМ. Однако если возникает необходимость кодировать информацию «вручную», например, при составлении программы на машинном языке, то предпочтительнее оказывается пользоваться восьмеричной или шестнадцатеричной системой счисления (в силу их свойств, которые будут отмечены позднее). В восьмеричной системе счисления базисными числами являются 0, 1, 2, 3, 4, 5, 6, 7. Запись любого числа в этой системе основывается на его разложении по степеням числа восемь с коэффициентами, являющимися указанными выше базисными числами. Например, десятичное число 83.5 в восьмеричной системе будет изображаться в виде 123.4 8 . Действительно, эта запись по определению означает представление числа в виде полинома: 1х8 2 +2х8 1 +3х8 0 +4х8 -1 = 64 + 16 + 3 + 4/8 = 83.5. В шестнадцатеричной системе счисления базисными являются числа от нуля до пятнадцати. Эта система отличается от рассмотренных ранее тем, что в ней общепринятых (арабских) цифр не хватает для обозначения всех базисных чисел, поэтому приходится вводить в употребление новые символы. Обычно для обозначения первых десяти целых чисел от нуля до девяти используют арабские цифры, а для следующих целых чисел от десяти до пятнадцати используются буквенные обозначения A, B, C, D, E, F. Например, десятичное число 175.5 в шестнадцатеричной системе будет записываться в виде AF.8. 98 Смешанные системы счисления В ряде случаев числа, заданные в системе счисления с основанием Р, приходится изображать с помощью цифр другой системы счисления с основанием Q, где Q<P. Такая ситуация возникает, например, когда в ЭВМ, способной непосредственно воспринимать только двоичные числа, необходимо изобразить десятичные числа, с которыми мы привыкли работать. В этих случаях используются смешанные системы счисления, в которых каждый коэффициент Р-ичного разложения числа записывается в Q- ичной системе. В такой системе Р называется старшим основанием, a Q - младшим основанием, а сама смешанная система называется (Q - Р)-ичной. Для того чтобы запись числа в смешанной системе счисления была однозначной, для представления любой Р-ичной цифры отводится одно и то же количество Q-ичных разрядов, достаточное для представления любого базисного числа Р-ичной системы. Так, в смешанной двоично-десятичной системе счисления для изображения каждой десятичной цифры отводится четыре двоичных разряда. Например, десятичное число х = 925 в двоично- десятичной системе запишется в виде 1001 0010 0101. Здесь последовательные четверки (тетрады) двоичных разрядов изображают цифры 9, 2, 5 записи числа в десятичной системе счисления. Следует обратить внимание, что хотя в двоично-десятичной записи числа и используются только цифры 0 и 1, эта запись отличается от двоичного изображения данного числа. Например, приведенный выше двоичный код в двоичной системе счисления изображает число 2341, а не число 925. Условимся изображать принадлежность числа к (Q - Р)-ичной системе счисления с помощью нижнего индекса (Q - Р) при данном числе, например: 925 10 = 100100100101 2-10 Аналогично рассмотренной выше двоично-десятичной системе можно использовать и другие смешанные системы при различных значениях Р и Q. Особого внимания заслуживает случай, когда Р = Q z , где z - целое положительное число. В этом случае запись какого-либо числа в смешанной системе тождественно совпадает с изображением этого числа в системе счисления с основанием Q (что не имеет места в двоично-десятичной системе в общем случае ). Докажем это утверждение. Рассмотрим произвольное целое число N. В Р-ичной системе счисления это число будет записано в виде p n p n-1 …p 1 p 0 , основанном на представлении N=p n p n +p n-1 p n-1 +…+p 1 p 1 +p 0 , (3.12) где p i , i = 0, 1, .... n являются базисными числами этой системы. Каждый коэффициент p i будет записываться в Q-ичной системе счисления в виде p i = q i,z-1 q i,z-2 … q i,z q i,0 основанном на представлении p i = q i , z-1 Q z-1 + q i , z-2 Q z-2 +… + q i , 1 Q 1 + q i , 0 , (3.13) 99 где q i,j - базисные числа системы счисления с основанием Q. Тогда в смешанной системе счисления число N будет записываться в виде N = q n,z-1 q n,z-2 … q n,0 q n-1,z-1 … q n-1,0 …q 0,z-1 … q 0,0 Подставляя (3.13) в (3.12) и учитывая соотношение Р = Q z , получим N = q n , z-1 Q nz+z-1 + q n , z-2 Q nz+z-2 +…+ q n , 0 Q nz + q n-1 , z-1 Q nz-1 + q n-1 , 0 Q nz-1 +…+ +q 0 , z-1 Q nz-1 +…+ q 0 , z-1 Q z-1 +…+ q 0 , 0 Q 0 (3.14) т.е. разложение числа N по степеням Q. Поэтому запись числа N в Q-ичной системе счисления, соответствующая разложению (3.14), будет иметь вид N = q n,z-1 q n,z-2 … q n,0 q n-1,z-1 … q n-1,0 …q 0,z-1 … q 0,0 . Как видно, эта запись тождественно совпадает с приведенной выше записью числа N в смешанной системе счисления, где каждая очередная группа из z цифр является просто изображением соответствующего коэффициента p i , в системе счисления с основанием Q. Все сказанное выше относительно целых чисел автоматически переносится и на случай произвольных чисел. Таким образом, изображение числа x в Р-ичной системе счисления в случае Р = Q z является просто сокращенной записью изображения этого же числа х в Q-ичной системе. Рассмотренное выше свойство некоторых смешанных систем широко используется на практике для сокращенной записи чисел, заданных в системе счисления с небольшим основанием. Для этого в исходной записи числа разряды объединяются вправо и влево от точки в группы некоторой длины (добавляя в случае необходимости левее старшей или правее младшей значащих цифр соответствующее количество нулей), и каждая такая группа записывается одной цифрой другой системы, основание которой равно соответствующей степени исходного основания. |