Циклічні коди

Якщо ступінь многочлена досягає розрядності коди, то відбувається «перенесення» в нульовий ступінь при . У шифраторах циклічних код ця операція здійснюється шляхом з'єднання виходу осередку старшого розряду з входом осередку нульового розряду. Складання по модулю 2 будь-яких двох сусідніх комбінацій циклічної коди еквівалентно операції множення многочлена відповідного комбінації першого доданку на многочлен якщо приведення подібних членів здійснюється по модулю 2:

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

Проте мало побудувати циклічний код. Треба уміти виділити з нього можливі помилкові розряди, тобто ввести деякі пізнавачі помилок, які виділяли б помилковий блок зі всіх інших. Оскільки циклічні коди - блокові, то кожен блок повинен мати свій пізнавач. І тут вирішальну роль грають властивості створюючого многочлена . Методика побудови циклічної коди така, що створюючий многочлен бере участь в утворенні кожної кодової комбінації, тому будь-який многочлен циклічної коди ділиться на створюючий без залишку. Але без залишку діляться тільки ті многочлени, які належать даному коду, тобто створюючий многочлен дозволяє вибрати дозволені комбінації зі всіх можливих. Якщо ж при діленні циклічної коди на створюючий многочлен буде отриманий залишок, то означає або в коді відбулася помилка, або це комбінація якогось іншої коди (заборонена комбінація), що для декодуючого пристрою не має принципової різниці. По залишку і виявляється наявність забороненої комбінації, тобто виявляється помилка. Залишки від ділення многочленів є пізнавачами помилок циклічних кодів.

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

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

починаючи|розпочинати| з|із| восьмого, залишки повторюватимуться.

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

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

Рядками створюючої матриці є перші комбінації шуканої коди. Решта комбінацій коди виходить в результаті підсумовування по модулю 2 всіляких поєднань рядків створюючої матриці[13].

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

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

На закінчення пропонуємо ще один метод побудови|шикування| циклічних код. Гідністю|чеснотою| цього методу є|з'являється| виняткова простота схемних реалізації кодуючих і декодуючих пристроїв|устроїв|.

Для отримання|здобуття| комбінацій циклічної коди в цьому випадку досить провести циклічне зрушення|зсув| рядка створюючої матриці і комбінації, що є|з'являється| її дзеркальним відображенням. При побудові|шикуванні| код з|із|,, число комбінацій, що отримуються|одержують| підсумовуванням по модулю 2 всіляких поєднань рядків створюючої матриці, дорівнює числу комбінацій, що отримуються|одержують| в результаті|унаслідок| циклічного зрушення|зсуву| рядка створюючої матриці і дзеркальної нею комбінації. Проте|однак| цей спосіб використовується для отримання|здобуття| код з|із| малим числом інформаційних розрядів. Вже при число комбінацій, що отримуються|одержують| в результаті|унаслідок| циклічного зрушення|зсуву|, буде менше, ніж число комбінацій, що отримуються|одержують| в результаті|унаслідок| підсумовування всіляких поєднань рядків створюючої матриці.

Число ненульових комбінацій, що отримуються|одержують| в результаті|унаслідок| підсумовування по модулю 2 всіляких поєднань рядків створюючої матриці

(61)

де - число інформаційних розрядів коди[14].

Число ненульових комбінацій, що отримуються|одержують| в результаті|унаслідок| циклічного зрушення|зсуву| будь-якого рядка створюючої матриці і дзеркальної нею комбінації

(62)

де - довжина кодової комбінації.

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

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

Ідея виправлення помилок базується на тому, що помилкова комбінація після|потім| певного числа циклічних зрушень|зсувів| “ підганяється|припасовує| ” під залишок|остачу| таким чином, що в сумі із|із| залишком|остачею| вона дає виправлену комбінацію. Залишок|остача| при цьому є не що інше, як різницю між спотвореними і правильними символами, одиниці в залишку|остачі| стоять якраз на місцях|місце-милях| спотворених розрядів в підігнаній|припасовувати| циклічними зрушеннями|зсувами| комбінації. Підганяють|припасовують| спотворену комбінацію до тих пір, поки число одиниць в залишку|остачі| не дорівнюватиме числу помилок в коді. При цьому, природно, число одиниць може бути або дорівнює числу помилок, що виправляються даним кодом (код виправляє 3 помилки і в спотвореній комбінації 3 помилки), або менше s (код виправляє 3 помилки, а в прийнятій комбінації - 1 помилка).

