Matematyka.pl

Hej. Czy mógłby ktoś zerknąć i ocenić, czy wgl rozumiem o co w tym chodzi? Pierwsze moje zadanie tego rodzaju.

Zaprojektować układ przepuszczający na wyjście pierwszą z lewej gruppę jedynek z n-bitowego słowa wejściowego.

Przykład 1
We: 001101001110110100011
Wy: 001100000000000000000

Przykład 2
We: 000011110011101101001
Wy: 000011110000000000000

Moje rozwiązanie(iteracyjnie):

Przeniesienia od lewej do prawej.
Wejście:
\(\displaystyle{ x _{i}}\) - bit wejściowy
oraz przeniesienia:
\(\displaystyle{ p _{i}}\) - czy szukana grupa już była
\(\displaystyle{ q _{i}}\) - czy znajduję się w szukanej grupie

Wyjście:
\(\displaystyle{ y_{i}}\) - bit wyjściowy
\(\displaystyle{ p _{i+1}}\)
\(\displaystyle{ q _{i+1}}\)

\(\displaystyle{ p _{i}}\) =0 - grupa już była
\(\displaystyle{ p _{i}}\) =1 - grupy nie było
\(\displaystyle{ q _{i}}\) =0 - jestem w grupie(lub tuż za nią)
\(\displaystyle{ q _{i}}\) =1 - jestem poza grupą



\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|c|c|c}
\hline
x _{i} & p _{i} & q _{i} & p _{i+1} & q _{i+1} & y _{i} \\ \hline

0 & 0 & 0 & 0 & 0 & 0 \\ \hline
1 & 0 & 0 & 1 & 1 & 1 \\ \hline
0 & 0 & 1 & 0 & 1 & 0 \\ \hline
1 & 1 & 0 & x & x & x \\ \hline
1 & 0 & 1 & 0 & 1 & 0 \\ \hline
0 & 1 & 0 & x & x & x \\ \hline
0 & 1 & 1 & 0 & 1 & 0 \\ \hline
1 & 1 & 1 & 1 & 1 & 1 \\ \hline

\end{tabular}}\)

Tabele funkcji wyjściowych:



\(\displaystyle{ q_{i+1} = x_{i} * ( q_{i} + p_{i} )

p_{i+1} = p_{i} + x_{i}

y_{i} = x_{i} * ( q_{i} + p_{i} )}\)

aga2210 pisze:\(\displaystyle{ q_{i+1} = x_{i} * ( q_{i} + p_{i} )\\
p_{i+1} = p_{i} + x_{i}\\
y_{i} = x_{i} * ( q_{i} + p_{i} )}\)

Nie jestem w tym specjalnie mocny ale jakoś automat o takich równaniach nie chce tak działać jak w treści zadania tego oczekują.

Druga sprawa co najmniej pierwsza funkcja przejścia \(\displaystyle{ q_{i+1} = \delta_{1}(x_{i}, q_{i}, p_{i})}\) jest nieprawidłowo zminimalizowana.

Zgodnie z tabelą analizujemy np. taką sekwencję:

aga2210 pisze: \(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|c|c|c}
\hline
x _{i} & p _{i} & q _{i} & y _{i} \\ \hline

0 & 1 & 1 & 0 \\ \hline
0 & 0 & 1 & 0 \\ \hline
1 & 0 & 1 & 0 \\ \hline
1 & 0 & 1 & 0 \\ \hline
0 & 0 & 1 & 0 \\ \hline
\end{tabular}}\)

Jak widać nie działa.... a przecież stan początkowy w powyższej sekwencji:
\(\displaystyle{ p _{i} =1}\) - grupy nie było
\(\displaystyle{ q _{i} =1}\) - jestem poza grupą
oznacza że na ową grupę jedynek oczekujemy, czy tak?
"Po drodze" jednak się taka grupa pojawiła... i nic!.-- 17 lut 2014, o 00:06 --Można zaproponować automat o zmiennych stanu \(\displaystyle{ p}\), \(\displaystyle{ q}\), którego działanie widać na poniższej sekwencji:

\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|c|c|c}
\hline
x _{i} & p _{i} & q _{i} & y _{i} \\ \hline
0 & 0 & 0 & 0\\ \hline
0 & 0 & 0 & 0\\ \hline
1 & 0 & 0 & 1\\ \hline
1 & 1 & 0 & 1\\ \hline
0 & 1 & 0 & 0\\ \hline
0 & 0 & 1 & 0\\ \hline
1 & 0 & 1 & 0\\ \hline
1 & 1 & 1 & 0\\ \hline
1 & 1 & 1 & 0\\ \hline
0 & 1 & 1 & 0\\ \hline
1 & 1 & 1 & 0\\ \hline
\end{tabular}}\)

