Курсовая работа: Системы счисления и основы двоичных кодировок

В системах с основанием ρ > 10 для чисел, больших или равных 10, не вводят специальных символов, а используют десятичную запись этих чисел, заключая эту запись в скобки. Например, в четырнадцатеричной системе имеется четырнадцать цифр: 0, 1, 2, 3 ... 9, (10), (11), (12), (13).

В системе счисления с основанием ρ, так же как и в десятичной системе счисления, место, занимаемое цифрой, считая, справа налево, называется разрядом.

Число N= а_n ρⁿ + . . . +a₁ ρ +а₀ содержит а₀ единиц первого разряда, а₁ единиц второго разряда, а₂ единиц третьего разряда и так далее. Единица следующего разряда в ρ раз больше единицы предыдущего разряда.

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

Теорема. Любое натуральное число N может быть записано в системе с основание ρ и притом единственным образом.

Доказательство:

1. Докажем существование представления любого натурального числа в виде

N=a_n ρ_n +a_{n -1} ρ_{n -1} + ... +аρ+а₀ (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 ρⁿ + . . . +a₁ ρ +а₀ (3)

где 1≤а_n ≤ρ -1, 0≤ a_i ≤ρ -l, (i=0,1,..,n-1)

Подставим выражения (2) и (3), получим:

k+l= (a_n ρ+ ... +а_i ρ +а₀ ) ρ + г = а_n ρ +... + a_i ρ +a₀ ρ +г (4)

где 1 ≤a_n ≤ρ -1, 0≤a_j ≤ ρ -1, 0 ≤ г ≤ ρ -1 0=0,1,. . ,n-1)

Это выражение (4) дает представление числа к+1 в виде (1):

К+1=b_{n +1} ρ ^{n +1} + b_n ρ _n + ... + b₁ ρ +b₀

где b₀ =r, b_i+1 - a_i (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 -1} ρ ^{n -1} + ....+ а₁ ρ +а₍₎ (6)