Місце|місце-миля| помилки в кодовій комбінації не має значення. Якщо те після|потім| певної кількості зрушень|зсувів| всі помилки опиняться в зоні “разової” дії створюючого многочлена, тобто досить отримати|одержувати| один залишок|остачу|, вага якого, і це вже буде досить для виправлення спотвореної комбінації. У цьому сенсі|змісті| коди БЧХ (про них ми говоритимемо нижче) можуть виправляти пачки помилок, аби довжина пачки не перевищувала s.

5.5. Побудова|шикування| і декодування конкретних циклічних код

I. Коди, що виправляють одиночну помилку .

1. Розрахунок співвідношення між контрольними і інформаційними символами коди проводиться на підставі виразів (43) - (53).

Якщо задано число інформаційних розрядів, то число контрольних розрядів знаходимо|находимо| з|із| виразу|вираження|

Загальне|спільне| число символів коди

Якщо задана довжина коди, то число контрольних розрядів

Співвідношення числа контрольних і інформаційних символів для код з|із| .

2. Вибір створюючого многочлена проводиться по таблицях двійкових многочленів, що не приводяться.

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

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

4. Визначення елементів додаткової матриці проводиться по залишках від ділення останнього рядка транспонованої матриці (одиниці з нулями) на створюючий многочлен. Отримані залишки повинні задовольняти наступним вимогам:

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

б) число залишків має бути не менше числа рядків одиничної|поодинокої| транспонованої матриці, тобто має дорівнювати числу інформаційних розрядів ;

в) число одиниць кожного залишку|остачі|, тобто його вага, має бути не менше величини, де - мінімальна кодова відстань, не менша числа помилок, що виявляються;

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

5. Матриця твірної складається дописуванням елементів додаткової матриці праворуч від одиничної транспонованої матриці або множенням елементів одиничної матриці на створюючий многочлен.

6. Комбінаціями шуканої коди є рядки створюючої матриці і всі можливі суми по модулю 2 різних поєднань рядків створюючої матриці.

7. Виявлення і виправлення помилок проводиться по залишках від ділення прийнятої комбінації на створюючий многочлен . Якщо прийнята комбінація ділиться на створюючий многочлен без залишку, то код прийнятий безпомилково. Залишок від ділення свідчить про наявність помилки, але не указує, який саме. Для того, щоб знайти помилковий розряд і виправити його в циклічних кодах, здійснюють наступні операції:

а) прийняту комбінацію ділять на створюючий многочлен і

б) підраховують|підсумовують| кількість одиниць в залишку|остачі| (вага залишку|остачі|).

Якщо де s - допустиме число що виправляються даним кодом помилок, то прийняту комбінацію складають по модулю 2 з отриманим залишком. Сума дасть виправлену комбінацію. Якщо то

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

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

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

е) проводять циклічне зрушення управо рівно на стільки розрядів, на скільки була зрушена підсумовувана з останнім залишком комбінація щодо прийнятої комбінації. В результаті отримаємо виправлену комбінацію[15].

II. Коди, що виявляють триразові|трикратні| помилки .

1. Вибір числа розрядів, що коректують, проводиться із співвідношення

або

2. Вибір створюючого многочлена проводять, виходячи з таких міркувань: для виявлення триразової помилки

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

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

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

5. Виявлення помилок проводиться по залишках від ділення прийнятої комбінації на створюючий многочлен . Якщо залишку немає, то контрольні розряди відкидаються і інформаційна частина коди використовується за призначенням. Якщо в результаті ділення виходить залишок, то комбінація бракується. Відмітимо, що такі коди можуть виявляти 75% будь-якої кількості помилок, оскільки окрім подвійної помилки виявляються всі непарні помилки, але гарантована кількість помилок, яку код ніколи не пропустить, дорівнює 3.

