Методичні вказівки до виконання курсової роботи з дисципліни «Дослідження І проектування програмних систем»

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
МЕТОДИЧНІ ВКАЗІВКИ
до виконання курсової роботи з дисципліни
«Дослідження і проектування програмних систем»
для студентів спеціальності 123.03
«Спеціалізовані комп’ютерні системи» денної форми навчання.
Затверджено
на засіданні кафедри спеціалізованих
комп’ютерних систем
Національного університету
«Львівська політехніка»,
протокол № 10 від 13.01.2020 р.
Львів 2020

3
ЧАСТИНА 1
Варіанти тем
(може бути будь-яка інша в межах назви курсу)
1. Методологія системного аналізу розробки програмних систем
2. Об’єктний підхід до створення програмних систем
3. Життєві цикли розробки програмного забезпечення
4. Об’єктно-орієнтований аналіз: домени та підсистеми
5. Об’єктно-орієнтований аналіз: моделі станів та моделі процесів
6. Об’єктно-орієнтоване проектування: фази проектування
7. Об’єктно-орієнтоване проектування: стилі та засоби проектування
8. Об’єктно-орієнтоване проектування: проектування архітектури та механізмів
9. Стандарт опису системи IDEF0 10. Стандарт опису системи IDEF3 11. Проектування на основі патерів та фреймворків
12. Технології проектування на базі JAVA та C#
13. Особливості використання технології JSF
14. Особливості використання технології ASP NET
15. Технології проектування баз даних
16. Архітектурне проектування програмних систем
17. Деталізоване проектування програмних систем
18. Принципи розробки програмних систем: частотний принцип
19. Принципи розробки програмних систем: принцип модульності
20. Принципи розробки програмних систем: принцип функціональної вибірковості
21. Загальносистемні принципи розробки програмних систем
22. Стандарти проектування програмних систем
23. Методики підвищення якості програмних систем
24. Архітектурні стилі проектування програмних систем
25. Проектування програмних систем: REST архітектура
26. Проектування програмних систем: аналіз вимог і розробка зовнішніх специфікацій
27. Синтез програмних систем та етапи проектування
28. Класифікація і особливості видів тестування
29. Підходи до проектування програмних систем
30. Проектування програмних інтерфейсів комп’ютерних систем

4
ЧАСТИНА 2
1. ЦИКЛІЧНІ КОНТРОЛЬНІ СУМИ
1.1 Принцип утворення і використання циклічних контрольних сум
При передачі інформації в локальних мережах можливі помилки, тобто спотворення інформації, що передається. Ці помилки необхідно виявляти і виправляти. Контроль правильності передачі інформації може виконуватись як приймачем, так і передавачем.
Контрольпередавачем на відміну від контролю приймачемне потребує практично ніякого додаткового часу. Але як приймаючий абонент може взнати, чи є помилки в прийнятій інформації? Ідея в полягає наступному: до
інформації добавляються додаткові контрольні біти, в які входить в згорнутому вигляді характеристика всіх інформаційних бітів. Вважається, що ймовірність спотворення цих додаткових бітів набагато менша, ніж інформаційних бітів
(менша у стільки ж разів, в скільки разів кількість додаткових бітів менша кількості інформаційних бітів). А далі приймач перевіряє відповідність прийнятих інформаційних і контрольних бітів, і на основі цього і робиться висновок про наявність помилок. Потім він повідомляє передавачеві, чи виявив він помилки чи ні, а передавач при необхідності повторює свою передачу.
Дуже часто додаткові контрольні біти формуються як циклічна контрольна сума. Її використання викликане прагненням підвищити якість контролю, тобто збільшити ймовірність виявлення помилок. Цю суму не можна просто обрахувати програмно, однак надійність такого методу контролю набагато нижча ніж при його апаратній реалізації. Даний метод часто називають “циклічним контролем за надлишковостю” (скорочено СRС -
Сусliс Radundanсу Сheсk). Зміст його полягає в тому, що весь інформаційний пакет розглядається як М-розрядне двійкове число, де M - кількість біт в пакеті.
Для обчислення контрольної суми це число ділиться на деяке постійне число, вибране спеціальним чином (але ділиться не просто, а по модулю 2). Частка від ділення відкидається, а залишок використовується як контрольна сума.
Обчислення і використання коду CRC проводиться у відповідності з наступною послідовністю дій: до вмістимого кадра, що описується поліномом F(x), добавляється набір одиниць (поліном L(x) степені n-1)
L(x) =