jestem początkująca. Jak mogę sprawdzić czy mój automat będzie działał?

Gdy tak na to patrzę... to chyba popełniłam błąd przy przepisywaniu, wartosci powinny być odwrotnie:

p _{i} =1 - grupa już była
p _{i} =0 - grupy nie było

Wtedy wydaje mi się że ww sekwencja już działa, prawda?

aga2210 pisze:Gdy tak na to patrzę... to chyba popełniłam błąd przy przepisywaniu, wartosci powinny być odwrotnie:

p _{i} =1 - grupa już była
p _{i} =0 - grupy nie było

Wtedy wydaje mi się że ww sekwencja już działa, prawda?

Niestety jakoś nie chce działać. Sama sprawdź. No chyba, że źle zmodyfikowałem tabelę funkcji przejść i wyjść wg wyżej podanych przez Ciebie wskazówek.

aga2210 pisze:jestem początkująca. Jak mogę sprawdzić czy mój automat będzie działał?

Można to sprawdzić analizując tabelę przedstawiającą funkcję przejść i wyjść automatu. Ta tabela może się wydawać mało czytelna na początku. Zawsze można narysować odpowiadający tej tabeli graf. Tam widać lepiej jak automat działa. Widać, że automat pod wpływem odpowiednich zmian sygnałów wejściowych przechodzi z jednego stanu wewnętrznego w drugi i wystawia odpowiednie wartości sygnałów wyjściowych, w zależności od tego w jakim stanie wewnętrznym się aktualnie znajduje i co aktualnie "czyta" na swoich wejściach. Jeśli analizujemy odpowiedź takiego automatu na pewne zadane sygnały wejściowe to trzeba mieć świadomość, że kolejne stany wewnętrzne, w jakich będzie się znajdował nasz analizowany automat, będą tylko sekwencją skończonej ilości takich zmian stanów, które są określone w tablicy przejść-wyjść (lub na odpowiadającym jej grafie).

Weźmy na przykład automat o następującej tablicy przejść-wyjść:

\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|c|c|c}
\hline
x _{i} & p _{i} & q _{i} & p _{i+1} & q _{i+1} & y _{i} \\ \hline

0&0&0&0&0&0\\ \hline
0&0&1&0&1&0\\ \hline
0&1&0&0&1&0\\ \hline
0&1&1&1&1&0\\ \hline
1&0&0&1&0&1\\ \hline
1&0&1&1&1&0\\ \hline
1&1&0&1&0&1\\ \hline
1&1&1&0&0&0\\ \hline

\end{tabular}}\)

Spróbuj napisać jakie będą kolejne wartości sygnału wyjściowego i stany wewnętrzne tego automatu przy stanie początkowym: \(\displaystyle{ p=0, \ q=0}\) i przy następującej sekwencji na wejściu: \(\displaystyle{ x: 0,0,1,1,0,0,1,1,1,0,1}\), czyli po prostu uzupełnij tabelę:

\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|c|c|c}
\hline
x _{i} & p _{i} & q _{i} & y _{i} \\ \hline
0 & 0 & 0 & 0\\ \hline
0 & 0 & 0 & 0\\ \hline
1 & 0 & 0 & \\ \hline
1 & & & \\ \hline
0 & & & \\ \hline
0 & & & \\ \hline
1 & & & \\ \hline
1 & & & \\ \hline
1 & & & \\ \hline
0 & & & \\ \hline
1 & & & \\ \hline
\end{tabular}}\)
Trochę tabeli na początku wypełniłem.
To jest ważne ćwiczenie pozwalające uzmysłowić sobie jaka jest relacja pomiędzy tablicą przejść-wyjść automatu a odpowiedzią automatu (zachowaniem automatu) na konkretną sekwencję stanów sygnału wejściowego. Takie ćwiczenie jest po to:
1) by poczuć co to takiego automat,
2) by na podstawie takich przykładowych zachowań jak te poniżej

Przykład 1
We: 001101001110110100011
Wy: 001100000000000000000

Przykład 2
We: 000011110011101101001
Wy: 000011110000000000000

umieć skonstruować poprawną tablicę przejść-wyjść automatu, czyli zaprojektować automat spełniający nasze wymagania.
Nawiasem mówiąc ten przykładowy automat jest bardzo "bliski" automatowi spełniającemu wymagania z Twojego zadania. Znajdź "byka" a będziesz miała rozwiązanie swojego zadania.

Szczerze chciałbym pomóc, aczkolwiek nie wiem co to jest gruppa.

zrobiłam od początku i działa przy przepisywaniu zamieniłam p i q w trabeli... ito była główna przyczyna. dzięki za pomoc