Приклад: Початкова кодова комбінація - 0101111000, прийнята - 0001011001 (тобто відбувся потрійний збій). Показати процес виявлення помилки, якщо відомо, що комбінації коди були утворені за допомогою многочлена 101111.

Рішення|розв'язання|:

Залишок|остача| не нульової, комбінація бракується. Вказати помилкові розряди при триразових|трикратних| спотвореннях такі коди не можуть.

III. Циклічні коди, що виправляють дві і більша кількість помилок

Методика побудови|шикування| циклічних код з|із| відрізняється від методики побудови|шикування| циклічних код з|із| тільки|лише| у виборі створюючого многочлена. У літературі ці коди відомі як коди БЧХ (перші букви|літери| прізвищ Боуз, Чоудхурі, Хоквінхем - авторів методики побудови|шикування| циклічних код з|із| ).

Побудова створюючого многочлена залежить, в основному, від двох параметрів: від довжини кодового слова п. і від числа помилок s, що виправляються. Решта параметрів, що беруть участь в побудові створюючого многочлена, залежно від заданих і можуть бути визначені за допомогою таблиць і допоміжних співвідношень, про які буде сказано нижче.

Для виправлення числа помилок ще не достатньо|досить| умови, щоб|аби| між комбінаціями коди мінімальна кодова відстань . необхідно також, щоб|аби| довжина коди задовольняла умові

(63)

при цьому п завжди буде непарним числом. Величина h визначає вибір числа контрольних символів і пов'язана з і s наступним співвідношенням:

(64)

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

(65)

де є одним із співмножників, на які розкладається число п.

Співвідношення між З і h можуть бути зведені в наступну таблицю

№ п/п	h		C
			5; 3 7; 3; 3 17; 5; 3 7; 3; 7 31; 11; 3 89; 23 3; 3; 5; 7; 13

Наприклад, при h = 10 довжина кодової комбінації може бути рівна і 1023 і 341 (З = 3), і 33 (З =31), і 31 (З = 33), зрозуміло, що п не може бути менше Величина З впливає на вибір порядкових номерів мінімальних многочленів, оскільки індекси спочатку вибраних многочленів умножаються на С.

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

(66)

Порядок многочлена використовується при визначенні числа співмножників . Наприклад, якщо s = 6, то . Оскільки для побудови використовуються тільки непарні многочлени, то ними будуть: старший з них має порядок . Як видимий, число співмножників рівне 6, тобто числу помилок, що виправляються. Таким чином, число мінімальних многочленів, що беруть участь в побудові створюючого многочлена

(67)

а старший ступінь|міра|

(68)

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

Ступінь|міра| створюючого многочлена, отриманого|одержувати| в результаті перемножування вибраних мінімальних многочленів

(69)

У загальному|спільному| вигляді|виді|

(70)

Декодування кодів БЧХ проводиться за тією ж методикою, що і декодування циклічних кодів|із| з . Проте|однак| у зв'язку з тим, що практично всі коди БЧХ представлені|уявляти| комбінаціями з|із|, можуть виникнути вельми|дуже| складні варіанти, коли для виявлення і виправлення помилок необхідно проводити велике число циклічних зрушень|зсувів|. В цьому випадку для полегшення можна комбінацію, отриману|одержувати| після|потім| -кратного| зрушення|зсуву| і підсумовування із|із| залишком|остачею|, зрушувати|зсовувати| не управо|вправо|, а вліво на циклічних зрушень|зсувів|. Це доцільно робіти|чинити| тільки|лише| при .

6. УЩІЛЬНЕННЯ|стиснення| ІНФОРМАЦІЇ

Ущільнення інформації є операцією, в результаті якої даному коду або повідомленню ставиться у відповідність коротший код або повідомлення[16].

Ущільнення|стиснення| інформації має на меті - прискорення і здешевлення процесів механізованої обробки, зберігання і пошуку інформації, економія пам'яті ЕОМ. При стискуванні|стисненні| слід прагнути до мінімальної неоднозначності стислих код при максимальній простоті алгоритму ущільнення|стиснення|. Розглянемо|розглядуватимемо| найбільш характерні|вдача| методи ущільнення|стиснення| інформації.

