Giáo trình kỹ thuật số - Phần 3 Mạch dãy - Chương 11

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

165
lượt xem 38
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mạch dãy đồng bộ Mạch dãy đồng bộ là một mạch số bao gồm các mạch tổ hợp và các phần tử nhớ FF, mạch hoạt động theo sự đồng bộ của xung nhịp Ck. I. Phân tích Bài toán phân tích là bài toán xác định chức năng cho tr-ớc; - Sơ đồ mạch: Từ sơ đồ mạch cho tr-ớc cần xác định chức năng từng phần tử cơ bản của sơ đồ, và mối liên hệ giữa các sơ đồ đó - Xác định đầu vào, đầu ra, số trạng thái trong của mạch: Coi mạch nh-...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình kỹ thuật số - Phần 3 Mạch dãy - Chương 11

BomonKTDT-§HGTVT Ch−¬ng 11 M¹ch d∙y ®ång bé M¹ch d·y ®ång bé lµ mét m¹ch sè bao gåm c¸c m¹ch tæ hîp vµ c¸c phÇn tö nhí FF, m¹ch ho¹t ®éng theo sù ®ång bé cña xung nhÞp Ck. I. Ph©n tÝch Bµi to¸n ph©n tÝch lµ bµi to¸n x¸c ®Þnh chøc n¨ng cho tr−íc; - S¬ ®å m¹ch: Tõ s¬ ®å m¹ch cho tr−íc cÇn x¸c ®Þnh chøc n¨ng tõng phÇn tö c¬ b¶n cña s¬ ®å, vµ mèi liªn hÖ gi÷a c¸c s¬ ®å ®ã - X¸c ®Þnh ®Çu vµo, ®Çu ra, sè tr¹ng th¸i trong cña m¹ch: Coi m¹ch nh− mét hép ®en, cÇn ph¶i x¸c ®Þnh sè ®Çu vµo, ®Çu ra, ®Æc ®iÓm c¸c ®Çu vµo ra, x¸c ®Þnh tr¹ng th¸i cña m¹ch - X¸c ®Þnh ph−¬ng tr×nh hµm ra, hµm kÝch cho c¸c FF Dùa vµo s¬ ®å cho tr−íc x¸c ®Þnh hÖ ph−¬ng tr×nh hµm ra, hµm kÝch cho c¸c FF - LËp b¶ng tr¹ng th¸i, b¶ng ra nhÞ ph©n: B¶ng tr¹ng th¸i, b¶ng ra nhÞ ph©n lµ b¶ng biÓu diÔn quan hÖ gi÷a tr¹ng th¸i chuyÓn ®Õn, tÝn hiÖu ra nhÞ ph©n víi tr¹ng th¸i hiÖn t¹i vµ tÝn hiÖu vµo t−¬ng øng. Dùa vµo c¸c ph−¬ng tr×nh hµm kÝch, hµm ra x¸c ®Þnh ®−îc ë trªn, vµ dùa vµo ph−¬ng tr×nh ®Æc tÝnh cña FF x¸c ®Þnh ®−îc tr¹ng th¸i chuyÓn tíi vµ tÝn hiÖu ra t−¬ng øng víi tÝn hiÖu vµo vµ tr¹ng th¸i hiÖn t¹i cña m¹ch. - §å h×nh tr¹ng th¸i: Tõ b¶ng tr¹ng th¸i vµ b¶ng ra ®· lËp ë trªn, x©y dùng ®−îc ®å h×nh tr¹ng th¸i vµ tÝn hiÖu ra cña m¹ch. - Chøc n¨ng cña m¹ch: Sau khi lËp ®−îc ®å h×nh tr¹ng th¸i, dùa vµo ®å h×nh ®ã x¸c ®Þnh ®−îc chøc n¨ng cña m¹ch. Cô thÓ lµ tõ sù ph©n tÝch ®ã mµ rót ra ®−îc chøc n¨ng cña m¹ch. II. ThiÕt kÕ 1. C¸c b−íc thiÕt kÕ: C¸c b−íc thiÕt kÕ ng−îc l¹i víi c¸c b−íc ph©n tÝch, tuy nhiªn m¹ch thiÕt kÕ ph¶i thùc hiÖn chøc n¨ng cho tr−íc víi s¬ ®å cµng ®¬n gi¶n cµng tèt, ®iÒu nµy ®ång nghÜa víi viÖc tèi thiÓu ho¸ tr¹ng th¸i. - B−íc 1: X¸c ®Þnh bµi to¸n §©y lµ b−íc ®Çu tiªn vµ còng lµ b−íc quan träng ®Ó thùc hiÖn tèt viÖc thiÕt kÕ m¹ch, tr−íc tiªn ph¶i x¸c ®Þnh ®−îc yªu cÇu ®Æt ra cho m¹ch vµ ph¶i x¸c ®Þnh m¹ch ®−îc thiÕt kÕ tõ nh÷ng yÕu tè nµo? - B−íc 2: X¸c ®Þnh tÝn hiÖu vµo/ra: X¸c ®Þnh tÝn hiÖu vµo, ra còng nh− ®Æc ®iÓm cña chóng - B−íc 3: X©y dùng ®å h×nh tr¹ng th¸i, b¶ng tr¹ng th¸i, b¶ng tÝn hiÖu ra Nãi chung viÖc x©y ®å h×nh tr¹ng th¸i kh«ng dùa trªn mét quy t¾c nµo, mµ phÇn lín dùa vµo kinh nghiÖm cña ng−êi thùc hiÖn, nh−ng quy t¾c lµ dùa vµo yªu cÇu cña bµi to¸n ®Æt ra(tÝn hiÖu vµo ra ), tõ ®ã lËp ®å h×nh tr¹ng th¸i, x¸c ®Þnh ®−îc ®iÒu kiÖn ®Ó cho m¹ch cã thÓ chuyÓn ®æi tõ tr¹ng th¸i nµy sang tr¹ng th¸i tiÕp theo vµ khi nµo th× m¹ch cho tÝn hiÖu ra. 113
PTH-DTT Tõ ®å h×nh tr¹ng th¸i lËp trªn, x©y dùng b¶ng tr¹ng th¸i vµ b¶ng tÝn hiÖu ra X¸c ®Þnh bµi to¸n X¸c ®Þnh tÝn hiÖu vµo ra §å h×nh tr¹ng th¸i, b¶ng tr¹ng th¸i, b¶ng ra Rót gän tr¹ng th¸i M· ho¸ nhÞ ph©n X¸c ®Þnh hÖ ph−¬ng tr×nh cña m¹ch S¬ ®å m¹ch thùc hiÖn - B−íc 4: Tèi thiÓu ho¸ Nh− ®· biÕt sè tr¹ng th¸i trong cña m¹ch gÇn nh− tØ lÖ víi sè FF ®−îc dïng trong m¹ch, viÖc tèi thiÓu ho¸ tr¹ng th¸i chñ yÕu dùa vµo kh¸i niÖm t−¬ng ®−¬ng, ta sÏ xÐt sau. - B−íc 5: M· ho¸ nhÞ ph©n 114
BomonKTDT-§HGTVT Sau khi tèi thiÓu ho¸ c¸c tr¹ng th¸i, vµ ®−a vµo ®å h×nh tr¹ng th¸i t−¬ng øng, dïng c¸c biÕn nhÞ ph©n ®Ó m· ho¸ cho c¸c tr¹ng th¸i, sè biÕn nhÞ ph©n dïng ®Ó m· ho¸ c¸c tr¹ng th¸i phô thuéc vµo sè tr¹ng th¸i trong. NÕu sè l−îng tr¹ng th¸i trong lµ N, sè l−îng biÕn nhÞ ph©n dïng lµ n, th× n ph¶i tho¶ m·n ®iÒu kiÖn: n≥log2N Cã nhiÒu c¸ch ®Ó m· ho¸ kh¸c nhau, mçi c¸ch cho mét s¬ ®å kh¸c nhau, yªu cÇu ph¶i m· ho¸ sao cho s¬ ®å lµ ®¬n gi¶n nhÊt. - B−íc 6: X¸c ®Þnh hÖ ph−¬ng tr×nh cña m¹ch: Sau khi ®· m· ho¸ ®−îc c¸c tr¹ng th¸i trong cña m¹ch, cã thÓ x¸c ®Þnh hÖ ph−¬ng tr×nh cña m¹ch theo 2 c¸ch: + LËp b¶ng chuyÓn ®æi tr¹ng th¸i vµ tÝn hiÖu ra nhÞ ph©n, tõ ®ã x¸c ®Þnh ®−îc ph−¬ng tr×nh ®Çu vµo kÝch cho c¸c FF vµ ph−¬ng tr×nh cña tÝn hiÖu ra, sau ®ã chóng ta tiÕn hµnh tèi thiÓu ho¸ c¸c ph−¬ng tr×nh ®ã. + Dùa trùc tiÕp vµo ®å h×nh tr¹ng th¸i, viÕt hÖ ph−¬ng tr×nh Ton , Toff cña c¸c FF vµ ph−¬ng tr×nh tÝn hiÖu ra cña m¹ch sau ®ã tiÕn hµnh tèi thiÓu ho¸ hÖ ph−¬ng tr×nh ®ã. - B−íc 7: S¬ ®å m¹ch thùc hiÖn Tõ c¸c ph−¬ng tr×nh ®· x¸c ®Þnh ®−îc ta x©y dùng s¬ ®å m¹ch III. Tèi thiÓu ho¸: NhiÖm vô ®Æt ra cho ng−êi thiÕt kÕ lµ ph¶i ®−a ra m¹ch ho¹t ®éng ®óng chøc n¨ng cho tr−íc, s¬ ®å cµng ®¬n gi¶n cµng tèt, muèn vËy cÇn gi¶m nhá sè trang th¸i trong. ViÖc tèi thiÓu ho¸ chñ yÕu dùa vµo kh¸i niÖm"tr¹ng th¸i t−¬ng ®−¬ng", bµi to¸n tèi thiÓu ho¸ tr¹ng th¸i chÝnh lµ bµi to¸n ®i t×m líp tr¹ng th¸i t−¬ng ®−¬ng lín nhÊt, vµ ®−îc thay b»ng mét tr¹ng th¸i ®¹i diÖn, sè tr¹ng th¸i t−¬ng ®−¬ng chÝnh lµ sè tr¹ng th¸i tèi thiÓu. Cã 3 ph−¬ng ph¸p tèi thiÓu hay dïng: 1, Ph−¬ng ph¸p Caldwell: Ph−¬ng ph¸p nµy ®−îc minh häa qua vÝ dô sau: ThiÕt kÕ mét m¹ch d·y ®ång bé thùc hiÖn nhiÖm vô kiÓm tra d·y tÝn hiÖu vµo ë d¹ng nhÞ ph©n cã ®é dµi b»ng 3 ®−îc ®−a vµo liªn tiÕp ®Çu vµo X, nÕu d·y tÝn hiÖu vµo cã d¹ng 010 huÆc 110 huÆc 111 th× tÝn hiÖu ra Z=1®Ó b¸o hiÖu lµ m¹ch ®· nhËn ®−îc mét trong c¸c d·y tÝn hiÖu vµo ®ã. - B−íc 1: X¸c ®Þnh bµi to¸n M¹ch thiÕt kÕ cã nhiÖm vô ph¸t hiÖn d·y tÝn hiÖu vµo, nÕu d·y tÝn hiÖu vµo cã d¹ng 010, huÆc 011, huÆc 110 huÆc 111 th× Z=1 ®Ó b¸o hiÖu m¹ch ®· nhËn ®−îc mét trong c¸c d·y tÝn hiÖu ®ã. - B−íc 2: X¸c ®Þnh tÝn hiÖu vµo ra M¹ch ph¶i thiÕt kÕ lµ m¹ch ®ång bé, nªn ngoµi ®Çu vµo X cßn cã ®Çu vµo xung nhÞp Ck mét ®Çu tÝn hiÖu ra lµ Z, theo d¹ng s¬ ®å khèi nh− sau: Error! X Z M¹ch logic Ck - B−íc 3: ®å h×nh tr¹ng th¸i, b¶ng tr¹ng th¸i, b¶ng ra: Dùa vµo c¸c yªu cÇu cña tÝn hiÖu vµo, ra lËp ®−îc ®å h×nh chuyÓn tr¹ng th¸i nh− sau: S¬ ®å chuyÓn ®æi tr¹ng th¸i: 115
PTH-DTT S0 000 X CK XCK S1 S2 001 010 XCK XCK X CK X CK S3 011,Z=1 100 110 011,Z=1 S4 S5 S6 XCK XCK XCK XCK X CK X CK X CK X CK Tr¹ng th¸i ban ®Çu lµ S0 : khi tÝn hiÖu vµo lµ XCK m¹ch chuyÓn ®Õn S1, X CK m¹ch chuyÓn ®Õn S2. T−¬ng tù víi tr¹ng th¸i S1, m¹ch sÏ chuyÓn ®Õn S3 khi tÝn hiÖu vµo lµ XCK, m¹ch chuyÓn ®Õn S2 khi tÝn hiÖu vµo lµ X CK T−¬ng tù víi tr¹ng th¸i S2, m¹ch sÏ chuyÓn ®Õn S5 khi tÝn hiÖu vµo lµ XCK, m¹ch chuyÓn ®Õn S2 khi tÝn hiÖu vµo lµ X CK. NÕu m¹ch ë mét trong 4 tr¹ng th¸i S3, S4, S5, S6, khi cã tÝn hiÖu vµo lµ XCK huÆc X CK m¹ch sÏ chuyÓn ®Õn tr¹ng th¸i ban ®Çu S0, vËy khi d·y tÝn hiÖu vµo lµ 110 huÆc 111 ®−êng chuyÓn ®æi tr¹ng th¸i: S0->S1->S3->S0 hay khi d·y tÝn hiÖu vµo lµ 010 huÆc 011 ®−êng S0->S2->S5->S0 th× m¹ch sÏ cho tÝn hiÖu ra Z=1 t¹i thêi ®iÓm cña xung nhÞp thø 3. Víi ®−êng chuyÓn ®æi kh¸c Z=0, tõ ®å h×nh tr¹ng lËp ®−îc b¶ng tr¹ng th¸i nh− b¶ng sau: S' Z S X=0 X=1 X=0 X=1 S0 S2 S1 0 0 S1 S4 S2 0 0 S2 S6 S5 0 0 S3 S0 S0 1 1 S4 S0 S0 0 0 S5 S0 S0 1 1 S6 S0 S0 0 0 - B−íc 4: Tèi thiÓu ho¸ tr¹ng th¸i, ta sÏ dïng ph−¬ng ph¸p Caldwell: + Tr¹ng th¸i t−¬ng ®−¬ng: 116
BomonKTDT-§HGTVT Tr¹ng th¸i Si ®−îc gäi lµ t−¬ng ®−¬ng víi Sj khi vµ chØ khi nÕu lÊy Si vµ Sj lµ 2 tr¹ng th¸i ban ®Çu th× víi mäi tÝn hiÖu vµo cã thÓ cã chóng lu«n lu«n cho tÝn hiÖu ra gièng nhau. NÕu cã nhiÒu tr¹ng th¸i t−¬ng ®−¬ng víi nhau tõng ®«i mét th× chóng t−¬ng ®−¬ng víi nhau. §Ó kiÓm tra nhãm c¸c tr¹ng thai t−¬ng ®−¬ng víi nhau kh«ng, cã thÓ sö dông b¶ng tr¹ng th¸i vµ tÝn hiÖu ra nh− sau: - Nhãm c¸c tr¹ng th¸i t−¬ng ®−¬ng ph¶i cã nh÷ng hµng trong b¶ng tÝn hiÖu ra gièng nhau. - Nhãm c¸c tr¹ng th¸i t−¬ng ®−¬ng ph¶i cã nh÷ng hµng trong b¶ng tr¹ng th¸i ë cïng mét cét(øng víi cïng tæ hîp tÝn hiÖu vµo ) lµ t−¬ng ®−¬ng. NghÜa lµ øng víi cïng mét tæ hîp tÝn hiÖu vµo c¸c tr¹ng th¸i sÏ chuyÓn biÕn tíi, cña chóng lµ t−¬ng ®−¬ng. §iÒu nµy cho thÊy thñ tôc kiÓm tra tÝnh t−¬ng ®−¬ng cña nhãm c¸c tr¹ng th¸i ph¶i tiÕn hµnh tuÇn tù tõng b−íc cho ®Õn nhãm cã tr¹ng th¸i cuèi cïng, nÕu nhãm cã tr¹ng th¸i cuèi cïng nµy lµ t−¬ng ®−¬ng th× nhãm tr¹ng th¸i ®−îc kiÓm tra lµ t−¬ng ®−¬ng. Quy t¾c Caldwell: Nh÷ng hµng(t−¬ng øng víi tr¹ng th¸i trong) cña b¶ng chuyÓn ®æi tr¹ng th¸i vµ tÝn hiÖu ra sÏ kÕt hîp víi nhau vµ ®−îc biÓu diÔn mét hµnh chung- ®Æc tr−ng(tr¹ng th¸i ®Æc tr−ng) cho chóng nÕu nh− chóng tho¶ m·n 2 ®iÒu kiÖn sau: 1- C¸c hµng t−¬ng øng trong ma trËn gièng nhau 2- Trong ma trËn ra, c¸c hµng t−¬ng øng ph¶i tho¶ m·n mét trong 3 ®iÓm: - C¸c hµng trong ma trËn ph¶i gièng nhau - C¸c tr¹ng th¸i trong cïng mét cét n»m trong nhãm tr¹ng th¸i ®−îc xÐt - C¸c tr¹ng th¸i ë trong cïng mét cét lµ c¸c tr¹ng th¸i t−¬ng øng Sau khi ®· thay thÕ c¸c tr¹ng th¸i t−¬ng ®−¬ng b»ng mét tr¹ng th¸i chung ®Æc tr−ng cho chóng, lÆp l¹i c¸c c«ng viÖc t×m c¸c tr¹ng th¸i t−¬ng ®−¬ng(c¸c hµng t−¬ng ®−¬ng) kh¸c, cho tíi khi nµo kh«ng thÓ t×m ®−îc c¸c hµng(c¸c tr¹ng th¸i) t−¬ng ®−¬ng víi nhau n÷a th× dõng l¹i. Sè tr¹ng th¸i trong b¶ng tr¹ng th¸i lóc ®ã lµ tèi thiÓu. ¸p dông quy t¾c Caldwell vµo bµi to¸n trªn, trong b¶ng trªn: S' Z S X=0 X=1 X=0 X=1 S0 S2 S1 0 0 S1 S4 S2 0 0 S2 S6 S5 0 0 S3 S0 S0 1 1 S4 S0 S0 0 0 S5 S0 S0 1 1 S6 S0 S0 0 0 S4 t−¬ng ®−¬ng S6, S3 t−¬ng ®−¬ng S5, thay thÕ c¸c tr¹ng th¸i t−¬ng ®−¬ng b»ng tr¹ng th¸i ®Æc tr−ng cho chóng, ch¼ng h¹n thay thÕ S4, S6 b»ng S46, S3 vµ S5 b»ng S35, tõ ®ã lËp ®−îc b¶ng míi nh− sau: 117
PTH-DTT S X=0 X=1 S0 S2 S1 Z=0 Z=0 S1 S46 S35 Z=0 Z=0 S2 S46 S35 Z=0 Z=0 S35 S0 S0 Z=1 Z=1 S46 S0 S0 Z=0 Z=0 Tõ ®©y ta l¹i thÊy S1≈S2, b¶ng sÏ rót gän nh− sau: S X=0 X=1 S0 S12 S12 Z=0 Z=0 S12 S46 S35 Z=0 Z=0 S35 S0 S0 Z=1 Z=1 S46 S0 S0 Z=0 Z=0 Tõ b¶ng trªn, kh«ng cã tr¹ng th¸i nµo t−¬ng ®−¬ng n÷a, nh− vËy m¹ch cßn l¹i 4 tr¹ng th¸i, víi ®å h×nh tr¹ng th¸i nh− sau: AB S 00 S0 01 S12 11 S35 10 S46 118
BomonKTDT-§HGTVT AB 00 01 Ck Ck XCk X Ck 10 11, Z=1 - B−íc 5: M· ho¸ tr¹ng th¸i, c¸c tr¹ng th¸i ®−îc m· ho¸ nh− b¶ng trªn - B−íc 6: X¸c ®Þnh hÖ ph−¬ng tr×nh cña m¹ch. Dùa vµo b¶ng tr¹ng th¸i, b¶ng ra ®Ó x¸c ®Þnh ®Çu vµo kÝch cho c¸c FF vµ ph−¬ng tr×nh tÝn hiÖu ra. §Çu vµo kÝch cho c¸c FF-A vµ FF-B lµ JA, KA JB, KB t−¬ng øng víi gi¸ trÞ cña tÝn hiÖu vµo X, theo b¶ng sau: Tr¹ng Tr¹ng th¸i tiÕp theo C¸c ®Çu vµo cña FF th¸i hiÖn X=0 X=1 X=0 X=1 X=0 X=1 t¹i AB AB AB JA KA JA KA JB KB JB KB 00 01, Z=0 01, Z=0 0 x 0 x 1 x 1 x 01 10, Z=0 11, Z=0 1 x 1 x x 1 x 0 11 00, Z=1 00, Z=1 x 1 x 1 x 1 x 1 10 00, Z=0 00, Z=0 x 1 x 1 0 x 0 x Sau khi tèi thiÓu ho¸, ta thu ®−îc: JA=B; KA=1; JB= B ; KB= X + A ; Ph−¬ng tr×nh tÝn hiÖu ra Z ®−îc x¸c ®Þnh dùa vµo b¶ng chuyÓn ®æi tr¹ng th¸i, b¶ng ra vµ b¶ng m· ho¸ : Z=A.B.CK Ngoµi c¸ch nµy cã thÓ dùa trùc tiÕp vµo ph−¬ng tr×nh Ton vµ Toff ®Ó x¸c ®Þnh. - B−íc 7: S¬ ®å m¹ch: 119
PTH-DTT X JA A JB B A '1' K KB A A CK Z 2. Ph−¬ng ph¸p ph©n ho¹ch: Ph−¬ng ph¸p nµy ®−îc dùa trªn viÖc ph©n chia c¸c tr¹ng th¸i theo c¸c líp cã c¸c ®Æc ®iÓm gièng nhau, sù ph©n chia thùc hiÖn nh− sau: - Sù ph©n chia lÇn thø nhÊt(P1) Tõ b¶ng chuyÓn ®æi tr¹ng th¸i vµ tÝn hiÖu ra ban ®Çu, ph©n chia c¸c tr¹ng th¸i ban ®Çu thµnh nhiÒu líp, trong mçi líp lµ nh÷ng tr¹ng th¸i cã tÝn hiÖu ra nh− nhau khi tÝn hiÖu vµo nh− nhau. - Sù ph©n chia lÇn 2(P2) XÐt c¸c tr¹ng th¸i trong cïng mét líp cña P1: NÕu c¸c tr¹ng th¸i n»m trong cïng mét líp cña P1 cã c¸c tr¹ng th¸i tiÕp theo cïng n»m trong cïng mét líp cña P1 th× ®−îc xÕp chung trong mét nhãm. NÕu kh«ng tho¶ m·n th× ph¶i t¸ch chóng ra thµnh c¸c nhãm kh¸c nhau, vµ sÏ ®−îc mét tËp hîp c¸c nhãm míi P2 TiÕp tôc thùc hiÖn nh− trªn, sÏ ®−îc P3,P4,…, Pi. Qu¸ tr×nh ph©n chia ®ã sÏ dõng l¹i khi Pi+1=Pi, sè nhãm Pi chÝnh lµ sè tr¹ng th¸i ®· ®−îc tèi thiÓu ho¸. Sau ®©y lµ mét vÝ dô minh ho¹: B¶ng chuyÓn ®æi tr¹ng th¸i vµ tÝn hiÖu ra cña mét m¹ch d·y ®ång bé m« t¶ ë b¶ng sau: 120
BomonKTDT-§HGTVT Tr¹ng th¸i hiÖn t¹i Tr¹ng th¸i tiÕp theo X=0 X=1 S0 S4 S0 Z=0 Z=1 S1 S4 S2 Z=1 Z=0 S2 S0 S3 Z=1 Z=1 S5 S6 S3 Z=0 Z=1 S4 S1 S2 Z=1 Z=0 S5 S4 S5 Z=0 Z=1 S6 S0 S3 Z=1 Z=1 + Sù ph©n chia lÇn 1: P1=(S0,S3,S5)(S1,S4)(S2,S6) + Sù ph©n chia lÇn 2: P2=(S3)(S0, S5)(S1,S4)(S2,S6) Ta cã P3=P2=(S3)(S0, S5)(S1,S4)(S2,S6) Tr¹ng th¸i hiÖn t¹i Tr¹ng th¸i tiÕp theo X=0 X=1 S05 S05 S14 Z=0 Z=1 S14 S14 S26 Z=1 Z=0 S26 S05 S3 Z=1 Z=1 S3 S05 S26 Z=0 Z=1 Nh− vËy c¸c líp tr¹ng th¸i t−¬ng ®−¬ng cña m¹ch ®· ®−îc x¸c ®Þnh, sau khi tèi thiÓu ho¸ m¹ch chØ cã 4 tr¹ng th¸i nh− trªn. 3. Ph−¬ng ph¸p dïng b¶ng so s¸nh Gi¶ sö ban ®Çu m¹ch cã n-1 tr¹ng th¸i trong S0, S1, S2, …, Sn LËp b¶ng so s¸nh cã c¸c hµng vµ cét nh− h×nh vÏ. Mçi « biÓu diÔn cÆp so s¸nh gi÷a 2 tr¹ng th¸i t−¬ng øng(Si, Sj) t¹i hµng vµ cét t−¬ng øng víi « ®ã. TiÕn hµnh tèi thiÓu ho¸ nh− sau: - Trong mçi «, nÕu cÆp tr¹ng th¸i t−¬ng øng cã tÝn hiÖu ra gièng nhau víi mäi tæ hîp tÝn hiÖu vµo(hµng trong b¶ng ra nh− nhau) th× ghi vµo ®ã cÆp tr¹ng th¸i mµ nã chuyÓn ®Õn øng víi tõng tæ hîp tÝn hiÖu vµo. NÕu tÝn hiÖu ra kh¸c nhau th× ®¸nh dÊu X vµo ®ã. - KiÓm tra nh÷ng « ghi cÆp tr¹ng th¸i: « nµy bÞ g¹ch ®i(X) nÕu nh− trong « ®ã cã mét cÆp tr¹ng th¸i ®· bÞ g¹ch ë « t−¬ng øng víi chóng tr−íc. 121
PTH-DTT TiÕn hµnh nh− b−íc 2 cho tíi khi nµo kh«ng g¹ch ®−îc « nµo n÷a th× dõng l¹i, nh÷ng « kh«ng bÞ g¹ch sÏ t−¬ng øng víi c¸c cÆp tr¹ng th¸i t−¬ng ®−¬ng Si,Sj t¹i hµng vµ cét t−¬ng øng víi « ®ã. - KiÓm tra c¸c tr¹ng th¸i t−¬ng ®−¬ng víi Si: trªn b¶ng kÐo theo sÏ kiÓm tra tõng cét tõ ph¶i(Sn) sang tr¸i(S0) ®Ó x¸c ®Þnh c¸c líp tr¹ng th¸i t−¬ng ®−¬ng, sè líp tr¹ng th¸i t−¬ng ®−¬ng cña S0 chÝnh lµ sè tr¹ng th¸i cña m¹ch ®· tèi thiÓu. Minh häa: Cho b¶ng chuyÓn ®æi tr¹ng th¸i vµ tÝn hiÖu ra m« t¶ nh− b¶ng sau: Tr¹ng th¸i tiÕp theo Tr¹ng th¸i hiÖn t¹i X=0 X=1 S0 S0 S2 Z=0 Z=0 S1 S3 S0 Z=1 Z=0 S2 S5 S5 Z=0 Z=0 S3 S4 S1 Z=1 Z=0 S4 S6 S6 Z=1 Z=0 S5 S2 S0 Z=0 Z=0 S6 S1 S7 Z=1 Z=0 S7 S7 S2 Z=0 Z=0 Sau ®©y lµ c¸c b−íc tèi thiÓu ho¸: - B−íc 1: §¸nh dÊu X vµo nh÷ng « mµ cÆp tr¹ng th¸i t−¬ng øng víi « ®ã cã hµng t−¬ng øng trong b¶ng tÝn hiÖu ra kh¸c nhau. Nh÷ng « kh«ng bÞ g¹ch, ghi nh÷ng cÆp tr¹ng th¸i S'i-S'j mµ 2 tr¹ng th¸i Si, Sj sÏ chuyÓn biÕn tíi øng víi tÝn hiÖu vµo X=0 vµ X=1 - B−íc 2: TiÕn hµnh kiÓm tra c¸c « trong b¶ng KiÓm tra c¸c « trong b¶ng sau: S1 S2 S3 S4 S5 S6 S7 S1 S0 S2 S3 S4 S5 S6 122
BomonKTDT-§HGTVT S1 S0-S5 S2-S5 S2 S3-S4 S3 S0-S1 S4 S3-S6 S4-S6 S0-S6 S1-S6 S5 S0-S2 S2-S5 S1-S3 S1-S4 S1-S6 S6 S0-S7 S1-S7 S6-S7 S0-S7 S5-S7 S2-S7 S2-S5 S7 S1 S0 S2 S3 S4 S5 S6 G¹ch thªm mét sè « míi, ®−îc b¶ng ë h×nh sau S1 S2 S3-S4 S3 S0-S1 S4 S3-S6 S4-S6 S0-S6 S1-S6 S5 S2-S5 S1-S3 S1-S4 S1-S6 S6 S0-S7 S1-S7 S6-S7 S5-S7 S2-S7 S2-S5 S7 S1 S0 S2 S3 S4 S5 S6 S5: (S6)(S5, S7) S4: (S6)(S5, S7)(S4) S3: (S6)(S5, S7)(S4)(S3) S2: (S6)(S2, S5, S7)(S4)(S3)(S1) S1: (S6)(S2, S5, S7)(S4)(S3)(S1) Sè tr¹ng th¸i tèi thiÓu b»ng sè nhãm tr¹ng th¸i t−¬ng ®−¬ng cét S0, m¹ch cã sè tr¹ng th¸i tèi thiÓu lµ 5. 123
PTH-DTT LËp ®−îc b¶ng chuyÓn ®æi tr¹ng th¸i vµ tÝn hiÖu ra ®· tèi thiÓu nh− b¶ng sau: Tr¹ng th¸i hiÖn t¹i Tr¹ng th¸i tiÕp theo X=0 X=1 S0257 S0257 S0257 Z=0 Z=0 S1 S3 S0257 Z=1 Z=0 S3 S4 S1 Z=1 Z=0 S4 S6 S6 Z=1 Z=0 S6 S1 S0257 Z=1 Z=0 IV. M· ho¸ tr¹ng th¸i Trong c¸c minh ho¹ tr−íc ®©y c¸c tr¹ng th¸i cña m¹ch ®−îc m· ho¸ tuú ý, cã nhiÒu c¸ch m· ho¸ kh¸c nhau vµ mçi c¸ch cho mét s¬ ®å kh¸c nhau, cÇn ph¶i chän c¸ch m· ho¸ sao cho s¬ ®å m¹ch thùc hiÖn lµ ®¬n gi¶n nhÊt. HiÖn nay vÉn ch−a cã c¸ch m· ho¸ nµo lµ tèi −u nhÊt. Th−êng thùc hiÖn theo 2 c¸ch sau ®Ó cã ®−îc s¬ ®å t−¬ng ®èi ®¬n gi¶n - Quy t¾c1: NÕu mét tr¹ng th¸i hiÖn t¹i Si cã thÓ chuyÓn biÕn ®Õn nhiÒu tr¹ng th¸i S'i1, S'i2,…,S'in th× c¸c tr¹ng th¸i S'ij ph¶i ®−îc m· ho¸ b»ng c¸c tõ m· kÕ cËn(chØ kh¸c nhau mét biÕn). - Quy t¾c 2: NÕu nhiÒu tr¹ng th¸i Sj1, Sj2,…,Sjn cïng chuyÓn biÕn ®Õn mét tr¹ng th¸i tiÕp theo S'j th× c¸c tr¹ng th¸i Sj1, Sj2,…,Sjn ®ã ph¶i ®−îc m· ho¸ b»ng c¸c tõ m· ho¸ kÕ cËn nhau. V. M¹ch d·y ®ång bé dïng m« h×nh Moore vµ m« h×nh Mealy Nh¾c lai: M« h×nh Moore lµ m« h×nh mµ tÝn hiÖu ra chØ phô thuéc vµo tr¹ng th¸i trong cña m¹ch. M« h×nh Mealy lµ m« h×nh mµ tÝn hiÖu ra phô thuéc c¶ vµo tr¹ng th¸i trong vµ tÝn hiÖu vµo X. Ta nghiªn cøu 2 m« h×nh nµy qua mét vÝ dô: ThiÕt kÕ mét m¹ch d·y ®ång bé nhËn biÕt d·y tÝn hiÖu vµo, tÝn hiÖu vµo ®−îc ®−a liªn tiÕp ë ®Çu vµo cña m¹ch theo d¹ng nhÞ ph©n, mçi lÇn d·y tÝn hiÖu vµo lµ 101, m¹ch sÏ cho ra tÝn hiÖu Z=1, c¸c bÝt d÷ liÖu vµo ®−îc ®ång bé víi xung nhÞp Ck. Gi¶i: - B−íc 1: X¸c ®Þnh bµi to¸n Theo ®Çu bµi ra ta cÇn ph¶i thiÕt kÕ 1 m¹ch d·y ®ång bé ®Ó ph¸t hiÖn d·y tÝn hiÖu vµo, nÕu d·y tÝn hiÖu vµo cã d¹ng 101 th× ®Çu ra Z=1 - B−íc 2: X¸c ®Þnh tÝn hiÖu vµo, ra: M¹ch cã 2 ®Çu tÝn hiÖu vµo lµ X vµ xung nhÞp Ck, vµ cã mét ®Çu tÝn hiÖu ra Z, theo nh− s¬ ®å khèi sau: 124
BomonKTDT-§HGTVT X 10100111011 Z M¹ch logic Ck - B−íc 3: ®å h×nh tr¹ng th¸i, b¶ng tr¹ng th¸i, vµ tÝn hiÖu ra a, NÕu dïng m« h×nh Mealy: X Ck S3 S0 Ck AB 00 AB XCk 10 S1 X Ck XCk AB 01 X Ck XCk S2 AB Z=XCk 11 Theo yÕu cÇu cña bµi to¸n chØ cÇn sö dông 3 tr¹ng th¸i ®Ó m· ho¸ S0, S1, S2. Nh− vËy dïng 2 bÝt nhÞ ph©n sÏ thõa 1 tr¹ng th¸i, ®Ó tr¸nh t×nh tr¹ng r¬i vµo tr¹ng th¸i khãa, ta thiÕt kÕ ®Ó m¹ch khi r¬i vµo tr¹ng th¸i ®ã, th× ngay tõ xung nhÞp ®Çu tiªn nã sÏ vÒ S0. Ta cã b¶ng tr¹ng th¸i vµ tÝn hiÖu ra: 125
PTH-DTT S X=0 X=1 S0 S0 S1 Z=0 Z=0 S1 S2 S1 Z=0 Z=0 S2 S0 S1 Z=0 Z=1 S3 S0 S0 Z=0 Z=0 b, Víi m« m×nh Moore: ChuyÓn tõ m« h×nh Mealy sang Moore ta ®−îc s¬ ®å vµ c¸ch m· ho¸ nh− sau: A B S 0 0 S0 0 1 S1 1 1 S2 1 0 S3 X Ck S0 AB 00 XCk S1 XCk XCk X Ck AB 01 X Ck S2 S3 XCk AB Z=1 11 X Ck AB 10 Tr¹ng th¸i S3 chÝnh lµ tr¹ng th¸i cho tÝn hiÖu ra Z=1 126
BomonKTDT-§HGTVT - B−íc 4:Tèi thiÓu ho¸ Víi vÝ dô nµy ta nhËn thÊy c¸c tr¹ng th¸i kh«ng thÓ tèi thiÓu thªm ®−îc n÷a. - B−íc 5: M· ho¸ tr¹ng th¸i, víi bµi to¸n nµy ¸p dông ph−¬ng ph¸p m· ho¸ kh¸c nhau 1 bÝt AB S 00 S0 01 S1 11 S2 10 S3 - B−íc 6: HÖ ph−¬ng tr×nh cña m¹ch a, M« h×nh Mealy: TONA=S1 X = AB X => JA=B X TOffA=S3+ S2 X + S2X=S2+S3=A => KA=1 TONB=S0X= AB X => JB= AX TOffB=S2 X = AB X => KB= A X Vµ Z= ABXCk a, M« h×nh Moore: TONA=S1 X = AB X => JA=B X => KA=B⊕X TOffA=S2 X + S3X=AB X +A B X TONB= B ( AX + A) => JB=A+X TOffB=S2 X +S2X => KB= A Vµ Z= A B - B−íc 7: S¬ ®å a, M« h×nh Mealy: X JA A JB B A '1' K KB CK Z 127
PTH-DTT b, M« h×nh Moore: X JA A JB B A K KB CK Z 128