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

При переводе правильной дроби —

1)Отделяют дробную часть от целой части

2)Каждую цифру др. части умножают последовательно на основание новой системы сч.

3)Результат записывают второй строкой под существующими разрядами переводимого числа.

4)Цифры, стоящие справа от верт. Черты, вновь перемножают на основанеи новой системы. Результат записывают в 3 строку.

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

6)Рез-т получается считыванием сверху вниз цифр, стоящих слева от верт. черты

Второй способ - N=Anq^(n-1) + A(n-1)q^(n-2)... + a0 + a(-1)q^(-1)+a(-2)q^(-2)

Способ перевода триадами — 732 → 111, 011, 010

Арифметические основы работы ЭВМ. Равномерные простые цифровые коды.

Представление чисел в ЭВМ — естественное и с плавающей точкой. Все ар. Орерации в ЭВМ сводятся к сложению и сдвигу. Это позволяет реализовать 4 ар. Действия в одном АЛУ.

При выполнении ар. Операций в ЭВМ используются прямой, обратный, дополнительный и модифицированный коды.

Прямой код — само двоичное число, при этом знаковый разряд равен 0 если число (+) и 1 если (-)

Обратный код — для (+) совпадает с прямым. Для (-) производится инверсия разрядов.

Доп. Код - (+) числа совп. С прямым кодом. У отриц. - добавл. 1 к младшему разряду в обр. коде.

Модифицированный — есть знаковый разряд.

Пример +3 и -3 (0.11).... (дописать для всех кодов)

Арифм. Операции с двоичными числами

Сложение. 1)Условится в количестве разрядов, определить, какое кол-во разрядов потребуется. Для этого — а)Определить кол-во разрядов для наибольшего числа. б)Опр. Кол. Разрядов для представления результата. В числа, учавст. В действии, представить этим кол-вом разрядов.

2)Перевести отрицательное число в доп. Код (пример! )

3)Сложить столбиком

4)Анализ знаковых разрядов и определение знака результата.

Умножение 1)Выбрать знаковый разряд результата и забыть о нём

2)Умножение столбиком 3)Перевод

Деление — аналогично умножению, но делить столбиком двоичные числа.

Представление данных в ЭВМ

Представление чисел в ЭВМ — естественное и с плавающей точкой. Все ар. Орерации в ЭВМ сводятся к сложению и сдвигу. Это позволяет реализовать 4 ар. Действия в одном АЛУ.

(… #13)

 

Выполнение операций двоичной арифметики. Операции с фикс. Точкой.

Операция блядосложения реализуется в мод. Коде. Алгоритм сложения:

1)Если знак слагаемого положителен, то слагаемое вступает в опер. В прямом коде. Если знак (-), то в доп. Мод. Коде.

2)Производится сложение кодов слагаемых по всем разрядам, включая знаковые

3)Если значение знак. Разрядов суммы 00, то сумма (+) и предст. В прямом коде. Если знак.разряд (-), то сумма отриц. И представляется в доп. Коде. В этом случае осущ. Обратное преобразование в прямой код.

4)Если значение знак. Разрядов 01 или 10, то сумма переполняет разрядную сетку.

Умножение с помощью регистров: В регистр Р1 записываем множитель, в Р2 множимое. В Р3 будут зап. Как окончательные, так и промежут. Результаты в соотв. Со следующим алгоритмом:

1)Сначала в результат все нули

2)Анализируем первую цифру множителя. Если она =1, то производим суммирование Р3 с Р2.

3)Двигаем регистр Р3 на 1 разряд вправо.

4)Переходим к сле. Цифре и п2.

Деление с помощю регистров -

1)Опр. Знаковый разряд — 11

2)Берём 8+2 ячейки. В регистре Р1 записываем делимое как (+) число. В Р2 записываем делитель.

3)Нормализуем делитель. (двигаем в лево и троллим до совпадения старших разрядов). Опр. Количество сдвигов и старших разрядов.

4)Выписываем доп. Код делителя (нормализованный). Если получили (-) число, то в регистр результата записываем 0, иначе 1.

5)Двигаем полученный результат на 1 разряд влево.

Выполнение операций двоичной арифметики. Операции с плав. Точкой.

Алгоритм сложения чисел с плав. Точкой:

1)Перевести в 2-й код

2)Сравнить порядки. Если Pa-Pb > k то сумма приравнивается равной числу с большим порядком.

3)Если порядки не равны, производится уравнивание порядков слагаемых путём приведения числа с меньшим порядком с числа большим порядком.