Ущільнення інформації діленням коду на частини, менші деякої наперед заданої величини А, полягає в тому, що початковий код ділиться на частини, менші А, після чого отримані частини коду складаються між собою або за правилами двійкової арифметики, або по модулю 2. Наприклад, початковий код 101011010110; A = 4

Ущільнення інформації з побуквенным зрушенням в кожному розряді, як і попередній спосіб, не передбачає відновлення стискуваних код, а застосовується лише для скорочення адреси або самої коди стискуваного слова в пам'яті ЕОМ.

Припустимо, початкове слово «газета» кодується кодом, в якому довжина кодової комбінації букви l = 8:

Грам - 01000111; а - 11110000; з - 01100011; е - 00010111; т - 11011000.

Повний|цілковитий| код слова «Газета»

010001111111000001100011000101111101100011110000.

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

рис.1

Допустима кількість розрядів ущільненого коду є|з'являється| цілком|сповна| визначеною величиною, залежною від способу кодування і від ємкості|місткості| ЗУ. Кількість адрес, а відповідно максимальна кількість слів у виділеній ділянці пам'яті машини визначається з|із| наступного|такого| співвідношення

(71)

де - максимально допустима довжина (кількість двійкових розрядів) стислої коди; N - можлива кількість адрес в ЗУ.

Якщо представити|уявляти| процес побуквенного| зрушення|зсуву| в загальному|спільному| вигляді|виді|, як показано на мал. 1, а, те довжина стислої коди

де до - число побуквенных зрушень; - довжина кодової комбінації букви.

Оскільки зрушуються всі букви, окрім першої, то і число зрушень де L - число букв в слові. Тоді

У російській мові найбільш довгі слова мають 23 - 25 букв. Якщо прийняти з умовою здійснення побуквенного зрушення з кожним кроком рівно на один розряд, для n і l можуть бути отримані наступні співвідношення

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

Наприклад, якщо для попереднього прикладу|зразка| із|із| словом “Газета”, стислий код матиме вигляд|вид|:

Метод ущільнення|стиснення| інформації на основі виключення|винятку| повторення в старших розрядах подальших|наступних| рядків, масивів однакових елементів старших розрядів попередніх рядків масивів заснований на тому, що в стислих масивах елементи старших розрядів, що повторюються, замінюються деяким умовним символом.

Дуже часто оброблювана інформація буває представлена|уявляти| у вигляді набору однорідних масивів, в яких елементи стовпців або рядків масивів розташовані|схильні| в наростаючому порядку|ладі|. Якщо вважати за старших розряди, розташовані|схильні| лівіше даного елементу, а молодшими - розташовані|схильні| правіше, то можна відмітити|помітити|, що у багатьох випадках рядки матриць відрізняються один від одного в молодших розрядах. Якщо при записі кожного подальшого|наступного| елементу масиву відкидати що все повторюються в попередньому елементи, наприклад в рядку варті підряд елементів старших розрядів, то масиви можуть бути скорочені від 2 до 10 і більш за розряди.

Для обліку викинутих розрядів вводиться знак розділу який дозволяє відокремити елементи в згорнутому масиві. У разі повного повторення рядків записується відповідно кількість . При розгортанні замість знаку відновлюються всі пропущені розряди, які були до елементу, що стоїть безпосередньо за у стислому тексті.

Для прикладу|зразка| розглянемо|розглядуватимемо| наступний|слідуючий| масив:

Згорнутий масив матиме вигляд|вид|:

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

Пропущені цифри заповнюються автоматично по аналогічних розрядах попереднього рядка. Заповнення проводиться з початку масиву. Цей метод можна розвинути і для згортання масивів, в яких розряди, що повторюються, зустрічаються не тільки з початку рядка. Якщо в рядку одна ділянка, що повторюється, то окрім додається ще один додатковий символ До, що означає кінець рядка. Розшифровка ведеться від До до К. Дліна рядки відома. Потрібно, щоб що залишилися між K цифри разом з пропущеними розрядами складали повний рядок. При цьому нам все одно, в якому місці рядка викидаються розряди, що повторюються, аби в рядку було не більш за одну ділянку з розрядами, що повторюються. Наприклад:

