Scribd Logo
Upload

Welcome to Scribd!

  • 86 views

    Q1

    Uploaded by

    Danny Adonis
    This document discusses synchronous sequential circuits and iterative networks. It presents three problems involving synchronous circuits: 1) Problem 9.14 asks to find a minimal expression for the combinational circuit of a given synchronous circuit that produces a periodic output sequence. 2) Problem 9.15 involves a transmitter and receiver machine, where the receiver must decode messages sent by the transmitter. It asks to determine the receiver state diagram and which message bits can be uniquely decoded. 3) Problem 9.16 asks for the finite-state control of a Turing machine that can detect arbitrarily long palindromes by comparing symbols on a tape marked with numbers and blanks.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Q1

    Uploaded by

    Danny Adonis
    86 views2 pages
    This document discusses synchronous sequential circuits and iterative networks. It presents three problems involving synchronous circuits: 1) Problem 9.14 asks to find a minimal expression for the combinational circuit of a given synchronous circuit that produces a periodic output sequence. 2) Problem 9.15 involves a transmitter and receiver machine, where the receiver must decode messages sent by the transmitter. It asks to determine the receiver state diagram and which message bits can be uniquely decoded. 3) Problem 9.16 asks for the finite-state control of a Turing machine that can detect arbitrarily long palindromes by comparing symbols on a tape marked with numbers and blanks.

    Original Description:

    paper

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses synchronous sequential circuits and iterative networks. It presents three problems involving synchronous circuits: 1) Problem 9.14 asks to find a minimal expression for the combinational circuit of a given synchronous circuit that produces a periodic output sequence. 2) Problem 9.15 involves a transmitter and receiver machine, where the receiver must decode messages sent by the transmitter. It asks to determine the receiver state diagram and which message bits can be uniquely decoded. 3) Problem 9.16 asks for the finite-state control of a Turing machine that can detect arbitrarily long palindromes by comparing symbols on a tape marked with numbers and blanks.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    86 views2 pages

    Q1

    Uploaded by

    Danny Adonis
    This document discusses synchronous sequential circuits and iterative networks. It presents three problems involving synchronous circuits: 1) Problem 9.14 asks to find a minimal expression for the combinational circuit of a given synchronous circuit that produces a periodic output sequence. 2) Problem 9.15 involves a transmitter and receiver machine, where the receiver must decode messages sent by the transmitter. It asks to determine the receiver state diagram and which message bits can be uniquely decoded. 3) Problem 9.16 asks for the finite-state control of a Turing machine that can detect arbitrarily long palindromes by comparing symbols on a tape marked with numbers and blanks.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    304

    Introduction to synchronous sequential circuits and iterative networks

    Fig. P9.13

    t = 0 1 2 3 4 5 6 7 8 9 10 11 12
    x (t ) = 0 1 1 1 0 0 1 1 0 0 0 1 0
    z (t ) = 0 1 1 1 0 0 0 1 0 0 0 1 1
    (a)

    (b)

    (a )

    Problem 9.14. The synchronous circuit shown in Fig. P9.14, where D denotes a
    unit delay, produces a periodic binary output sequence. Assume that initially x1 = 1,
    x2 = 1, x3 = 0, x4 = 0 and that the initial output sequence is 1100101000. Thereafter,
    this sequence repeats itself. Find a minimal expression for the combinational circuit
    f (x1 , x2 , x3 , x4 ).

    x4

    x3

    x2

    x1

    Output

    f (x1, x2, x3, x4)


    Fig. P9.14

    Problem 9.15. A synchronous machine N is part of a transmitter and is used to encode


    binary serial messages. The coded messages are then transmitted to a receiver, as shown
    in Fig. P9.l5. The receiver contains a synchronous machine M that is used to decode
    the received messages.
    (a) Given that the initial state of N is A, nd the state diagram of machine M.
    (b) Suppose the initial state of N is unknown and machine M received a 10bit message; which of the 10 bits can be uniquely decoded without an error?
    Explain.

    Original
    message

    1/1

    1/0

    0/0

    Coded
    message

    Received
    message

    Original
    message

    0/1
    Transmitter, N

    Receiver, M

    Fig. P9.15

    Problem 9.16. A palindrome is a sequence which reads the same backward as forward,
    e.g., 11011 or 01010. Show the nite-state control of a Turing machine that is capable
    of detecting arbitrarily long palindromes. Assume that you are given a tape initially
    marked only with symbols #, 0, 1, where the blanks (#) separate blocks of intermixed
    0s and 1s. The machine will be started on a # and then checks whether the sequence
    to its right is a palindrome. If not, the machine should proceed to the next block. If the
    sequence is a palindrome, the machine should stop at the # to the right of the block. An
    example is shown in Fig. P9.16.

    PS
    A
    B
    C
    D
    E
    F

    N S, z
    x=0 x=1
    A, 0
    B, 1
    A, 1
    C, 1
    A, 1
    D, 1
    E, 0
    D, 1
    F, 0
    D, 0
    A, 0
    D, 0

    9.15.
    1/1

    0/0

    0/1
    B

    1/0
    Machine M

    (b) An output of 0 from machine N identies the nal state as B, while an output of 1 identies the
    nal state as A. Once the state of N is known, it is straightforward to determine the input to N and
    the state to which N goes by observing its output. Consequently, except for the rst bit, each of the
    subsequent bits can be decoded.
    9.16. A simple strategy can be employed here whereby the head moves back and forth across the block
    comparing the end symbols and, whenever they are identical, replacing them with 2s and 3s (for 0s
    and 1s, respectively). At the end of the computation, the original symbols are restored.

    PS
    A
    B
    C
    D
    E
    F
    G
    H
    I
    I
    Halt

    #
    B, #, R
    E, #, L
    F, #, L

    A, #, R
    J, #, R
    Halt
    Halt

    N S, write, shif t
    1
    2
    A, 1, R A, 0, R
    D, 3, R I, 2, L
    C, 1, R E, 2, L
    D, 1, R F, 2, L
    H, 1, L I, 2, L
    G, 3, L
    G, 1, L B, 2, R
    H, 1, L H, 2, L
    I, 1, L
    I, 2, L
    J, 1, R J, 0, R
    Halt

    0
    A, 0, R
    C, 2, R
    C, 0, R
    D, 0, R
    G, 2, L
    H, 0, L
    G, 0, L
    H, 0, L
    I, 0, L
    J, 0, R
    Halt

    3
    A, 1, R
    I, 3, L
    E, 3, L
    F, 3, L
    I, 3, L
    B, 3, R
    H, 3, L
    I, 3, L
    J, 1, R

    state A. Starting state. The machine restores the original symbols of the present block and moves to
    test the next block.
    state B. (columns 0,1): The head checks the leftmost original symbol of the block.
    (columns 2,3): A palindrome has been detected.

    45

    You might also like