ElectricalSystemsDesign(ELX304)

Part1Synchronoussequentialdesign

PART1

SYNCHRONOUSSEQUENTIAL
DESIGN

UniversityofSunderland

Page1

ElectricalSystemsDesign(ELX304)

Page2

Part1Synchronoussequentialdesign

UniversityofSunderland

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

LESSON1

SYNCHRONOUSDESIGN
CONCEPTS
INTRODUCTION
ALevel2moduleintroducedthedesignofsynchronouscounters.
Thislessonrevisestheseconceptsandextendsthemitdiscusses
thegeneral structureofsynchronoussystems,butrestricts
considerationtocounterbasedexamples.

YOURAIMS
Attheendofthislesson,youshould:
haverevisedthematerialonsynchronouscounters
designedseveralformsofsynchronouscounters.

STUDYADVICE
Thereferencesbelowbothtacklethesubjectwellthefirstis
probablyeasiertofollow.

SUPPORTMATERIAL
Mano,M.Morris(2001)DigitalDesign. 3rded. PrenticeHall
(Chapter6)
Lewin,D.& Protheroe,D.(1992) DesignofLogicSystem.
Chapman&Hall.(Chapters6& 7)

UniversityofSunderland

Page3

ElectronicSystemDesign(ELX304)

Page4

Lesson1SynchronousDesignConcepts

UniversityofSunderland

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

1.1 INTRODUCTIONTOSEQUENTIALDESIGN
Sequentialdesigninvolvestheideaofdevelopingcircuitsto
performaspecificfunctionwhenaparticularsequenceofinput
changesoccurs.Sequentialdesigncanbeeithersynchronousor
asynchronous.Intheformerthecircuitonlyrespondswhena
clocksignalispresentinthelatter,discussedinPart2ofthese
notes,thecircuitrespondstoinputchangesimmediately.The
detectionofasequencedemandssomeformofmemory,andthe
basisof synchronousdesignistheclockedFlipflop.

INTEXTQUESTION
Whichsystemdoyouthinkisfaster:synchronousorasynchronous?Andwhichistheharder
todesign?

ANSWER
Asynchronousisfaster,becauseitdoesntwaitforaclocksignal,andasynchronousisalso
hardertodesign,becausetheremaybenosettlingtimebetweeninputchanges.

AtLevel2welearntthebasicapplicationofFlipflopstocounters
andregisters.Synchronousdesignusesasitsbasicbuildingblock
theclockedFlipflop.Whenacircuitisunderclockcontrolall
changesoccurwhenaclockpulseisapplied.Ingeneral,Flip
flopscanbeedgetriggered,i.e.outputchangestakeplaceduring
aclockpulsetransitionfrom0to1(rising)or1to0(falling),or
leveltriggeredwhenoutputchangestakeplacewhentheclockis
inacertainstate.Theadvantageoverasynchronousprocessesis
thatthereistimeforthecircuittosettledowntoastablecondition
beforethenextclockpulse.

UniversityofSunderland

Page5

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

1.2 FLIPFLOPTYPES
ThisisessentiallyarevisionofworkfromLevel2.

1.2.1

SRFLIPFLOP
A

Ck
B
R

Figure1.1
ChangescantakeplacewhentheclockCk=1.NoteifS=R=1
then,whenCkgoesfrom1to0,theoutputsAandBbothgofrom
0to1simultaneously.ThereforetheoutputsQand Q willbe
determinedbysmalldifferencesinpropagationdelayswithinthe
gates.Thisisclearlyunsatisfactory,sowhenusingthistypeof
Flipfloponeshouldensurethatthiscondition(S=R=1)does
notoccur.ThetruthtableforthisFlipflopisshowninTable1.1.

S
0
0
1
1

R
0
1
0
1

Qn+1
Qn
0
1
?

Table1.1

Qn isthestateoftheFlipflopbeforetheClockpulseQn+1isthe
stateafter theClockpulse.

Page6

UniversityofSunderland

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

1.2.2

MASTERSLAVEJKFLIPFLOP

Preset
J

Q
MASTER

SLAVE

Q
Clear

Ck
Figure1.2

InthisFlipfloptheproblemoftheS=R=1inputcombinationis
avoided.ThetruthtableisshowninTable1.2.Inthiscase,Flip
flopdataiscapturedbytheMastersectionwhenCkis1and
transferredtotheSlaveoutputwhenCk=0.WhenJ=K=1,the
feedbackfromtheoutputscausestheoutputstochangeatthenext
clockpulse.
ProvetheTruthTable!
J
0
0
1
1

K
0
1
0
1

Qn+1
Qn
0
1
Qn

Table1.2

AdditionalfacilitiesareprovidedbythePresetandClearinputs.
Normallythesearesetto1.However,theoutputQcanbePreset
asynchronously(i.e.Ck=0)to1byputtingthePresetto0
momentarily,andResetto0byputtingtheClearto0.

UniversityofSunderland

Page7

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

1.2.3

TTYPEFLIPFLOP

AT(oggle)TypeFlipFlopcanbederivedfromaJKby
connectingtheJKinputstogether.SeeFigure1.3andTable1.3.

T
0
1

Ck

Figure1.3

Qn+1
Qn
Qn

Table1.3

InthisFlipflopifT=1theoutputchangeswitheachclockpulse.

1.2.4

DTYPEFLIPFLOP

AD(ata)TypeFlipflopcanbeobtainedfromtheJKbythe
circuitofFigure1.4.ThishasaTruthTableasshowninTable
1.4.InthisFlipflopthedataontheinputistransferredtothe
outputattheclockpulse.ThisiswhythistypeofFlipflopforms
thebasisofShiftRegisters.

Q
J

D
0
1

Ck
K

Figure1.4

Page8

Qn+1
0
1

UniversityofSunderland

Table1.4

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

1.3 GENERALSYNCHRONOUSDESIGN
CONSIDERATIONS
Ourexperienceofsynchronousdesignhassofarbeenconfinedto
thedesignofsynchronouscounters,inwhichtheoutputshave
beentheoutputsoftheFlipflops.Theseoutputshavebeenfed
backviacombinationallogictotheFlipflopinputstodefinethe
nextstateoftheFlipflopsafterthenextClockpulse.
ThemoregeneralsituationinvolvesadditionalexternalINPUTS
andthegenerationofOUTPUTSwhichmaybeafunctionofboth
Flipflopoutputsandtheinputs.Thegeneralstructureisshownin
Figure1.5.

FEEDFORWARD

FLIP
FLOPS

LOGIC

LOGIC

INPUTS

OUTPUTS

FEEDBACK
CLOCK
Figure1.5

AFlipflophastwostates,0and1.HenceNFlipflopscanhave
2N differentoutputcombinations.Acounterwhichcountsfrom0
to9has10states,andthereforeweneed4Flipflopsbecause
23<10<24.Ingeneralwedonotstartadesignknowingthenumber
ofFlipflopsrequired.Thedesignproblemisspecifiedintermsof
itsinputs,outputsandsequenceofoperation.Thenumber(and
type)ofFlipflopsandtheirinterconnectionwithcombinational
logicarisesfromthedesignprocess.
Notethefeedforwardpathsshowninthediagram.Theoutputsare
clearlyadirectfunctionoftheinputs.Normallythisisnotthe
casetheoutputsarefunctionsoftheFlipflopoutputs.

UniversityofSunderland

Page9

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

INTEXTQUESTION
Whywoulditbeundesirabletomaketheoutputsdependentontheinputs?

ANSWER
Because,iftheinputsarenotsynchronous,theoutputsarenotsynchronous.Usually the
feedforwardpathsareonly presentiftheinputscanonlychangesynchronously.

1.4 SYNCHRONOUSCOUNTERDESIGN
EXAMPLE
1.4.1

PROBLEMSTATEMENT

Wewillcommenceourinvestigationsbydesigningasimple
synchronouscounter.Itwillcountcontinuouslyfrom0to5.
Obviously,therearenoinputsinthissituationandtheoutputsare
theFlipflopoutputs.Thedesignprocessgoesthroughanumber
ofstages:

1.4.2

STATEDIAGRAM