−
=
1 0
n
i
x
i
= 11...1,

5 кількість котрих рівна довжині поля CRC. Утворене таким чином число х
n
(F(x)
+ x
k
L(x)), де k - степінь F(x), знак “+” означає додавання по модулю 2, а множення на x
i відповідає зсуву на i розрядів вліво, ділиться на твірний поліном g(x) степені n. Залишок O(x) від такого ділення, що визначається з співвідношення Q(x)g(x) = x
n
(F(x) + x
k
L(x)) + O(x), де Q(x) - частка від ділення
x
n
(F(x) + x
k
L(x)) на g(x), в інвертованому вигляді O’(x) = Q(x) + L(x) поміщається в контрольне поле кадра. На прийомній стороні виконується ділення вмістимого кадра з полем CRC F
*
(x) = x
n
(F(x) + x
k
L(x)) + O’(x) (кодова комбінація, що передається), на поліном g(x). Результат такого ділення можна привести до вигляду: [x
n
(F(x) + x
k
L(x)) + O(x)]/ g(x) + L(x)/ g(x) =
[Q(x)g(x)]/
g(x) + L(x)/ g(x). Доданок першої складової ділиться на g(x), тому в приймача, якщо при передачі не було помилок, залишок получається рівним залишку від ділення постійного доданка другої складової L(x) і , так як L(x) < g(x), має вигляд x
n-1
+ x
n-2
+ x
n-3
+ ... + x
3
+ x
2
+ x + 1 = 111...111 = L(x).
Таким чином, якщо результат обчислень на стороні приймача рівний деякому визначеному числу (в наведеному вище прикладі 11..11, в деяких системах нулю чи іншому числу, що не співпадає з приведеним вище), то вважається, що передача проведена без помилок.
Можливі й інші алгоритми формування і перевірки контрольного поля кадра. Однак відмінності їх від розглянутого носять частковий характер.
Технічна реалізація обчислень CRC базується, як правило, на використанні регістрів зсуву з логічними елементами “виключне АБО” (сума за модулем 2).
Наприклад, схема ділення вхідної послідовності на поліном g(x) = x
6
+ x
4
+1
(який відповідає двійковому запису дільника 1010001) наведена на рис. 1.1.
0
Вхід
1 2
3 4
5
Рис. 1.1 Схема ділення на поліном g(x) = x
6
+ x
4
+1
Після зсуву всього вихідного кадра в комірках пам’яті регістра зсуву залишається результат ділення (залишок). В подальшому він використовується як контрольне поле кадра.

6
1.2 Формувач циклічних контрольних сум
Схема формування циклічних контрольних сум (передавач) зображена на рис. 1.2.
Схема функціонує наступним чином: інформація на вхід формувача подається через вхід D_in. Циклічні контрольні суми формуються у тригерах регістру RG_CRC, у кожен з яких при подачі сигналу скиду записується значення ‘1’, паралельно інформація поступає до буферного регістра Rg_delay, якbq при початковому скиді встановлюються в ‘0’. Пакет вихідної інформації складається з інформаційних розрядів та розрядів циклічних контрольних сум.
На вихід формувача інформація поступає через вивід D_out з мультиплексора.
Робота мультиплексора керується сигналом +data/-crc, який подається на його адресний вхід та переключає його після проходження останнього біту вхідного повідомлення.
Максимальну кількості залишків при діленні дають так звані прості поліноми, які визначаються аналогічно тому, як визначаються прості числа у звичайній арифметиці (табл. 1.1). Відміна полягає лише в тому, що при визначенні поліномів використовується модульна арифметика (додавання за модулем 2 - ⊕).
Таблиця 1.1
Прості поліноми
N x
2
x
1
x
0
Вираз
Простий поліном ?
0 0 0
0 0
1 0 0
1 1
Так
2 0 1
0 x
Так
3 0 1
1 x+1
Так
4 1 0
0 x
2
=x*x
Ні
5 1 0
1 x
2
+1=(x+1)*( x+1)=x
2
+(x
⊕x)+1
Ні
6 1 1
0 x
2
+x=x*(x+1)
Ні
7 1 1
1 x
2
+x+1
Так
RG_CRC
RG_delay
+data/-crc
D_out
D_in
0 1
2 3
4 5
0
1
2
3
4
5
&
&
&
1
Рис. 1.2 Схема формування циклічних контрольних сум (передавач)

