1. Алгоритми генерації рівномірно розподілених псевдовипадкових чисел

Для генерації рівномірно розподілених псевдовипадкових чисел можна застосовувати найпростіший алгоритм, оснований на наступному рекуррертному співвідношенні:

I(n+1)=(a*I(n)+c)(mod m)

де число a називається мультиплікатором;

число c – інкрементом;

число m - модулем

Приклад генератора рівномірно розподілених псевдовипадкових чисел

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading;

namespace RandomGenerator

{

class Program

{

static int next = 1;

static int GetRand() {

next = next * 1103515245 + 12345;

return((int)(next/65536)%32768);

}

static void Main(string[] args)

{

for (int i = 0; i < 10; i++)

{

int Rand = Math.Abs(GetRand() % 100);

Console.WriteLine(Rand);

}

Console.ReadKey();

}

}

}

Генератор рівномірно розподілених випадкових чисел на основі алгоритму Парка-Міллера

2. Перевірка якості випадкових чисел

Якість випадкових чисел визначається їх відповідністю певному закону розподілу

Для перевірки якості необхідно обрати статистичний крітерій (Пірсона, Ст’юдента та ін. ) і перевірити гіпотезу про відповідність розподілу

Крім того, для генератора псевдовипадкових випадкових чисел важливо запобігти взлому, тобто підбору такого алгоритму, який би дозволив зпрогнозувати значення наступних чисел за значеннями попередніх

Для перевірки якості можна застосовувати спеціальне програмне забезпечення, наприклад вільно доступний пакет Національного інституту стандартів і технології США : http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

3. Кодування з виправленням помилок

В процесі передавання каналами зв’язку чи зберігання на носіях даних інформація може бути пошкоджена

Для виявлення пошкодження інформації, а також її відновлення використовуються спеціальні методи кодування

Найпростіша схема кодування для виявлення помилок полягає у наступному:

сторона, що передає дані, використовує певний алгоритм для розрахунку контрольної суми даних, яка передається разом із самими даними;

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

Перевірка парності/непарності

Найпростіший алгоритм такого кодування – “перевірка парності”: для кожного переданого байту підраховується сума одиничок, і у окремому біті заноситься “0” чи “1” в залежності від того, відповідно, чи є сума парною, чи ні. Таким чином, сума бітів у байті (разом із додатковим бітом) завжди є парною (чи непарною, якщо використовується перевірка непарності).

Поблокова перевірка парності/непарності

Алгоритм CRC

Алгоритм CRC (Cyclic Redundancy Check) є одним з найпоширеніших алгоритмів контролю цілісності даних.

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

Незначні зміни даних, як правило, приводять до суттєвих змін залишку, у такому разі алгоритм дозволяє дуже ефективно виявляти помилки у даних.

Для зручності розрахунку CRC операції проводяться над поліномами, за допомогою яких представляються числа.

Існують стандартизовані поліноми:

Виправлення помилок

Виправлення помилок дещо складніше за їх виявлення

Процедура виправлення помилки передбачає два послідовних процеси: виявлення помилки та визначення місця, де вона відбулася.

Код Хемінга – популярний код виправлення помилок, відноситься до блокових кодів, який дозволяє виявити та виправити помилково переданий біт в межах одного переданого блоку.

Звичайно цей код характеризується двома цілими числами, наприклад (11,7), які означають, що при передачі 7-бітного коду (у минулому стандартне для США ASCII-кодування) передається додатково 4 контрольних біти (11 – 7 = 4).

Приклад використання коду Хемінга

Приклад. Необхідно передати літеру s = 1110011.

Передача буде здійснюватись наступним чином:

(*) – місце для контрольних бітів, ціла ступінь 2 (1,2,4,8)

Контрольна сума визначається як операція XOR над кодами позицій ненульових бітів. У даному разі це 11, 10, 9, 5 та 3.

Розрахунок:

Таким чином, передаватися буде наступний код:

У даному разі контрольна сума за операцією XOR для усіх ненульових

бітів буде рівна нулю:

Приклад використання коду Хемінга (продовж.)

Тепер уявимо, що виникла помилка у біті посилки №7 (1 замість 0), розрахунок контрольної суми дасть наступний результат:

Отримана ненульова контрольна сума свідчить про наявність помилки, а її значення – позицію біта, який необхідно інвертувати:

1112 = 710

Обмеження коду Хемінга

Код може усувати помилку лише у одному біті, якщо відбувається декілька помилок, то використання коду для виправлення неможливе.

Для збільшення діапазону виправлення помилок використовується більш складна загальна форма коду BCH (Bose-Chadhuri-hocquenghem).

Позиційна система корекції помилок

Передбачає блочний розрахунок кодів парності у декількох вимірах.