2016 [11] Защитный блок
Промышленная установка управляется по 4-разрядной шине данных. Команды по ней передаются последовательно. Для удобства записи будем интерпретировать их как символы в алфавите 0,1,2,..,9,A,B,C,D,E,F.
Известно, что некоторые цепочки команд приводят к поломке установки. Поэтому на шине планируется установить защитный блок, исправляющий такие цепочки на безопасные. Логика работы защитного блока определяется двумя таблицами. Первая из них определяет следующую активную строку в зависимости от входного символа и текущей активной строки (функция переходов). Вторая таблица определяет, что появится на выходе защитного блока в зависимости от входного символа и текущей активной строки (функция выходов). В начальный момент времени активна строка с номером 0. Фрагмент кода функции работы защитного блока приведен ниже.
Паскаль
|
Си
|
type matrix=
array[1..n,1..m] of
integer;
function GetOutput(
StateMas : matrix;
OutMas : matrix;
InSymb : integer;
var CurState:integer):
integer;
var
NewState:integer;
OutSymb:integer;
begin
NewState :=
StateMas[CurState]
[InSymb];
OutSymb :=
OutMas[CurState]
[InSymb];
CurState := NewState;
result := OutSymb;
end;
|
int GetOutput(
int **StateMas,
int **OutMas,
int InSymb,
int& CurState)
// StateMas –таблица(матрица) переходов
// OutMas – таблица(матрица) выходов
// InSymb – входной символ
// CurState – текущее состояние (меняется в результате выполнения функции)
// RETURN – выходной символ
{
int NewState;
int OutSymb;
NewState =
StateMas[CurState]
[InSymb];
OutSymb =
OutMas[CurState]
[InSymb];
CurState = NewState;
return OutSymb;
}
|
Настройте защитный блок таким образом, чтобы он пропускал все команды, кроме запрещенных, вместо которых на выходе должна появиться безопасная выходная последовательность (см. таблицу).
Запрещенная входная
последовательность
|
Выходная последовательность
|
FA0B
|
FA01
|
10F1
|
10FA
|
Результат выполнения задачи – файл с прошивкой защитного блока.
Комментарий. К задаче прилагается: программа обучения и тестирования защитного блока.
Показать решение
Защитный блок устроен следующим образом: при подаче на вход символа выполняется две операции:
-
- по функции выходов определяется, какой символ будет на выходе. Он зависит от текущего активного состояния (выделенная строка в таблице выходов) и подданного на вход символа (столбец в таблице выходов). Значение ячейки на пересечении строки и столбца – это и есть выходной символ;
-
- по функции переходов определяется новое активное состояние. Оно зависит от текущего активного состояния (выделенная строка в таблице переходов) и подданного на вход символа (столбец в таблице переходов). Значение ячейки на пересечении строки и столбца – это и есть номер нового активного состояния.
По таблицам переходов и выходов видно, что алфавит составляет 16 символов (16 столбцов), и число состояний равно 16 (16 строк в таблице). Изначально активным считается состояние 0.
Чтобы определить последовательность входных символов необходимо следующее:
-
- при подаче очередного символа последовательности изменять активное состояние;
-
- при подаче символа не из последовательности сбрасывать активное состояние в начальное.
Чтобы изменить последний символ последовательности необходимо следующее:
-
- определить, что предыдущие символы принадлежат искомой последовательности;
-
- при подаче на вход последнего символа последовательности изменить выходной символ в таблице выходов.
Поскольку всего возможно 16 состояний, то максимум такой блок может отслеживать последовательность длиной 16 символов. По условию требуется две последовательности длиной 4 символа. Предлагается выделить состояния 0-3 для последовательности FA0B и состояния 5-8 для последовательности 10F1:
-
- состояние 0 – не введена никакая последовательность;
-
- состояние 1 – введена последовательность F;
-
- состояние 2 – введена последовательность FA;
-
- состояние 3 – введена последовательность FA0;
-
- состояние 4 – введена последовательность FA0B;
-
- состояние 5 – введена последовательность 1;
- состояние 6 – введена последовательность 10;
-
- состояние 7 – введена последовательность 10F;
-
- состояние 8 – введена последовательность 10F1.
Замена последовательности FA0B на FA01
-
1. При подаче на вход первого символа F необходимо перейти из любого состояния в состояние 1. Для этого в таблице переходов необходимо заменить ячейки:
StateMas[i][F] = 1, i = 0,1,...,F, кроме i=6.
-
2. Если на вход подается символом A и активным является состояние 1 (ввод символа F), значит это продолжение последовательности и необходимо перейти в состояние 2. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[1][A] = 2.
Остальные незадействованные ячейки в строке 1 должны быть равны 0.
-
3. Если на вход подается символом 0 и активным является состояние 2 (ввод символов FA), значит это продолжение последовательности и необходимо перейти в состояние 3. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[2][0] = 3.
Остальные незадействованные ячейки в строке 2 должны быть равны 0.
-
4. Если на вход подается символом B и активным является состояние 3 (ввод символов FA0), значит это окончание последовательности и необходимо перейти в состояние 4 либо в состояние 0. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[3][B] = 4.
Остальные незадействованные ячейки в строке 3 должны быть равны 0.
Кроме того, необходимо изменить выходной символ B->1. Для этого необходимо изменить ячейку в таблице выходов:
OutMas[3][B] = 1.
Замена последовательности 10F1 на 10FA
-
1. При подаче на вход первого символа 1 необходимо перейти из любого состояния в состояние 5. Для этого в таблице переходов необходимо заменить ячейки:
StateMas[i][1] = 5, i = 0,1,...,F, кроме i = 7.
-
2. Если на вход подается символом 0 и активным является состояние 5 (ввод символа 1), значит это продолжение последовательности и необходимо перейти в состояние 6. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[5][0] = 6.
Остальные незадействованные ячейки в строке 5 должны быть равны 0.
-
3. Если на вход подается символом F и активным является состояние 6 (ввод символов 10), значит это продолжение последовательности и необходимо перейти в состояние 7. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[6][F] = 7.
Остальные незадействованные ячейки в строке 6 должны быть равны 0.
-
4. Если на вход подается символом A и активным является состояние 7 (ввод символов 10F), значит это окончание последовательности и необходимо перейти в состояние 8 либо в состояние 0. Для этого в таблице переходов необходимо заменить ячейку:
StateMas[7][A] = 8.
Остальные незадействованные ячейки в строке 7 должны быть равны 0.
Кроме того, необходимо изменить выходной символ 1->A. Для этого необходимо изменить ячейку в таблице выходов:
OutMas[7][1] = A.
Показать ответ
См. Решение
<< Назад в раздел (Все задания)