7
1.3 Вузол виправлення помилки
Cхема блоку виправлення помилки (приймача) приведена на рис. 1.3.
На вхід D_in надходять дані з лінії передачі інформації. Для виправлення помилки необхідно віднайти номер біту, який є зіпсований, та у подальшому
інвертувати його. Циклічна контрольна сума формуються у регістрах RG_CRC
при цьому замість серії нулів після подачі інформаційного повідомлення (як це відбувалося в передавачі) на вхід подається контрольна сума. У випадку відсутності помилки результатом, що сформується у регістрі RG_CRC,
буде серія одиниць. Якщо ж у повідомленні мала місце помилка, то результат буде ненульовим. Його необхідно інвертувати і переслати на вузол визначення помилкового біта RG_err. Схема цього вузла аналогічна схемі вузла RG_CRC
при умові подачі на її вхід нулів. Синдром помилки (комбінація бітів результату) виникає у випадку наявності зіпсованого біту. Для кожного конкретного твірного поліному синдром помилки є величиною постійною.
Його значення визначається розрахунком, а сам сигнал індикації помилки формується за допомогою схеми “&”, вихід якої сигналізує про помилку у поточному біті. Для виправлення помилки необхідно зберігати в допоміжному буфері саме повідомлення. Для цього використовується регістр Rg_delay, кількість тригерів у якому залежить від довжини повідомлення. Виправлення помилки реалізується за допомогою побітового додавання за модулем 2
RG_error
Error
&
5
4
3
RG_CRC
RG_delay
D_out
D_in
Рис. 1.3 Cхема блоку виправлення помилки (приймач)
56
1
55
1
54
1
2
1
0
2
1
0
5
4
3
2
1
0

8 розряду повідомлення і сигналу Error наявності помилки в даному біті.
Відновлена інформація поступає на вихід блоку Data_out.
1.4 Приклад визначення контрольної суми
Для виправлення однократної помилки контрольна сума повинна однозначно кодувати номер зіпсутого двійкового розряду повідомлення (якщо він є) або кодувати ознаку відсутності помилок. Тобто, n-розрядна контрольна сума кодує ознаку відсутності помилки і 2
n
-1 двійкових розрядів, у яких може бути помилка. Серед цих розрядів знаходятся і n розрядів самої контрольної суми. Таким чином кількість інформаційних розрядів у повідомленні складає максимум 2
n
-n-1. Для 4 розрядної контрольної суми кількість інформаційних розрядів повідомлення дорівнює 2 4
-4-1=11.
Нижче наведено приклад визначення 4-розрядної контрольої суми, яка утворюється приймачем за допомогою полінома g(x) = x
4
+х
2
+ x +1 (рис. 1.4).
На вхід приймача подається інформаційний двійковий код 10111 і закінчення
0000. Початковий стан тригерів передавача - одиничний. Зміна інформації у тригерах передавача показана на рис. 1.4.
На вхід приймача подається інформаційний двійковий код 10111,
інвертована контрольна сума 1010. Зміна інформації у тригерах приймача показана на рис. 1.5.
0
Вхід
1
Початковий стан тригерів
Результат першого зсуву
Інверсія результату – CRC
1 0
1 1
1 1
1 0
1 1
0 1
1 0
0 1
1 0
0 0
0 0
0 0
1 1
1 0
1 1
1
Результат останнього зсуву
1 0
1 1
1 1
1 1
0 0
0 1
1 1
0 0
1 0
1 1
1 0
1 1
0 1
1 1
0 1
0 1
0
Ін ф
ор ма ці
йн
і б
іт и
Б
іт и ци кл
іч но го к
од у
3 2
Рис. 1.4 Схема ділення на поліном g(x) = x
4
+х
2
+ x +1