4)Мантиссы, полученные после уравнивания порядков, складываются как двоичные числа с фик. Запятой.

5)Сумма нормализуется. Если значение мантиссы = 0, то нормализация не возможна.

Произведение и деление чисел с плав. Точкой-

Значение мантиссы произведения определятеся умнож. Чисел с фикс. Порядки складываются.

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

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

Количество 1 в к.к. Называют весом кода. Степень отличия к.к. Называют кодовым расстоянием (d). Кодовое расстояние называет количество ошибок.

Существует несколько способов наглядного представления кодового ансамбля — код. Таблица и кодовое дерево.

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

Dmin > = количество обнар. Ошибок (t) + Количество испр. ошибок + 1

Dmin = 1 — безизбыточный кодирование

Dmin =2 — ошибка обнаружена

2 ошибки приводят к трансформации кода

Принципы помехоустойчивого кодирования:

1)Основан на том, что не все к.к., входящие в состав кодового ансамбля, счит. Разрешёнными. В этом случае при приёме какой-либо комбинации из числа запрещённых делается вывод о наличии ошибки.

2)Основан на введении избыточности в к.к. Без изб. Кода. Добавление одного или нескольких разрядов, наз. Проверочными.

Построение кода с заданной корректирующей способностью

По заданному количеству сообщений, которые необходимо передать, определяем число инф. Разрядов. K=log 2 N

По заданному числу ошибок Е, которые необх. Исправить, определяем длинну кода n. Используем для этого формулу N < = 2^n / (1+E)

Пример реацлизации алгоритма — код с проверкой на общую чётность, с удвоением элементов.

Принцип построения систематических кодов

Для всех с.к. Характерна след. Особенность — сумма по модулю 2 двух разрешённых кк даёт также разрешённую кк.

Исходные кодовые комбинации должны уд. Следующим условиям — 1)В число исходных к.к. Не должна входить нулевая 2)Кодовое расстояние между любыми парами исх. к.к. Не должно быть меньше дмин.

3)Каждая исх. Комбинация должна содержать количество 1 не меньше дмин.

4)Все исходные кодовые комбинации должны быть линейно независимыми.

Код Хэмминга

Код Хэмминга строится таким образом, чтобы в результате q=n-k проверок получить q разрядное двоичное число указывающее номер искаженной позиции кодовой комбинации. Для этого проверочные символы должны находиться на номерах позиций равных степеням двойки(1, 2, 4, 8…). Проверочная матрица Н кода Хэмминга строится следующим образом: по вычисленной длине кода Н записываем в столбцы матрицы Н двоичные q разрядные числа от 1 до n.

Код Хэмминга обеспечивает исправление всех однократных ошибок.

dmin=3

Количество информации и энтеропия

Численная мера количества информации должна соответствовать след. условиям:

1. Кол-во информации в сообщении пропорционально длине сообщения.
2. Кол-во информации равно нулю, если в системе возможно только 1 сообщение.

Т.к. система событий конечная и полная, то сумма вероятностей начала событий – есть единица. Поэтому для удобства за единицу информации берут такое кол-во, которое исключает неопределенность относительно появления одной из двух возможных вероятных независимых событий. Такая единица кол-ва информации наз. «двоичной единицей информации» или бит

Таким обр. мера кол-ва инф., которая есть в сообщении: I=logpi где pi – вероятность появления сообщения

Энтропия – среднее кол-во инф. на 1сообщение. Энтропия показывает степень разнообразия возможных состояний системы.

Оперативные структуры данных. Статические структуры.

Оперативными наз. Структуры данных, хран. В оперативной памяти ЭВМ.

Стуктурой данных наз. Совокупность элементов данных и отношений между ними.

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

Массив — это вектор, каждый элемент которого также вектор.

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

Полу статические структуры

Список — это линейно-упорядоченная последовательность элементов. Каждый элемент хар-ся одним и тем же набором полей. Такой список наз. Линейным. Могут быть односвязные и двусвязные списки.

Стек (магазин, очередь) — работает по принципу LIFO.

Основные операции со стеком- 1)Включение элемента 2)чтение элемента

Дек — это очередь с двумя концами.

Динамические структуры

Динамические структуры данных– это структуры данных, память под которые выделяется и освобождается по мере необходимости.

n=var (количество элементов не ограничено)

Односвязные списки — отличаются наличием однозначного соответствия между пред. И послед. Элементом списка.

 

⇐ Предыдущая12

Поделиться: