Квин-МакКласкийн алгоритм

Тоон электроникийн үндэс хичээл дээр багшид асуугдаад дараа нь ангийхандаа ярьж өгөх гэж бэлдэж байсан юм гэтэл багшид шалгуулж чадаагүй болохоор эндээ бичихээр шийдэв. Хэд хэдэн материал цуглуулж байж ойлгож авсан юм.

Энэ нь карно карт ажиллахад төвөгтэй болж ирэх 5,6-аас дээш оролттой болох үед маш их хэрэг болдог алгоритм юм. Мөн тоон хэлхээг хялбарчлахад зориулсан компьютерийн програм бичихэд ихэвчлэн хэрэглэдэг алгоритм юм.

Хэлхээг үнэний хүснэгтээс үүсгэх алхмууд:

1. Бүх минтерм эсвэл макстермүүдийг бичнэ.
2. 2т-ын тооллын системд эзлэх нэг эсвэл тэг гэсэн битийн тоогоор нь эрэмбэлэн бүлэг үүсгэнэ.
3. Бүх элемэнтийг шалгаж үзнэ. Ингэхдээ:
1. Нэг бүлгийн элемэнтүүдийг хооронд нь шалгахгүй
2. Нэг бүлгийн элемэнтийг нөгөө бүлгийн элемэнттэй шалгаж үзнэ
3. Хэрвээ шалгаж үзсэн 2 элемэнт хоорондоо нэг л битээр ялгаатай байвал хос болгоод дараагийн хүснэгтэд бичнэ. Хүснэгтэд бичихдээ тэр зөрсөн элемэнтийг Х гэж бичээд бусад битүүдийг нь хэвээр нь бичнэ.
4. Хос болж чадсан элемэнтүүдийг тэмдэглэх хэрэгтэй.
5. Дараагаар нь үүсэх хүснэгтийг мөн адил аргаар хайж давтана.
4. Хэрвээ хүснэгтэд ямар ч хос олдохгүй бол хайх алхамыг дуусгаад логик хэлхээний илэрхийллийг бичнэ.

Энэ алхамыг бас 10т-н тооллын системд хийж болдог ба тэр нь бол арай л амар юм байна лээ. Тэгэхдээ бичихээс залхуу хүрэв. Мэдмээр хүн байвал хүсэлтээ үлдээгээрэй.

Одоо нэгэн жишээг үзье.

Бидний шаардлагыг хангасан үнэний хүснэгт хэрэгтэй.

N0	A	B	C	D	Y
0	0	0	0	0	1
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	1
4	0	1	0	0	1
5	0	1	0	1	1
6	0	1	1	0	0
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	0
11	1	0	1	1	0
12	1	1	0	0	0
13	1	1	0	1	0
14	1	1	1	0	1
15	1	1	1	1	1

Одоо энэ үнэний хүснэгтээсээ мин термүүдийг ялгаж бичнэ.

N0	Binary	Y	Min terms
0	0000	1	A'B'C'D'
3	0011	1	A'B'CD
4	0100	1	A'BC'D'
5	0101	1	A'BC'D
8	1000	1	AB'C'D'
9	1001	1	AB'C'D
14	1110	1	ABCD'
15	1111	1	ABCD

Одоо мин термүүдээ 2тын тооллын системд эзэлж байгаа 1 гэсэн битийн тоогоор эсвэл 0 гэсэн битийн тоогоор эрэмбэлнэ. Би 1 гэсэн битийнх нь тоогоор эрэмбэллээ.

N0	Bin	1-ийн тоо	Min terms
0	0000	0	A'B'C'D'
4	0100	1	A'BC'D'
8	1000	1	AB'C'D'
3	0011	2	A'B'CD
5	0101	2	A'BC'D
9	1001	2	AB'C'D
14	1110	3	ABCD'
15	1111	4	ABCD

Одоо энэ хүснэгтийнхээ 1 гэсэн битийн тоо ширхэгээр бүлэг болсон байгаа байдлыг харж байна. Дараа нь энэ хүснэгтийнхээ зөвхөн нэг нэг битээр ялгаатай байгаа элемэнтүүдийг шинэ багана үүсгэн хуулж бичнэ.

N0	Эхнийх	Дараагийнх
0	0000 #	0x00
4	0100 #	x000
8	1000 #	010x
3	0011	100x
5	0101 #	111x
9	1001 #
14	1110 #
15	1111 #

За одоо ингээд нэг битээр зөрсөн мин термүүдийг бичээд, хос болж чадсан бол # тэмдэг ард нь тавьчихлаа. Одоо ингээд үүнээс цааш хос олдохгүй болсон тул логик илэрхийллэ бичье.

Логик илэрхийллийг бичихдээ ардаа # тэмдэггүй буюу хос болоогүй элемэнтүүдийг ашиглан бичих ба х тэмдгийг орхиж бичнэ.

Y = A'B'CD+A'C'D'+B'C'D'+A'BC'+AB'C'+ABC

(тайлбар:

A'B'CD = 0011

A'C'D' = 0x00

B'C'D' = x000

A'BC' = 010x

AB'C' = 100x

ABC = 111x

)

ийм боллоо.

Ингээд л хялбарчлагдсан логик илэрхийлэл гаргаад авчихлаа. Үүнээс цааш энэ хэлхээ хялбар болохгүй бөгөөд харин оновчтой хэлбэрт орж болно.

За тэгээд эцэст нь хэлэхэд интернэт гэдэг агуу юм даа, энд бүх л юм байна. Гэхдээ та бүхэн мэдээллийн үнэн худлыг л ялгаж боловсруулж авч байгаарай. Миний энэ бичсэн ч буруу байж магадгүй шүү.