9
Ознака відсутності помилки
0
Вхід
1
Початковий стан тригерів
Результат першого зсуву
1 0
1 1
1 1
1 0
1 1
0 1
1 0
0 1
1 0
0 1
0 0
1 0
1 1
1 0
1 1
1
Результат останнього зсуву
1 0
1 1
1 1
1 1
0 1
0 1
0 1
0 1
0 1
1 1
1 1
1 1
0 1
1 1
0 0
0 0
0
Ін ф
ор ма ці
йн
і б
іт и
Б
іт и ци кл
іч но го к
од у
3 2
Рис. 1.5 Схема визначення ознаки відсутності помилки
2. ЗАВДАННЯ НА РОЗРАХУНКОВО-ГРАФІЧНУ
ТА КОНТРОЛЬНУ РОБОТУ
2.1 Завдання на роботи
В ході роботи необхідно розробити топологію друкованої плати, призначеної для пересилання інформації по послідовному каналу і її контролю за допомогою циклічних контрольних сум. Друкована плата повинна містити:
• вузол формування циклічної контрольної суми (передавач);
• вузол виправлення помилок (приймач).
В ході роботи необхідно:
1) розробити бібліотечні елементи, необхідні для проектування топології друкованої плати;
2) розробити схеми електричні принципові вузлів генерації та перевірки циклічних контрольних сум;
3) розробити топологію 1-шарової друкованої плати;
4) розробити топологію 2-шарової друкованої плати;
5) розробити топологію 4-шарової друкованої плати.
6) задокументувати розроблені схеми електричні принципові і топології друкованих плат. !!!!!!!!! Для виконання розрахунково-графічної роботи необхідно використати середовища OrCAD, P-CAD або їх аналоги.

10
!!!!!!!!! Для виконання контрольної роботи необхідно використати пакет
фірми Xilinx.
!!!!!!!!! Опис особливостей отримання друкованих плат описано в
Частині 2. Проектування друкованих плат.
2.2 Варіанти завдання
Варіанти завдання:
1) утворюючий поліном для циклічної контрольної суми обирається з табл. 2.1 відповідно до порядкового номера студента.
Варіант утворюючого поліному для розрахунково-графічної та
контрольної роботи один і той самий.
Таблиця 2.1
Утворюючі поліноми (для студентів денної форми навчання)
№ Поліном L(x)
№ Поліном L(x)
№
Поліном L(x)
1. x
6
+x
4
+x
2
+x+1 2. x
7
+x
4
+1 21. x
6
+x
2
+x+1 3. x
6
+x
4
+x
3
+x+1 4. x
7
+x
4
+x
3
+x
2
+1 22. x
7
+x
5
+x
3
+1 5. x
6
+x
5
+1 6. x
7
+x
5
+x
2
+x+1 23. x
6
+x
4
+x
3
+x+1 7. x
6
+x
5
+x
2
+x+1 8. x
7
+x
5
+x
3
+x+1 24. x
6
+x
5
+x
3
+x+1 9. x
6
+x
5
+x
3
+x
2
+1 10. x
7
+x
5
+x
4
+x
3
+1 25. x
7
+x
4
+x
2
+1 11. x
6
+x
5
+x
4
+x+1 12. x
5
+x
4
+x
2
+x+1 26. x
7
+x
6
+x
3
+x
2
+1 13. x
6
+x
5
+x
4
+x
2
+1 14. x
5
+x
4
+x
3
+x+1 27. x
7
+x
5
+x
4
+1 15. x
5
+x
3
+x
2
+x+1 16. x
5
+x
4
+x
3
+x
2
+1 28. x
5
+x
3
+x+1 17. x
6
+х
2
+x+1 18. x
7
+x
3
+1 29. x
7
+x
4
+1 19. x
6
+x
3
+1 20. x
7
+x
3
+x
2
+1 30. x
6
+x
4
+1
Утворюючі поліноми (для студентів заочної форми навчання)
Варіант
Поліном L(x) Варіант
Поліном L(x)
1. x
5
+x
3
+x
2
+x+1 11. x
5
+x
4
+x
3
+x
2
+1 2. x
5
+x
4
+x
3
+x+1 12. x
6
+x
5
+1 3. x
7
+x
5
+x
2
+x+1 13. x
6
+x
5
+x
2
+х+1 4. x
6
+x
4
+1 14. x
6
+x
3
+x
2
+1 5. x
6
+x
2
+1 15. x
5
+x
4
+1 6. x
5
+x
3
+1 16. x
5
+x
2
+1 7. x
4
+x
2
+x+1 17. x
4
+x
2
+1 8. x
4
+x
3
+1 18. x
3
+x+1 9. x
3
+x
2
+1 19. x
7
+x
3
+1 10. x
6
+x+1 20. x
6
+x+x
2
+1