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

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

СС бывают позиционные и непозиционные.

В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Под позиционной системой счисления обычно понимается b-ричная система счисления, которая определяется целым числом b > 1, называемым основанием системы счисления. Целое число x в b-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа b:

, где a_k — это целые числа, называемые цифрами, удовлетворяющие неравенству .

В непозиционной системе счисления каждая цифра алфавита имеет фиксированное значение. Самая известная непозиционная СС – римская СС. Пример: XXI = 21₁₀

Арифметические и логические операции над двоичными числами

Арифметические:

Сложение: 1000+101=1101

Вычитание: 1101-101=1000

Умножение: a*b алгоритм: Берём левый бит b умножаем на a, результат сдвигаем на один бит влево и т.д.

Арифметический сдвиг – основная идея – старший бит сохраняет своё значение

Логические

Побитовое «И» 11001&10101=10001

Побитовое «ИЛИ» 11001|10101=11101

Побитовое «НЕ» !11001=00110

Побитовое «XOR» 11001 XOR 10101 = 01100

Логический сдвиг: пустая ячейка заполняется нулём

Принципы архитектуры Фон Неймана

• Принцип двоичного кодирования.

Для представления данных и команд используется двоичная система счисления(0,1)

• Принцип однородности памяти.

Как программы (команды), так и относящиеся к программам данные хранятся в одной и той же памяти (и кодируются в одной и той же системе счисления — чаще всего двоичной). Над командами можно выполнять такие же действия, как и над данными.

• Принцип адресуемости памяти.

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

• Принцип последовательного программного управления.

Все команды располагаются в памяти и выполняются последовательно, одна после завершения другой, в последовательности, определяемой программой.

• Принцип жесткости архитектуры.

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

Компьютеры, построенные на этих принципах, относят к типу фон-неймановских.

Гарвардская архитектура

Гарвардская архитектура — архитектура ЭВМ, отличительным признаком которой является раздельное хранение и обработка команд и данных. Архитектура была разработана ГовардомЭйкеном в конце 1930-х годов в Гарвардском университете.

Типичные операции (сложение и умножение) требуют от любого вычислительного устройства нескольких действий:

1. выборку двух операндов,

2. выбор инструкции и её выполнение,

3. и, наконец, сохранение результата.

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

Такой подход применяется в современных сигнальных процессорах. Еще дальше по пути уменьшения стоимости пошли при создании однокристалльных ЭВМ — микроконтроллеров. В них одна шина команд и данных применяется и внутри кристалла.

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

Постоянная память и временная

Постоянное запоминающее устройство (ПЗУ) — энергонезависимая память, используется для хранения массива неизменяемых данных.

Временная память – энергозависимая память. Бывает статической и динамической.

Статическая - память, которой для хранения информации достаточно сохранения питающего напряжения.

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

Алгоритм. Понятие алгоритма

Алгори́тм, от имени учёного аль-Хорезми — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

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

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