коды подразделяются по величине позиционности на двухпозиционные и многопозиционные

Коды подразделяются по величине позиционности на двухпозиционные и многопозиционные

10.3. Многопозиционные сигналы и корректирующие коды

Ансамбль сигналов i(t)> M _i=1 на интервале (0, Т) можно представить в виде

Геометрически каждому сигналу ансамбля соответствует точка (или ректор) в n-мерном пространстве с координатами (a_i1, a_i2. a_in i = 1. М. Энергия сигнала при этом равна квадрату

а расстояние между сигналами

— коэффициент взаимной корреляции рассматриваемых сигналов. В дальнейшем будем рассматривать ансамбли сигналов с одинаковыми энергиями E_i = E_k = E.

Наиболее распространенными многопозиционными сигналами являются ортогональные, биортогональные и симплексные. Если сигнальные точки выбрать на линиях, совпадающих с ортами φ на расстояниях √E от начала координат, то получим систему ортогональных сигналов. Число сигналов в таком ансамбле М = n. Так, если принять

Ортогональные сигналы образуют эквидистантную систему, расстояния между любыми двумя сигнальными точками которой одинаковы и, согласно выражению (10.15), равны d = √2E. Биортогональные сигналы образуются по следующему правилу: к каждому ортогональному сигналу добавляется противоположный. Здесь число сигналов М = 2n. Простейшим из биортогональных

является ансамбль с М = 4. Сигналы имеют одинаковые энергии и находятся на одинаковом расстоянии от начала координат. На (плоскости они образуют квадрат (рис. 10.4). При выборе в качестве базисных функций

Известные сигналы с амплитудно-фазовой модуляцией (АФМ) образуют круговую сеть (см. рис. 10.4): например, три сигнала равномерно распределены по окружности, а четвертый расположен в центре окружности. В том же базисе они могут быть представлены так:

Многопоэиционные сигналы с фазовой модуляцией (ФМ) образуют круговую сеть с равномерным распределением точек по окружности. Построить ансамбли ортогональных и биортогональных многопозиционных сигналов можно и на основе двоичных последовательностей. Для этого обычно используют элементарную матрицу Адамара А, повторением которой трижды в позитивной и один раз в негативной форме можно увеличить размеры матрицы каждый раз вдвое и получить матрицу Б, которая представляет ансамбль ортогональных сигналов с М = 4:

Каждая строка этой матрицы (последовательность двоичных символов) образует один сигнал. Нетрудно проверить, что эти строки (сигналы) взаимноортогональны. Дополняя матрицу Б инверсиями строк, получим матрицу В, представляющую ансамбль М = 8 биортогональных сигналов. Аналогично строятся ансамбли с большим числом сигналов М. Симплексные сигналы также могут быть получены на основе двоичных последовательностей [12].

Рис. 10.4. Примеры ансамблей двумерных сигналов

Помехоустойчивость систем связи в общем случае зависит как от вида передаваемых сигналов, так и от способа приема. При оптимальном приеме реализуется потенциальная помехоустойчивость. Алгоритм оптимального приема М-позиционных сигналов определяется системой неравенств (6.23), а вероятность ошибки вычисляется как вероятность невыполнения этих неравенств.

В § 6.5 получены выражения для вероятности ошибки при М = 2. Для не двоичных систем (М>2) получить такие простые выражения не всегда удается. Для некоторых ансамблей сигналов такие формулы имеются в [8], а для других, путем численного интегрирования, получены графики зависимости p = f(E/N₀) [12, 18], которые ниже используются для вычисления энергетической эффективности р. Для приближенных вычислений при симметричных системах можно воспользоваться верхней оценкой (6.60)

Различают два класса многопозиционных сигналов. Первый образуют «плотные» сигналы, когда с ростом объема ансамбля М при фиксированной размерности n расстояние между сигналами уменьшается, а удельная скорость γ, согласно (10.18) возрастает при соответствующем снижении энергетической эффективности β. В качестве примера таких сигналов на рис. 10.5 приведены кривые для многопозиционных сигналов ФМ и АФМ.

Рис. 10.5. Кривые энергетической и частотной эффективности систем с многопозиционными сигналами и корректирующими кодами

Приведенные на рис. 10.5 βγ-диаграммы позволяют количественно оценить обменный выигрыш (проигрыш) различных систем. Так, например, применение биортогональных сигналов с М = 16 позволяет получить энергетический выигрыш Др = 2,4 дБ в обмен на снижение удельной скорости γ в 2 раза (3 дБ). Обмен энергетической эффективности на частотную можно осуществить с помощью многопозиционных сигналов с ФМ. Однако более эффективными являются АФМ сигналы.

Расчетные кривые на рис. 10.5 показывают, что применение циклического кода в канале с ФМ или сверточного кода в канале с АФМ позволяет получить одновременно выигрыш как по энергетической, так и по частотной эффективности или во всяком случае выигрыш по одному показателю без ухудшения другого. Построение таких высокоэффективных систем (η>0,5) на основе сложных сигнально-кодовых конструкций ведет к неизбежному увеличению сложности системы. Не пропускная способность (предел Шеннона), а сложность является ограничивающим фактором при построении высокоэффективных систем. Задача состоит в том, чтобы построить систему удовлетворяющую высоким показателям эффективности, при минимальной (допустимой) сложности, а следовательно, и стоимости системы.

Источник

Анализ методов обеспечения безошибочности передачи данных в сетях

Методы обеспечения безошибочности передачи данных

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

Метод Вердана

К групповым методам защиты от ошибок можно отнести давно уже используемый в телеграфии способ, известный как принцип Вердана: вся информация (или отдельные кодовые комбинации) передается несколько раз, обычно не четное число раз (минимум три раза). Принимаемая информация запоминается специальным устройством и сравнивается. Суждение о правильности передачи выносится по совпадению большинства из принятой информации методами «два из трех», «три из пяти» и так далее. Например, кодовая комбинация 01101 при трехразовой передаче была частично искажена помехами, поэтому приемник принял следующие комбинации: 10101, 01110, 01001. В результате проверки каждой позиции отдельно правильной считается комбинация 01101.

Метод передачи информации блоками

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

Помехоустойчивое кодирование

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

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

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

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

Основными среди многочисленных характеристик корректирующих кодов являются значность, корректирующая способность, избыточность и оптимальность кода, коэффициент обнаружения и исправления ошибки, простота технической реализации метода и другие. Так, значность кода, или длина кодовой комбинации, включает как информационные элементы m, так и проверочные (контрольные) k. Как правило, значность кода n равна m+k.

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

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

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

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

Большие вычислительные системы (Amdal, IBM, Burroughs, ICL) используют очень сложную методику проверки ошибок при передаче по линиям связи между машинами. В ПЭВМ обычно применяется более простая техника проверки ошибок.

Источник

Классификация кодов, их представление, свойства кодов без избыточности

Под кодированием (в узком смысле или дискретом кодировании) понимают процедуру сопоставления дискретному (или дискретизированному непрерывному) сообщению яД/ = 1, 2, 3,К) определенной последовательности кодовых символов, выбираемых из конечного множества различных (отличающихся друг от друга) элементарных кодовых символов a, (i = 1,2,3,т). Применяя приемлемый способ кодирования, можно в той или иной степени согласовать дискретный источник с каналом связи.

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

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

При помехоустойчивом кодировании чаще всего считают, что избыточность источника на входе кодера р_и = 0. Дш этого имеются следующие основания: во-первых, очень многие дискретные источники (например, информация на выходе многих ЭВМ) обладают малой избыточностью; во-вторых, если избыточность первичных источников существенна, она обычно порождается сложными связями, которые в месте приема затруднительно использовать для повышения верности. Поэтому в таких случаях разумно сначала, но возможности, уменьшить избыточность первичного источника, а затем методами помехоустойчивого кодирования внести в сигнал такую избыточность, которая позволяет достаточно простыми средствами поднять верность. Из сказанного следует, что экономное кодирование вполне может сочетаться с помехоустойчивым.

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

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

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

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

Полагая избыточность источника на входе кодера р_и = О, а m-позиционный код равномерным длиной п, можно написать следующую формулу для избыточности кода:

При кодировании удобно совокупность элементов (букв) источника сообщений а_к представить совокупностью чисел: 0, 1,2, 3, 4,

С другой стороны, любое число М можно записать в заданной системе счисления т (или кодом с заданным основанием т) следующим образом:

В системе счисления число 59 запишется следующим образом:

— в десятичной (код с основанием 10)

— в четверичной (код с основанием 4)

М= 59 = 3-4 2 + 2-4′ + 3-4°

в двоичной (код с основанием 2)

М= 59= 1-2 5 + 1-2 4 + 1*2 3 + 0*2 2 + 1-2‘+ 1-2°.

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

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

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

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

Рассмотрим построение кодового дерева для наиболее простого и распространенного двоичного кода, для чего, начиная с определенной точки («корня»), будем проводить отрезки прямой (ветви), наклоненные влево или вправо, если кодовым символом является соответственно «О» или «1». На рис. 5.4 построено «кодовое дерево» дня двоичного кода из табл. 5.1. На вершинах этого дерева написаны буквы алфавита источника, соответствующие данным кодовым комбинациям. Обратим внимание на то, что здесь каждой букве соответствует своя вершина «кодового дерева», с помощью которого можно однозначно декодировать любую последовательность символов, если только она принята с самого начала. Это справедливо для любого равномерного кода.

Рассмотрим теперь неравномерный двоичный код. Пусть он, например, задан «кодовым деревом». В данном случае некоторым буквам сообщения соответствуют нс вершины, а узловые точки дерева. Но тогда декодирование будет неоднозначным. Действительно, приняв в начале кодовой последовательности символ «О», не знаем, означает ли он букву «Б» или является началом кодовой комбинации, означающей буквы «Д» или «Е». Однако можно построить неравномерные коды, допускающие однозначное декодирование, для чего достаточно, чтобы в кодовом дереве всем буквам источника соответствовали бы только вершины. Тогда ни одна кодовая комбинация не будет являться началом другой, более длительной комбинации.

Равенство имеет место только тогда, когда «буквы» выбираются источником с равными вероятностями и независимо друг от друга. Если считать, что в канале связи нет помех (все символы принимаются безошибочно) и он позволяет передавать н_к символов в секунду, то пропускная способность такого канала

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

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

При р₀ « 1, воспользовавшись формулой бинома Ньютона,

Следовательно, используя примитивный код в канале с помехами, принципиально нельзя обеспечить сколько угодно малую вероятность ошибки, о которой говорится в основной теореме К. Шеннона. Такой код применяется в канале с помехами, если достигаемая вероятность ошибочного приема «буквы» не превышает допустимой для данной системы связи величины.

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

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

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

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

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

Источник

Основы систем счисления

Изучая кодировки, я понял, что недостаточно хорошо понимаю системы счислений. Тем не менее, часто использовал 2-, 8-, 10-, 16-ю системы, переводил одну в другую, но делалось все на “автомате”. Прочитав множество публикаций, я был удивлен отсутствием единой, написанной простым языком, статьи по столь базовому материалу. Именно поэтому решил написать свою, в которой постарался доступно и по порядку изложить основы систем счисления.

Введение

Система счисления — это способ записи (представления) чисел.

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

Системы счисления подразделяются на позиционные и непозиционные, а позиционные, в свою очередь, — на однородные и смешанные.

Непозиционная — самая древняя, в ней каждая цифра числа имеет величину, не зависящую от её позиции (разряда). То есть, если у вас 5 черточек — то число тоже равно 5, поскольку каждой черточке, независимо от её места в строке, соответствует всего 1 один предмет.

Позиционная система — значение каждой цифры зависит от её позиции (разряда) в числе. Например, привычная для нас 10-я система счисления — позиционная. Рассмотрим число 453. Цифра 4 обозначает количество сотен и соответствует числу 400, 5 — кол-во десяток и аналогично значению 50, а 3 — единиц и значению 3. Как видим — чем больше разряд — тем значение выше. Итоговое число можно представить, как сумму 400+50+3=453.

Однородная система — для всех разрядов (позиций) числа набор допустимых символов (цифр) одинаков. В качестве примера возьмем упоминавшуюся ранее 10-ю систему. При записи числа в однородной 10-й системе вы можете использовать в каждом разряде исключительно одну цифру от 0 до 9, таким образом, допускается число 450 (1-й разряд — 0, 2-й — 5, 3-й — 4), а 4F5 — нет, поскольку символ F не входит в набор цифр от 0 до 9.

Смешанная система — в каждом разряде (позиции) числа набор допустимых символов (цифр) может отличаться от наборов других разрядов. Яркий пример — система измерения времени. В разряде секунд и минут возможно 60 различных символов (от «00» до «59»), в разряде часов – 24 разных символа (от «00» до «23»), в разряде суток – 365 и т. д.

Непозиционные системы

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

Единичная система счисления

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

Для удобства, люди стали группировать палочки по 3, 5, 10 штук. При этом, каждой группе соответствовал определенный знак или предмет. Изначально для подсчета использовались пальцы рук, поэтому первые знаки появились для групп из 5 и 10 штук (единиц). Все это позволило создать более удобные системы записи чисел.

Древнеегипетская десятичная система

Почему она называется десятичной? Как писалось выше — люди стали группировать символы. В Египте — выбрали группировку по 10, оставив без изменений цифру “1”. В данном случае, число 10 называется основанием десятичной системы счисления, а каждый символ — представление числа 10 в какой-то степени.

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

Вавилонская шестидесятеричная система

В отличии от египетской, в вавилонской системе использовалось всего 2 символа: “прямой” клин — для обозначения единиц и “лежачий” — для десятков. Чтобы определить значение числа необходимо изображение числа разбить на разряды справа налево. Новый разряд начинается с появления прямого клина после лежачего. В качестве примера возьмем число 32:

Число 60 и все его степени так же обозначаются прямым клином, что и “1”. Поэтому вавилонская система счисления получила название шестидесятеричной.
Все числа от 1 до 59 вавилоняне записывали в десятичной непозиционной системе, а большие значения — в позиционной с основанием 60. Число 92:

Запись числа была неоднозначной, поскольку не существовало цифры обозначающей ноль. Представление числа 92 могло обозначать не только 92=60+32, но и, например, 3632=3600+32. Для определения абсолютного значения числа был введен специальный символ для обозначения пропущенного шестидесятеричного разряда, что соответствует появлению цифры 0 в записи десятичного числа:

Теперь число 3632 следует записывать, как:

Шестидесятеричная вавилонская система — первая система счисления, частично основанная на позиционном принципе. Данная система счисления используется и сегодня, например, при определении времени — час состоит из 60 минут, а минута из 60 секунд.

Римская система

Римская система не сильно отличается от египетской. В ней для обозначения чисел 1, 5, 10, 50, 100, 500 и 1000 используются заглавные латинские буквы I, V, X, L, C, D и M соответственно. Число в римской системе счисления — это набор стоящих подряд цифр.

Позиционные системы счисления

Как упоминалось выше — первые предпосылки к появлению позиционной системы возникли в древнем Вавилоне. В Индии система приняла форму позиционной десятичной нумерации с применением нуля, а у индусов эту систему чисел заимствовали арабы, от которых её переняли европейцы. По каким-то причинам, в Европе за этой системой закрепилось название “арабская”.

Десятичная система счисления

Это одна из самых распространенных систем счисления. Именно её мы используем, когда называем цену товара и произносим номер автобуса. В каждом разряде (позиции) может использоваться только одна цифра из диапазона от 0 до 9. Основанием системы является число 10.

Для примера возьмем число 503. Если бы это число было записано в непозиционной системе, то его значение равнялось 5+0+3 = 8. Но у нас — позиционная система и значит каждую цифру числа необходимо умножить на основание системы, в данном случае число “10”, возведенное в степень, равную номеру разряда. Получается, значение равно 5*10 2 + 0*10 1 + 3*10 0 = 500+0+3 = 503. Чтобы избежать путаницы при одновременной работе с несколькими системами счисления основание указывается в качестве нижнего индекса. Таким образом, 503 = 503₁₀.

Помимо десятичной системы, отдельного внимания заслуживают 2-, 8-, 16-ая системы.

Двоичная система счисления

Эта система, в основном, используется в вычислительной технике. Почему не стали использовать привычную нам 10-ю? Первую вычислительную машину создал Блез Паскаль, использовавший в ней десятичную систему, которая оказалась неудобной в современных электронных машинах, поскольку требовалось производство устройств, способных работать в 10 состояниях, что увеличивало их цену и итоговые размеры машины. Этих недостатков лишены элементы, работающие в 2-ой системе. Тем не менее, рассматриваемая система была создана за долго до изобретения вычислительных машин и уходит “корнями” в цивилизацию Инков, где использовались кипу — сложные верёвочные сплетения и узелки.

Двоичная позиционная система счисления имеет основание 2 и использует для записи числа 2 символа (цифры): 0 и 1. В каждом разряде допустима только одна цифра — либо 0, либо 1.

Примером может служить число 101. Оно аналогично числу 5 в десятичной системе счисления. Для того, чтобы перевести из 2-й в 10-ю необходимо умножить каждую цифру двоичного числа на основание “2”, возведенное в степень, равную разряду. Таким образом, число 101₂ = 1*2 2 + 0*2 1 + 1*2 0 = 4+0+1 = 5₁₀.

Хорошо, для машин 2-я система счисления удобнее, но мы ведь часто видим, используем на компьютере числа в 10-й системе. Как же тогда машина определяет какую цифру вводит пользователь? Как переводит число из одной системы в другую, ведь в её распоряжении всего 2 символа — 0 и 1?

Чтобы компьютер мог работать с двоичными числами (кодами), необходимо чтобы они где-то хранились. Для хранения каждой отдельной цифры применяется триггер, представляющий собой электронную схему. Он может находится в 2-х состояниях, одно из которых соответствует нулю, другое — единице. Для запоминания отдельного числа используется регистр — группа триггеров, число которых соответствует количеству разрядов в двоичном числе. А совокупность регистров — это оперативная память. Число, содержащееся в регистре — машинное слово. Арифметические и логические операции со словами осуществляет арифметико-логическое устройство (АЛУ). Для упрощения доступа к регистрам их нумеруют. Номер называется адресом регистра. Например, если необходимо сложить 2 числа — достаточно указать номера ячеек (регистров), в которых они находятся, а не сами числа. Адреса записываются в 8- и 16-ричной системах (о них будет рассказано ниже), поскольку переход от них к двоичной системе и обратно осуществляется достаточно просто. Для перевода из 2-й в 8-ю число необходимо разбить на группы по 3 разряда справа налево, а для перехода к 16-ой — по 4. Если в крайней левой группе цифр не достает разрядов, то они заполняются слева нулями, которые называются ведущими. В качестве примера возьмем число 101100₂. В восьмеричной — это 101 100 = 54₈, а в шестнадцатеричной — 0010 1100 = 2С₁₆. Отлично, но почему на экране мы видим десятичные числа и буквы? При нажатии на клавишу в компьютер передаётся определённая последовательность электрических импульсов, причём каждому символу соответствует своя последовательность электрических импульсов (нулей и единиц). Программа драйвер клавиатуры и экрана обращается к кодовой таблице символов (например, Unicode, позволяющая закодировать 65536 символов), определяет какому символу соответствует полученный код и отображает его на экране. Таким образом, тексты и числа хранятся в памяти компьютера в двоичном коде, а программным способом преобразуются в изображения на экране.

Восьмеричная система счисления

8-я система счисления, как и двоичная, часто применяется в цифровой технике. Имеет основание 8 и использует для записи числа цифры от 0 до 7.

Шестнадцатеричная система счисления

Шестнадцатеричная система широко используется в современных компьютерах, например при помощи неё указывается цвет: #FFFFFF — белый цвет. Рассматриваемая система имеет основание 16 и использует для записи числа: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B. C, D, E, F, где буквы равны 10, 11, 12, 13, 14, 15 соответственно.

Помимо рассмотренных позиционных систем счисления, существуют и другие, например:
1) Троичная
2) Четверичная
3) Двенадцатеричная

