Концепция организации сетей

Граничные соотношения между параметрами корректирующих кодов.

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

Рассмотрим граничные оценки, связывающие dmin, n и k. Пусть код предназначен для исправления ошибок кратности t, тогда в каждой из 2k защитных зон должно находится

 t

 S Сni разрешенных комбинаций, а число различных комбинаций 

 i=0

 t t

 должно быть 2n, т.е. 2n ³ 2k S Сni или nk ³ log2 S Сni.

 i=0 i=0

Такое соотношение называется границей Хемминга. Для qичного кода граница Хемминга имеет вид

 t t

S Сni (q1) £ qn(k1) = r ³ logq S Cni (q1)i.

 i=0 i=0

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

 dmin £ (q1)nqk1 / (qk 1), а для двоичного кода

2k(n 2dmin) £ 2dmin или dmin ³ 2k 1 (n2dmin).

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

Пусть в сферу с радиусом 2t, проведенную вокруг любой разрешенной комбинации, не попадает никакая другая разрешенная комбинация, тогда этот код способен исправить все ошибки кратности не менее t. Число разрешенных комбинаций определяется соотношением

 2t 2t

2k ³ 2n S Cni или n k £ log2 S Cni.

 i=0 i=0

Такое соотношение носит название границы ВаршамoваГилберта. Для qичного кода граница имеет вид

 t d2

n k  logq  Cni (q1)i = r = logq  Cni (q1)i,

 i=0 i=0

где d = 2t + 1; dmin / n dmin ³ 2k1.

Граница ВаршамоваГилберта показывает при каком значении nk определенно существует код, гарантийно исправляющий ошибки кратности t.

Зависимость скорости передачи кода от dmin для различных граничных оценок представлена на рис. 19.10.

Общие сведения об архитектуре компьютера.

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

Шину данных, состоящую из линий данных и служащую для передачи информации между процессором и памятью, процессором и устройствами ввода-вывода, памятью и внешними устройствами.

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

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


Беспроводные сети