Пристрій контролю даних у флеш-пам’яті за допомогою кодів crc

Реферат: UA 122543 U UA 122543 U 5 10 15 20 25 30 35 Корисна модель належить до комп'ютерної техніки і може бути використана в комп'ютерних мережах та системах. Відомі пристрої контролю даних у флеш-пам'яті. Згідно з Керівництвом по проектуванню флеш-памяті [NAND Flash Application Design Guide from Toshiba America Electronic Components, Inc., Revision 1.0 April 2003], для виявлення та виправлення помилок використовуються різні завадостійкі коди, найчастіше коди CRC (Cyclic Redundancy Code). CRC може обчислюватись в межах сектора прикладної програми, завантажувального сектора або заданого діапазону адрес. Недоліком такого способу контролю є зберігання значення CRC в комірках з постійними адресами. Оскільки флеш-пам'ять має обмежену кількість циклів перезапису даних, а значення CRC часто змінюються, в результаті збільшується кількість операцій запису і флеш-пам'ять швидко витрачає свій ресурс. Найбільш близьким по технічній суті до запропонованого пристрою є пристрій для розподілу кодів CRC у флеш-пам'яті [патент США US 7,055,083 В2 Μ. кл., Η03Μ 13/00, May 30, 2006 (Method and Apparatus for Allocating CRC Codes in Flash ROM)], що містить мікропроцесор, оперативний запам'ятовуючий пристрій (ОЗП), флеш-пам'ять та системну шину, яка зв'язує їх між собою. У відомому пристрої коди CRC більш рівномірно розподілені по флеш-пам'яті, але внаслідок збільшення їх кількості відповідно збільшується кількість операцій стирань та запису у флешпам'ять, що призводить до скорочення терміну її використання. Крім цього недоліками відомого пристрою є також тривалий час для формування контрольної інформації для окремого блока флеш-пам'яті та мала здатність для виявлення та виправлення помилок. В основу корисної моделі поставлена задача створення пристрою контролю даних у флешпам'яті за допомогою кодів CRC, в якому за рахунок введення нових блоків та зв'язків досягається можливість прискорення формування контрольної інформації та зменшення кількості операцій стирань та запису у флеш-пам'ять. Поставлена задача вирішується за рахунок того, що у пристрої контролю даних у флешпам'яті за допомогою кодів CRC, який складається з мікропроцесора, ОЗП і системної шини, яка зв'язує їх між собою, флеш-пам'ять розбита на перший та другий вузли, крім того введений блок контролю, перший і другий інформаційні входи якого з'єднані відповідно з виходом даних першого вузла флеш-пам'яті і з виходом даних другого вузла флеш-пам'яті, входи та виходи даних і адрес яких під'єднані до системної шини, керуючий та установочний входи пристрою зв'язані з керуючим та установочним входами блока контролю, вихід якого під'єднаний до контрольного виходу пристрою. На фіг. 1 представлена функціональна схема пристрою; на фіг. 2 - функціональна схема блока контролю; на фіг. 3 - приклад "прямої" лінійної послідовнісної схеми (ЛПС) для породжувального поліному g( x )  1  x 4  x 5  x 6  x 8 ; на фіг. 4 - приклад "оберненої" лінійної 40 45 50 55 ЛПС для породжувального поліному g( x )  1  x 4  x 5  x 6  x 8 . Пристрій контролю даних у флеш-пам'яті за допомогою кодів CRC (фіг. 1) містить мікропроцесор 1, ОЗП 2, системну шину 3, перший вузол флеш-пам'яті 4, другий вузол флешпам'яті 5 та блок контролю 6, перший інформаційний вхід, другий інформаційний вхід, керуючий вхід, установочний вхід та вихід якого зв'язані відповідно з виходом даних першого вузла флешпам'яті 4, виходом даних другого вузла флеш-пам'яті 5, з керуючим входом 7 пристрою, з установочним входом 8 пристрою та контрольним виходом 9 пристрою, системна шина, яка служить для передавання даних і адресів, зв'язує між собою мікропроцесор 1, ОЗП 2, перший вузол флеш-пам'яті 4 та другий вузол флеш-пам'яті 5. Блок контролю 6 (фіг. 2) містить "пряму" ЛПС 10, "обернену" ЛПС 11, схему порівняння 12, RS-тригер 13, перший елемент кон'юнкції 14, другий елемент кон'юнкції 15, керуючий вхід 7 пристрою з'єднаний з S-входом RS-тригера 13, вихід якого з'єднаний з першими входами першого елемента кон'юнкції 14 та другого елемента кон'юнкції 15, виходи яких з'єднані з інформаційними входами "прямої" ЛПС 10 і "оберненої" ЛПС 11, інформаційні виходи яких з'єднані з входами схеми порівняння 12, вихід якої з'єднаний з контрольним виходом 9 пристрою, установочний вхід 8 якого з'єднаний з установочними входами "прямої" ЛПС 10, "оберненої" ЛПС 11 та з R-входом RS-тригера 13, другі входи першого елемента кон'юнкції 14 та другого елемента кон'юнкції 15, з'єднані відповідно з першим інформаційним входом 16 блока та другим інформаційним входом 17 блока. Приклад "прямої" ЛПС для породжувального поліному g( x )  1  x 4  x 5  x 6  x 8 (фіг. 3) містить вісім елементів пам'яті 18,118,8 і чотири суматори по модулю два 19,119,4. 1 UA 122543 U 5 Приклад "оберненої" ЛПС для породжувального поліному g( x )  1  x 4  x 5  x 6  x 8 (фіг. 4) містить вісім елементів пам'яті 20,120,8 і чотири суматори по модулю два 21,121,4. Пристрій працює таким чином. Для зберігання даних використовуються перший вузол флеш-пам'яті 4 та n другий вузол флеш-пам'яті 5, в яких розмір блоків даних дорівнює бітів 2 ( n  512,1024, 2048,... ). Перед записом k -розрядного інформаційного слова U  u1u2,..., uk у перший вузол флеш-пам'яті 4 та у другий вузол флеш-пам'яті 5 має бути проведено його кодування за правилами кодування циклічних ( n,k )-кодів. Для кодування використовується лише один різновид циклічних кодів - коди CRC, які задаються r -розрядними породжувальними поліномами: примітивним поліномом виду: 10 G1( x )  g0  g1x  g2 x 2  ...  gr 1x x 1  gr x r , GF(2) (1) або поліномом виду: G2 ( x)  G0 ( x)1  x  , GF(2), 15 (2) де G0 ( x ) - примітивний поліном виду: G0 ( x )  g0  g1x  g2 x 2  ...  gr 1x x 1 . GF(2). 20 25 30 При несистематичному кодуванні k -розрядне інформаційне слово U перетворюється у n розрядне кодове слово Z , в якому інформаційні та контрольні розряди не містяться в явному вигляді. При систематичному кодуванні до k -розрядного інформаційного слова U додається r розрядне контрольне слово  , в результаті чого формується n -розрядне кодове слово Z  U . Після завершення процедури кодування у перший вузол флеш-пам'яті 4 записується перша частина кодового слова Z розміром n розрядів (при непарному n перед першим розрядом 2 інформаційного слова u1 додається нуль), а у другий вузол флеш-пам'яті 5 записується друга частина кодового слова Ζ розміром n розрядів. 2 Під час зчитування кодового слова Z даних відбувається його декодування за правилами декодування циклічних кодів (кодів CRC). Для опису операцій декодування кодів CRC використовується теорія лінійних автоматів - лінійних послідовнісних схем (ЛПС). ЛПС реалізована у двох варіантах: як "пряма" ЛПС 10 та як "обернена" ЛПС 11. Функціонування "прямої" ЛПС 10 при декодуванні здійснюється згідно з формулою: St  1  A  St   B  Zt  , GF(2), 35  r r , де t - дискретний час; A  a i, j 40 (3) B  bi r - характеристичні матриці; Zt  - t -й розряд кодового слова Z в такт часу t ; St  - стан "прямої" ЛПС в момент часу t ; St  1 - стан "прямої" ЛПС в момент часу t  1; "  " - операція множення по модулю 2, "  " - операція додавання по модулю 2. Формула (3) описує перехід в такт часу t  1 "прямої" ЛПС 10 із стану St  в наступний стан St  1 . "Пряма" ЛПС 10 використовує характеристичні матриці такого типу: 2 UA 122543 U 0 1 A 0 ... 0 0 0 1 ... 0 0 0 0 ... 0 ... ... ... ... 1 g0 1 g1 0 ,B 0 . g2 ... ... gr 1 0 (4) Останній стовпчик матриці A в (4) містить коефіцієнти породжувального поліному циклічного коду степеня r виду (1) або (2). Функціонування "оберненої" ЛПС 11 при декодуванні здійснюється згідно з формулою: 5 St   Ainv  St  1  B  Zt  , GF(2). (5) Формула (5) описує перехід в такт часу t  1 "оберненої" ЛПС 11 із стану St  1 в попередній стан St  . "Обернена" ЛПС 11 використовує характеристичні матриці такого типу: 10 g1 A inv 1 0 0 ... 0 0 g2 0 1 0 ... 0 0 g3 0 0 1 ... 0 0 ,B .  ... ... ... ... ... ... ... gr 1 0 0 0 ... 1 0 g0 0 0 0 ... 0 1 (6) Перший стовпчик матриці A в (6) містить коефіцієнти породжувального поліному циклічного коду степеня r виду (1) або (2). Для матриць A і A inv в (4) і (6) справедлива рівність: 15 A  A inv  I , GF(2), 20 25 30 де I - одинична матриця. При традиційному способі декодування коду CRC використовується лише "пряма" ЛПС 10: якщо при подачі на вхід "прямої"" ЛПС 10 n -розрядного кодового слова Z , починаючи з перших розрядів, тоді така ЛПС з початкового нульового стану S0  через n тактів часу знову перейде в стан S0  , це буде свідчити про відсутність в кодовому слові Z тих помилок, які виявляються вибраним породжувальним поліномом виду (1) або (2). Аналогічним чином для декодування коду CRC може бути використана лише "обернена" ЛПС 11: якщо при подачі на вхід "оберненої" ЛПС 11 n -розрядного кодового слова Z , починаючи з останніх розрядів, така ЛПС з початкового нульового стану S0  через n тактів часу знову перейде в стан S0  , це буде свідчити про відсутність в кодовому слові Z тих помилок, які виявляються вибраним породжувальним поліномом виду (1) або (2). При одночасному використанні "прямої" ЛПС 10 та "оберненої" ЛПС 11 час декодування може бути скорочено вдвічі. В цьому випадку на вхід "прямої"" ЛПС 10 надходить кодове слово Z , починаючи з перших розрядів, а на вхід "оберненої" ЛПС 11 надходить кодове слово Z , починаючи з останніх розрядів. Протягом n тактів часу "пряма" ЛПС 10 переходить із початкового нульового стану 2 sy S0  в стан S n , який є першим синдромом перевірки S1 n. Одночасно "обернена" ЛПС 11 2 переходить із початкового нульового стану S0  в стан S n , який є другим синдромом 2   35   перевірки Ssy n. 2 3 UA 122543 U При відсутності помилок зберігання і зчитування два синдроми перевірки повинні бути 5 10 15 рівними: Ssy n  Ssy n. 1 2 На підготовчому етапі роботи пристрою за допомогою кодувальної ЛПС (тут не показано) здійснюється кодування даних. На цьому етапі RS-тригер 13 знаходиться в стані логічної одиниці, що дозволяє запис кодових слів Z по системній шині 3 через перший елемент кон'юнкції 14 та другий елемент кон'юнкції 15 відповідно у перший вузол флеш-пам'яті 4 і другий вузол флеш-пам'яті 5. Після завершення підготовчого етапу у першому вузлі флеш-пам'яті 4 зберігається перша частина кодового слова Z , а в другому вузлі флеш-пам'яті 5 зберігається друга частина кодового слова Z . Далі на установочний вхід 8 пристрою надходить сигнал, який встановлює в нульовий стан RS-тригер 13, елементи пам'яті 18,118,8 та елементи пам'яті 20,120,8. Нульовий стан елементів пам'яті 18,118,8 та елементів пам'яті 20,120,8 означає нульовий стан S0  відповідно "прямої" ЛПС 10 і "оберненої" ЛПС 11. На етапі зчитування даних з першого вузла флеш-пам'яті 4 і другого вузла флеш-пам'яті 5 на керуючий вхід 7 пристрою надходить сигнал, який встановлює RS-тригер 13 в стан логічної одиниці і дозволяє передачу кодових слів на системну шину 3 та у блок контролю 6. "Пряма" ЛПС 10 та "обернена" ЛПС 11 починають одночасно функціонувати відповідно формули (3) та формули (5). Через n тактів часу за допомогою "прямої" ЛПС 10 буде сформовано перший синдром 2 перевірки Ssy n, а за допомогою "оберненої" ЛПС 11 буде сформовано другий синдром 1 20 25 30 35 40 перевірки Ssy n. 2 За допомогою схеми порівняння 12 здійснюється порівняння станів "прямої" ЛПС 10 та "оберненої"' ЛПС 11. Рівність синдромів Ssy n  Ssy n на n -му такті часу формує сигнал логічної 1 2 2 одиниці на контрольному виході 9 пристрою, що свідчить про відсутність помилок у відповідному записаному та зчитаному кодовому слові. Робота пристрою відбувається під керуванням мікропроцесор 1, згідно з програмою, яка записана в ОЗП 2 і передається через системну шину 3. У відомому пристрої процедура декодування циклічних ( n,k )-кодів (кодів CRC) здійснюється протягом n тактів часу. У відомому пристрої окрім n тактів для обчислення традиційного коду CRC необхідно також і n тактів для його модифікації, в результаті чого втрачається можливість для виправлення помилок. У запропонованому пристрої процедура декодування здійснюється швидше: протягом n 2 тактів часу. При цьому зберігається можливість для виправлення поодиноких помилок та подвійних сусідніх помилок. У відомому пристрої модифікація контрольного слова (CRC) вимагає додаткової операції його запису у флеш-пам'ять, що зменшує термін використання всього пристрою. У запропонованому пристрої при систематичному кодуванні контрольне слово (CRC) буде міститись лише у другому вузлі флеш-пам'яті 5 (при k  n ), завдяки чому збільшується термін 2 використання першого вузла флеш-пам'яті 4. При формуванні кодового слова Z за допомогою несистематичного кодування код CRC повністю відсутній як окремий параметр, інформаційні та контрольні розряди рівномірно розподілені по кодовому слову, відповідно кількість операцій стирань та запису буде однаковою для всіх використаних комірок першого вузла флеш-пам'яті 4 та другого вузла флеш-пам'яті 5. Завдяки цьому збільшується термін використання першого вузла флеш-пам'яті 4 та другого вузла флеш-пам'яті 5. Тоді вже немає потреби розподіляти флеш-пам'ять на два вузли. 45 4 UA 122543 U ФОРМУЛА КОРИСНОЇ МОДЕЛІ 5 10 15 20 1. Пристрій контролю даних у флеш-пам'яті за допомогою кодів CRC, який складається з мікропроцесора, оперативного запам'ятовуючого пристрою (ОЗП) і системної шини, яка зв'язує їх між собою, який відрізняється тим, що флеш-пам'ять розбита на перший вузол і другий вузол, крім того в нього введений блок контролю, перший і другий інформаційні входи якого з'єднані відповідно з виходом даних першого вузла флеш-пам'яті і з виходом даних другого вузла флеш-пам'яті, входи та виходи даних і адрес яких під'єднані до системної шини, керуючий та установочний входи пристрою зв'язані з керуючим та установочним входами блока контролю, вихід якого під'єднаний до контрольного виходу пристрою. 2. Пристрій за п. 1, який відрізняється тим, що блок контролю містить "пряму" ЛПС, "обернену" ЛПС, схему порівняння, RS-тригер, перший елемент кон'юнкції, другий елемент кон'юнкції, причому керуючий вхід пристрою з'єднаний з S-входом RS-тригера, вихід якого з'єднаний з першими входами першого елемента кон'юнкції та другого елемента кон'юнкції, виходи яких з'єднані з інформаційними входами "прямої" ЛПС і "оберненої" ЛПС, інформаційні виходи яких з'єднані з входами схеми порівняння, вихід якої з'єднаний з контрольним виходом пристрою, установочний вхід якого з'єднаний з R-входом RS-тригера, другі входи першого елемента кон'юнкції та другого елемента кон'юнкції, з'єднані відповідно з першим та другим інформаційними входами блока. 5 UA 122543 U 6 UA 122543 U Комп’ютерна верстка Л. Ціхановська Міністерство економічного розвитку і торгівлі України, вул. М. Грушевського, 12/2, м. Київ, 01008, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7