FromtheproblemstatementweconstructaSTATEDIAGRAM
asshownbelowinFigure1.6.Usuallythestudentfindsthistobe
thehardeststep.
A
000

B
001

C
010

F
101

E
100

D
011

Figure1.6

Eachstateisshownbyacircle,andidentifiedbyaletterAtoF.
Thearrowsshowthetransitionsfromstatetostate,i.e.itisa
definedsequence.Therequiredoutputsarealsoshowninsidethe
statecircle.

Page10

UniversityofSunderland

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

1.4.3

STATETABLE

TheinformationcontainedintheStateDiagramistransferredtoa
StateTable,asshowninTable1.5.
PresentState
A
B
C
D
E
F

Nextstate
B
C
D
E
F
A

PresentOutput
000
001
010
011
100
101

Table1.5

1.4.4

FLIPFLOPCHOICE

INTEXTQUESTION
HowmanyFlipflopsdoweneed?

ANSWER
Inthiscase3.ThreeFlipflopsgiveusupto8differentstates,sowehavetwospare.

WhatkindofFlipflopshouldwechoose?Well,itcouldbeanyof
thefour.Infactwecouldhaveamixture,butthatwouldhardlybe
sensible.Ingeneralthefollowingconsiderationsapply.
JK:Almostalwaysleadstothesimplestcircuit,butis
complicated,soisbestutilisedforsmallproblems.
SR:AverysimpleFlipflopstructurally,butbecausewemust
takecarenevertoletS=R=1,thelogictendstobemore
complex.
D:Usedinregistersandinconjunctionwithprogrammable
logic,becauseitissuitableforuseinarrays.
T:Oftenusedforsimplecounters,asynchronousaswellas
synchronous.
WeshallusetheTTypeinthisexample.

UniversityofSunderland

Page11

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

1.4.5

STATEASSIGNMENT

AtanyonetimethestateofthecircuitisdefinedbytheFlipflop
outputs.Thereare6states,andsowehavetochoosesix3bit
assignmentstorepresentthestatesAtoF.Thenumberofpossible
stateassignmentsisverylarge:

(2 ) !
(2 - S) !
N

Sa =
Sa
N
S

isthenumberofstateassignments
isthenumberofFlipflops
isthenumberofstates

InthiscaseN=3andS=6,soSa=20160
Althoughanumberofstateassignmentswillleadtocircuitsofthe
samecomplexity,theywillallbedifferent.Selectingagoodstate
assignmentisaproblemwhichisaddressedinalaterlesson.
Inthisexample,theobviousstateassignmentisonewhichgives
therequiredoutputs,i.e.
A=000
B=001
C=010
D=011
E=100
F=101

1.4.6

EXCITATIONTABLE

WenowhavetoconverttheSTATETABLEtoanEXCITATION
TABLE,wherewedefinewhatTinputsarerequiredtogenerate
thestatechangeswewant.
ForaTTypeFlipflop,ifwewantitsoutputtochangewemust
putalogic1ontheTinputandifnochangeisrequired,a0is
needed.SeeTable1.6
PresentState NextState
FlipflopInputs
QaQbQc
QaQbQc Ta
Tb
Tc
A
000
B
001
0
0
1
B
001
C
010
0
1
1
C
010
D
011
0
0
1
D
011
E
100
1
1
1
E
100
F
101
0
0
1
F
101
A
000
1
0
1
Table1.6

Page12

UniversityofSunderland

PresentOutput
QaQbQc
000
001
010
011
100
101

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

Aside:
FromtheFlipfloptruthtableswecanderiveChangeTables
whichwillgiveustherequiredinputstocauseadesired
change.Doyouremembertheseandcanyouderivethem?
TType

DType

SRType JKType

CHANGE
0
1
1
0

0 0
0 1
1 0
1 1

1.4.7

SR
0X
10
01
X0

0
1
0
1

JK
0X
1X
X1
X0

KARNAUGHMAPS

WenowminimisetheTinputsasfunctionsofthePresentStatein
Kmaps.Notethattherearetwosquaresinthemapswhichare
Dontcares,correspondingtotheunusedstateassignments.
NotethatalltheentriesinthecolumnforTc are1orX,soclearly
wecanwriteTc =1.
QaQb