Якщо в рядку є дві ділянки, що повторюються, то,використовуючи цей метод, викидаємо більший.

Процес розгортання масиву здійснюється таким чином: перехід на наступний рядок відбувається при зустрічі к

Пропущені цифри заповнюються по аналогічних розрядах попереднього рядка починаючи|розпочинати| з|із| кінця масиву.

Якщо в рядку масиву декілька ділянок, що повторюються, то можна замість вставляти спеціальні символи, вказуючі|показуючі| на необхідне число пропусків.

Наприклад, якщо позначити кількість пропусків, відповідно, Х - 2; Y - 3; Z - 5, то початковий і згорнутий масиви матимуть вигляд:

Процес розгортання масиву здійснюється таким чином: довжина рядка відома, кількість пропусків визначається символами X, Y, Z

Пропущені цифри заповнюються по аналогічних розрядах попереднього рядка. Умовою переходу на наступний|такий| рядок є|з'являється| заповнення попереднього рядка.

Метод Г. В. Лівінського заснований на тому, що в пам'яті машини зберігаються стислі числа, розрядність яких менше розрядності реальних чисел. Ефект ущільнення досягається за рахунок того, що послідовності заздалегідь впорядкованих чисел розбиваються на ряд рівних відрізань, усередині яких відлік ведеться не по їх абсолютній величині, а від межі попереднього відрізання. Розрядність чисел, що отримуються таким чином, природно, менше розрядності відповідних їм реальних чисел.

Для розміщення в пам'яті ЕОМ М код, в яких найбільше з кодованих чисел рівне N, необхідний об'єм пам'яті

Із зростанням N довжина кодової комбінації ростиме як . Для економії об'єму пам'яті Q, число де вираз в дужках - закруглене значення до найближчого цілого числа, розбивають на L рівних частин. Максимальне число в отриманому інтервалі чисел буде не більше . Величина визначає розрядність чисел, що зберігаються, об'єм пам'яті для їх зберігання буде не більший . Якщо в пам'яті ЕОМ зберігати адреси меж відрізань і порядкові номери чисел, що зберігаються, відлічуваних від чергової межі, то визначає розрядність чисел для виразу номера межі (у останньому інтервалі має бути хоч би одне число); об'єм пам'яті для зберігання номерів меж буде _

(72)

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

[17] (73)

Якщо підставити значення у вираз (72), то отримаємо. значення об'єму пам'яті при оптимальній кількості зон, на, які розбиваються числа, що зберігаються в пам'яті ЕОМ

(74)

Для значень при обчисленнях|підрахунках| можна користуватися наближеною формулою

(75)

При пошуку інформації в пам'яті ЕОМ перш за все|передусім| визначають значення і знаходять|находять| величину інтервалу між двома межами|кордонами|

Потім визначають, в якому саме з інтервалів знаходиться шукане число х

Після|потім| цього визначається адреса шуканого числа як різниця між абсолютним значенням числа і числом, яке є|з'являється| граничним для даного інтервалу.

Завдання 7.1:. Визначити допустиму кількість слів, адреси яких можуть зберігати в ЗУ, якщо максимальна довжина кодованих слів L=15, а двійковий код букв – п'ятизначний.

Рішення|розв'язання|:

Завдання 7.2:. Визначити допустиму кількість зрушень при стискуванні восьмирозрядних кодових комбінацій, якщо допустима довжина стислої коди n_макс=12.

Рішення|розв'язання|:

Завдання 7.3. Використовуючи знак розділу р, скрутити наступний масив чисел:

1 9 7 1 1 3 7 4 3 0

1 9 7 1 1 3 7 4 3 1

1 9 7 1 1 3 7 4 3 2

1 9 7 1 1 3 7 4 3 0

1 9 7 1 1 3 7 4 3 1

1 9 7 1 1 3 7 4 3 2

Рішення|розв'язання|:

1 9 7 1 1 3 7 4 3 0

1 2 0 1 2