Позиционные системы подразделяются на однородные и смешанные.

Однородные позиционные системы счисления

Определение, данное в начале статьи, достаточно полно описывает однородные системы, поэтому уточнение — излишне.

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

К уже приведенному определению можно добавить теорему: “если P=Q n (P,Q,n – целые положительные числа, при этом P и Q — основания), то запись любого числа в смешанной (P-Q)-ой системе счисления тождественно совпадает с записью этого же числа в системе счисления с основанием Q.”

Смешанными системами счисления также являются, например:
1) Факториальная
2) Фибоначчиева

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

Иногда требуется преобразовать число из одной системы счисления в другую, поэтому рассмотрим способы перевода между различными системами.

Преобразование в десятичную систему счисления

Пример: 101₂ = 1*2 2 + 0*2 1 + 1*2 0 = 4+0+1 = 5₁₀

Преобразование из десятичной системы счисления в другие

Записав все остатки снизу вверх, получаем итоговое число 17. Следовательно, 15₁₀ = 17₈.

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

В качестве примера возьмем число 1001₂: 1001₂ = 001 001 = (0*2 2 + 0*2 1 + 1*2 0 ) (0*2 2 + 0*2 1 + 1*2 0 ) = (0+0+1) (0+0+1) = 11₈

Для перевода в шестнадцатеричную — разбиваем двоичное число на группы по 4 цифры справа налево, затем — аналогично преобразованию из 2-й в 8-ю.

Преобразование из восьмеричной и шестнадцатеричной систем в двоичную

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

Для примера рассмотрим число 45₈: 45 = (100) (101) = 100101₂

Перевод из 16-ой в 2-ю — преобразуем каждый разряд шестнадцатеричного числа в двоичное 4-х разрядное число делением на 2, недостающие крайние разряды заполняем ведущими нулями.

Преобразование дробной части любой системы счисления в десятичную

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

Преобразование дробной части двоичной системы в 8- и 16-ую

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

Пример: 1001,01₂ = 001 001, 010 = (0*2 2 + 0*2 1 + 1*2 0 ) (0*2 2 + 0*2 1 + 1*2 0 ), (0*2 2 + 1*2 1 + 0*2 0 ) = (0+0+1) (0+0+1), (0+2+0) = 11,2₈

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

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

Для примера переведем 10,625₁₀ в двоичную систему:
0,625*2 = 1,25
0,250*2 = 0,5
0,5*2 = 1,0
Записав все остатки сверху вниз, получаем 10,625₁₀ = (1010), (101) = 1010,101₂

Источник