QaQb
00

01

11

10

Qc

00

01

11

10

Qc

Ta

Tb
Fromthemapstheminimisedfunctionsare:
Ta =Qb.Qc + Qa.Qc = Qc(Qa + Qb )
Tb = Qa.Qc
Tc = 1

UniversityofSunderland

Page13

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

1.4.8

TQ

CIRCUITDIAGRAM

TQ

a
Q

Ck
Figure1.7

1.4.9

UNWANTEDSTATES

InminimisingtheKmaps,wehaveallocated0 and1 valuesto

FlipflopInputs
Ta
Tb
Tc
0
0
1
1
0
1

NextState
QaQbQc
111
010

Table1.7

Soifwestartinstate110,wegotostate111,andwethengoto
state010whichisinthemainsequence.Soafteratmost2clock
pulseswereturntothemainsequenceandstaythere. Thisis
shownbytheStateDiagramshownbelow.
C
000

B
001

C
010

111

F
101

E
100

D
011

110

Figure1.8

Page14

UniversityofSunderland

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

SUMMARY
Thelessonhasrevisedtheconceptsofsynchronouscountersas
developedatLevel2,andhasintroducedtheideaofastate
diagram,afundamentaldesigntool.
Thelessonhasalsohighlightedtheawarenessofcertainproblems
thatcanoccurinsynchronousdesign:
stateassignmentchoice
unwantedstateanalysis
thedifferencebetweenFlipflopoutputsandSystemoutputs.
Someoftheseaspectswillbedevelopedfurtherinsubsequent
lessons.

UniversityofSunderland

Page15

ElectronicSystemDesign(ELX304)

Page16

Lesson1SynchronousDesignConcepts

UniversityofSunderland

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

SELFASSESSMENTQUESTIONS
QUESTION1
Designsynchronouscounterstocountfrom0to5using(a)DType,(b)SRTypeand(c)JK
TypeFlipflops.Ineachcasefollowthedesignprocessoftheexampleintheprevioussection.
Determinewhathappensifyoustartinanunwantedstate.Comparethesolutionsintermsofthe
numbersofgatesrequiredandthenumberofinputstothesegates.
FortheSRandJKFlipflopsyouwillneedtorefertoyourpreviousnotes(orthenextlesson)
todeterminewhatinputsarerequiredtoensureacorrectnextstate.
QUESTION2
DesignasynchronouscircuitusingJKFlipflopswhichwillgiveoutputssequentiallyas
follows:
Ck
1
2
3
4
5
6
7

ABC
000
001
011
111
01 1
001
000

Therearethreeoutputs,buttheycannotbethesameastheFlipflopoutputs!
ThinkaboutthestructureofFigure1.5!
QUESTION3
Fromthecircuitdiagrambelow,findtheequationsforeachinput.Henceforeverypossible
presentoutputstatefindthenextoutputstateandthendevelopageneralisedSTATEDIAGRAM.

JQ

OutputZ

Ck

J
K

Q
2

UniversityofSunderland

Page17

ElectronicSystemDesign(ELX304)

Page18

Lesson1SynchronousDesignConcepts

UniversityofSunderland

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

ANSWERSTOSELFASSESSMENTQUESTIONS
ANSWER1
ApplyingtheChangeTablerulesfortheprobleminquestionwegetacombinedExcitationTable
asshownbelow.
PresentState

NextState

DType

SRType

QaQbQc

QaQbQc

DaDbDc

SaRa SbRb ScRc

JaKa

JbKb

JcKc

000
001
010
011
100
101

001
010
011
100
101
000

001
010
011
100
101
000

0X
0X
0X
10
X0
01

0X
0X
0X
1X
X0
X1

0X
1X
X0
X1
0X
0X

1X
X1
1X
X1
1X
X1

0X
10
X0
01
0X
0X

JKType

10
01
10
01
10
01

UsingKmapstosolvefortheseinputsweget(Kmapsnotincluded):
Da =QbQc + QaQc
Sa = QbQc

Db = QbQc + QaQbQc
Sb = QaQbQc

Dc = Qc
Sc = Qc

Ra = QaQc (or QbQc) Rb = QbQc

Rc = Qc

Ja = QbQc

Jb = QaQc

Jc = 1

Ka = Qc

Kb = Qc

Kc = 1

Usingtheseequationswecanevaluatetheefficiencyofthedesigns:
GATETYPE
T
D
SR
JK

2inputAND
2
3
2
2

3inputAND

1
1

2inputOR
1
2

SotheJKtypeisthemosteconomic.Youmightexpectthisbecauseofthenumberof Xinthe
maps.
NotealsothatfortheJKFlipflopthatJnandKnarenotfunctionsofQn.Thisisausefulcheck
ofthevalidityofyourdesign.
Fortheunwantedstateanalysis,weusetheequationstogeneratenextstatesforthetwo
unwantedstates.

UniversityofSunderland

Page19

ElectronicSystemDesign(ELX304)

Present
State
QaQbQc
110
111

Lesson1SynchronousDesignConcepts

DType Next
State
DaDbDc QaQbQc
111
111
100
100

SRType
SaRa
01
11

SbRb ScRc
00 10
01 01

Next
State
QaQbQc
011
000

JKType
JaKa
00
11

JbKb
00
01

JcKc
11
11

Next
State
QaQbQc
111
000

Sonoundesirablelatchupproblemsoccur.

ANSWER2
ThefirststepistodrawtheStateDiagram.

A
000

B
001

G
000

C
011

F
001

D
111

E
011

Youhavetorealizethatthereare7states!Onecycletakes7clockpulsesthefactthatsome
stateshavethesameoutputsisirrelevant.Forexamplewecouldhaveadecadecounterwhich
givesanoutput1everytenthclockpulse,so9consecutiveclockpulsesrequireoutput0s.The
numberofoutputsdoesnotdependonthenumberofstates.Theimportantthingtorealizeisthat
inthiscasetheFlipflopoutputscannotbethesameasthesystemoutputs.Thisiseasilyseenin
theStateDiagramabove.Thereare7states,butonly4differentoutputconditions.
Thestructureofthesolutionisasshownbelow:
FlipflopOutputs

Outputs

Clock
7STAGECOUNTER

DECODER

Any7stagecounterwilldo!Soitisnotpossibletogiveageneralsolution.Thenaturalmethod
wouldbetocountinordinarybinary,butitiscertainlypossibletocountusinganysequenceof
threebits,e.g.000,001,011,111,110,100,101.
Ifwecountinnormalbinary,labellingtheFlipflops1,2,3, thenwegetthefollowingsolution,
labellingtheoutputsasX,Y,Z.

Page20

UniversityofSunderland

ElectronicSystemDesign(ELX304)

Lesson1SynchronousDesignConcepts

J 1 =Q2Q3

J2 = Q3

J3 = Q1 + Q2

K1 = Q2

K2 = Q1 + Q3 K3 = 1

X = Q2Q3

Y = Q1.Q2 + Q1Q2Q3

Z = Q3 + Q1Q2 + Q1Q2

Isthisthesolutionthatrequirestheminimumnumberofgatesof minimumsize?Probablynot!

ANSWER3
Fromthediagram,writedowntheinputfunctions:
J 1 =Q2 K1 = 1 J2 = 1 K2 = Q1 Z = Q1 + Q2
Nowweconductananalysisessentiallysimilartotheunwantedstateanalysisforacounter,using
theseequationstogenerateFlipflopinputsfromwhichyoucanpredictthenextstate.
PresentState
Q1Q2
00
01
10
11

FlipflopInputs
J1K1
01
11
01
11

NextState

J2K2
10
10
11
11

Q1Q2
01
11
01
00

Present
Output
Z
0
1
1
1

Nowlabelthestatesasfollows:A=00,B=01,C=10andD=11.Thisinformationcannow
betransformedintoaStateDiagram.

A
0

B
1

D
1

C
1

UniversityofSunderland

Page21

ElectronicSystemDesign(ELX304)

Page22

Lesson1SynchronousDesignConcepts

UniversityofSunderland