Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
Okay, good morning everyone, great to see you again. Welcome to 151-251A, Introduction to Digital Logic and the Integrated Circuit.
Được rồi, chào buổi sáng cả lớp, rất vui được gặp lại các bạn. Chào mừng các bạn đến với 151-251A, Nhập môn Thiết kế số và Mạch tích hợp.
In today's lecture, we're going to finish some of our discussions on combinational logic, especially how we can simplify the logic, and we will also start our discussion on sequential logic.
Trong bài giảng hôm nay, chúng ta sẽ kết thúc một số nội dung thảo luận về logic tổ hợp, đặc biệt là cách đơn giản hóa logic, và chúng ta cũng sẽ bắt đầu thảo luận về logic tuần tự.
In particular, one very representative sequential logic, finite state machine, and how we can actually build a system using the different concepts in finite state machines, or FSM.
Cụ thể là một dạng logic tuần tự rất tiêu biểu, máy trạng thái hữu hạn, và cách chúng ta thực sự xây dựng một hệ thống bằng cách dùng các khái niệm khác nhau trong máy trạng thái hữu hạn, hay FSM.
Before I get there, some interesting news or trends that are interesting to observe these days. We talk about a lot of things in the fab space, right?
Trước khi vào phần đó, có một vài tin tức hay xu hướng thú vị đáng quan sát trong thời gian gần đây. Chúng ta nói rất nhiều về lĩnh vực nhà máy chế tạo chip, đúng không?
Intel, TSMC, and Samsung building up their very advanced fab facilities to actually be very competitive when we actually think about how we fabricate different hardware components.
Intel, TSMC, và Samsung đang xây dựng các cơ sở chế tạo chip rất tiên tiến để có thể cạnh tranh mạnh mẽ khi nói đến việc chế tạo các linh kiện phần cứng khác nhau.
On the design end, things are also getting very interesting when we think about semiconductor design, right? Traditionally, it's like Intel, AMD, and then Nvidia, Qualcomm, right?
Về phía thiết kế, mọi thứ cũng đang trở nên rất thú vị khi chúng ta nghĩ về thiết kế bán dẫn, đúng không? Truyền thống thì đó là Intel, AMD, rồi Nvidia, Qualcomm, đúng không?
Those companies that really dominate the design of CPUs, GPUs, and typically we see those software system companies, Google or Microsoft, more like clients or customers of the hardware company, right?
Những công ty thực sự thống trị việc thiết kế CPU, GPU, và thông thường các công ty hệ thống phần mềm như Google hay Microsoft giống khách hàng của các công ty phần cứng hơn, đúng không?
They buy things from Intel and Nvidia, AMD, and then put it in their data center. Things are also really changing in the design side.
Họ mua sản phẩm từ Intel, Nvidia, AMD rồi đặt vào trung tâm dữ liệu của mình. Phía thiết kế cũng đang thay đổi rất nhiều.
Today, the line between hardware and software companies is really blurry. If you think about Google, it's not only just a software company, it's not just a cloud provider.
Ngày nay, ranh giới giữa công ty phần cứng và phần mềm rất mờ nhạt. Nếu nghĩ về Google, họ không chỉ là một công ty phần mềm, không chỉ là một nhà cung cấp dịch vụ đám mây.
They also design a lot of hardware silicon these days. They actually have their own silicon design for both their data centers, but also their Pixel phones, their hardware, their edge components.
Ngày nay họ cũng thiết kế rất nhiều chip silicon phần cứng. Họ thực sự có thiết kế silicon riêng cho cả trung tâm dữ liệu, lẫn điện thoại Pixel, phần cứng của họ, các thành phần biên.
I guess the TPU, the Tensor Processing Unit, is the most popular or famous one.
Tôi đoán TPU, Tensor Processing Unit, là cái phổ biến hay nổi tiếng nhất.
A lot of people actually get to know a lot more about domain-specific acceleration because of Google's Tensor Processing Unit, TPU design, for machine learning. But Google is not only just designing TPU.
Nhiều người biết nhiều hơn hẳn về tăng tốc chuyên biệt theo miền nhờ thiết kế Tensor Processing Unit, TPU, của Google cho học máy. Nhưng Google không chỉ thiết kế TPU.
Another recent silicon development from Google is this video transcoding unit in Google's data center.
Một phát triển silicon gần đây khác của Google là bộ chuyển mã video trong trung tâm dữ liệu của Google.
There are a lot of computations actually going on in Google's data center, and one of the very important ones, especially for video processing like YouTube, right? We do a lot of transcoding.
Có rất nhiều phép tính thực sự diễn ra trong trung tâm dữ liệu của Google, và một trong những phép rất quan trọng, đặc biệt với xử lý video như YouTube, đúng không? Chúng ta chuyển mã rất nhiều.
They do actually a lot of transcoding, making sure that we see video on the different platforms.
Họ thực sự chuyển mã rất nhiều, để đảm bảo chúng ta xem được video trên các nền tảng khác nhau.
Very recently, I think the paper was published a couple years ago, they actually released their video transcoding unit, or VCU, design.
Rất gần đây, tôi nghĩ bài báo được công bố cách đây vài năm, họ đã công bố thiết kế bộ chuyển mã video, hay VCU.
This is also completely designed at Google, where they're designing their own silicon and also deploying it in their data center to offload a very significant amount of computation onto their own silicon.
Cái này cũng hoàn toàn được thiết kế tại Google, nơi họ tự thiết kế silicon của mình và triển khai trong trung tâm dữ liệu để chuyển một lượng tính toán rất đáng kể sang silicon của riêng họ.
I don't expect this is like the only TPU and VCU or the only Google silicon. We'll see a lot more Google silicon for all the different applications.
Tôi không cho rằng đây chỉ là TPU và VCU hay chỉ là silicon duy nhất của Google. Chúng ta sẽ thấy nhiều silicon của Google hơn nữa cho đủ loại ứng dụng.
Especially, one of the biggest advantages for those software or system providers is that they have the visibility of all the different applications actually running on the cloud, right?
Đặc biệt, một trong những lợi thế lớn nhất đối với những công ty phần mềm hoặc nhà cung cấp hệ thống là họ có tầm nhìn về tất cả các ứng dụng khác nhau đang thực sự chạy trên đám mây, đúng không?
They know what kind of applications are important, and then they can actually tailor their efforts to those important applications. For traditional hardware companies like Intel, NVIDIA, AMD, they actually don't have that visibility, right?
Họ biết loại ứng dụng nào là quan trọng, và từ đó họ có thể tập trung nỗ lực vào những ứng dụng quan trọng đó. Với các công ty phần cứng truyền thống như Intel, NVIDIA, AMD, họ thực ra không có tầm nhìn đó, đúng không?
It's getting really interesting with this kind of vertically integrated system.
Điều này trở nên rất thú vị với kiểu hệ thống tích hợp theo chiều dọc.
If a company actually has both access to a software ecosystem, understands what kind of things are important, and also the ability to actually build a design and fabricate fairly complex hardware logic, it's a huge advantage, right?
Nếu một công ty vừa có hệ sinh thái phần mềm, vừa hiểu những thứ nào là quan trọng, lại vừa có khả năng thiết kế và chế tạo logic phần cứng khá phức tạp, thì đó là một lợi thế rất lớn, đúng không?
Now we see a lot of companies don't position themselves as a software company only or a hardware company only.
Giờ chúng ta thấy nhiều công ty không tự định vị mình chỉ là công ty phần mềm hay chỉ là công ty phần cứng.
They position themselves as a system company where they do both hardware and software development, right?
Họ định vị mình là một công ty hệ thống, tức là làm cả phát triển phần cứng lẫn phần mềm, đúng không?
So, something interesting to keep an eye on, and we'll discuss more different processing elements actually developed by those either software companies or even startups. There is a lot of excitement in those different components.
Đây là điều thú vị cần theo dõi, và chúng ta sẽ bàn thêm về các phần tử xử lý khác nhau được phát triển bởi các công ty phần mềm đó, hoặc thậm chí các startup. Có rất nhiều sự hào hứng xung quanh những thành phần này.
With that, we will transition to the topic of today. Last time we talked about, we started combinational logic, right? It's very important.
Đến đây, chúng ta chuyển sang chủ đề của hôm nay. Lần trước chúng ta đã bắt đầu về logic tổ hợp, đúng không? Nó rất quan trọng.
Basically, all the different processing can be factored into either combinational logic or sequential logic, right?
Về cơ bản, mọi kiểu xử lý đều có thể được phân tách thành logic tổ hợp hoặc logic tuần tự, đúng không?
We'll get to sequential logic later in this lecture, and we'll also see there's still some component combinational logic there. We talked about how we can use Boolean algebra to actually represent combinational logic.
Chúng ta sẽ đến với logic tuần tự ở phần sau của bài giảng này, và cũng sẽ thấy ở đó vẫn có một số thành phần logic tổ hợp. Chúng ta đã nói về cách dùng đại số Boole để biểu diễn logic tổ hợp.
Basically, truth table, Boolean algebra and the gate representation, right? Three different ways to represent combinational logic and how we actually convert from one form to another, right?
Về cơ bản là bảng chân trị, đại số Boole và biểu diễn bằng cổng, đúng không? Ba cách khác nhau để biểu diễn logic tổ hợp và cách chuyển đổi từ dạng này sang dạng khác, đúng không?
Next, today we are going to go deeper into logic simplification, why it matters, and how we can potentially use some general high-level principles to do logic simplification.
Tiếp theo, hôm nay chúng ta sẽ đi sâu hơn vào việc đơn giản hóa logic, vì sao nó quan trọng, và làm thế nào để có thể dùng một số nguyên tắc tổng quát ở mức cao để đơn giản hóa logic.
A lot of what we will be covering today are basically some of the fundamental optimizations already embedded into this tool.
Phần lớn những gì chúng ta sẽ đề cập hôm nay về cơ bản là một số tối ưu hóa nền tảng đã được tích hợp sẵn trong công cụ này.
This tool actually does a lot of simplification, making sure we actually get an optimal design in the end. You don't need to actually do this by hand when you actually design your logic.
Công cụ này thực hiện rất nhiều việc đơn giản hóa, để đảm bảo cuối cùng ta có một thiết kế tối ưu. Bạn không cần làm việc này bằng tay khi thiết kế logic của mình.
Today's tools are actually pretty good, but one thing very important for this class in general is really develop intuition, right?
Các công cụ ngày nay khá tốt, nhưng một điều rất quan trọng đối với môn học này nói chung là phát triển trực giác, đúng không?
How this tool works at a very high level and why this kind of optimization matters, right?
Công cụ này hoạt động như thế nào ở mức rất tổng quát và vì sao kiểu tối ưu hóa này quan trọng, đúng không?
So we'll talk about some of the high-level principles of doing logic simplification and one way, one very handy way actually to do that.
Vì vậy chúng ta sẽ nói về một số nguyên tắc ở mức cao của việc đơn giản hóa logic và một cách, một cách rất tiện lợi để làm việc đó.
At the same time, a lot of today's tools actually already do this simplification automatically, so you don't actually need to do that by hand anymore.
Đồng thời, nhiều công cụ ngày nay thực ra đã tự động thực hiện việc đơn giản hóa này, nên thực ra bạn không còn cần làm thủ công nữa.
So with that, simplification, why it matters, right? So we talked about the different metrics early on in the semester, right? Cost is always very important, right?
Vậy thì, đơn giản hóa và vì sao nó quan trọng nhỉ? Ở đầu học kỳ chúng ta đã nói về các thước đo khác nhau rồi, đúng không? Chi phí luôn rất quan trọng, đúng không?
We want to build smaller systems but also performant and also consume less power and energy, right?
Chúng ta muốn xây dựng các hệ thống nhỏ hơn nhưng vẫn có hiệu năng cao và cũng tiêu thụ ít công suất và năng lượng hơn, đúng không?
So when we come to logic simplification, we want to minimize the number of gates actually used in circuits, right? Because it actually takes area, we want things to get smaller, Right?
Vì vậy, khi nói đến đơn giản hóa logic, chúng ta muốn giảm thiểu số cổng thực sự được dùng trong mạch, đúng không? Bởi vì chúng chiếm diện tích, và chúng ta muốn mọi thứ nhỏ lại, đúng không?
We also want to minimize the amount of wiring in the circuit. If we have so many gates, we also need to connect them.
Chúng ta cũng muốn giảm thiểu lượng dây nối trong mạch. Nếu có quá nhiều cổng, chúng ta cũng cần kết nối chúng với nhau.
We'll see in a couple weeks, actually, when we talk about wiring, that's actually very expensive. You'll take a look at today's fabricated chips, right?
Thực ra vài tuần nữa chúng ta sẽ thấy, khi nói về dây nối, rằng nó rất tốn kém. Hãy nhìn các con chip được chế tạo ngày nay, đúng không?
You will look at, like, especially those vertical, like, die shots. A lot of area is actually spent in just connecting different components together.
Bạn sẽ thấy, đặc biệt là những ảnh chụp die theo chiều dọc. Rất nhiều diện tích thực ra được dùng chỉ để nối các thành phần khác nhau với nhau.
A lot of metals, actually, in the fabrication process, purely just for wiring. So we want to also reduce the amount of wiring in the circuit to get a more efficient implementation.
Trong quy trình chế tạo có rất nhiều kim loại chỉ để làm dây nối. Vì vậy chúng ta cũng muốn giảm lượng dây nối trong mạch để có một cách hiện thực hiệu quả hơn.
Again, we also want to reduce the number of gate levels, right? Instead of having a huge circuit, it actually can be simplified into a simpler logic. It can also make things faster.
Một lần nữa, chúng ta cũng muốn giảm số tầng cổng, đúng không? Thay vì có một mạch khổng lồ, nó thực ra có thể được đơn giản hóa thành một logic đơn giản hơn. Nó cũng có thể làm mọi thứ nhanh hơn.
So the question is, well, this is definitely important, and then how do we do that, right? So again, I mentioned today's tools actually are pretty good at doing a lot of logic simplifications.
Vậy câu hỏi là, điều này chắc chắn quan trọng, và vậy làm thế nào để thực hiện, đúng không? Như tôi đã nói, các công cụ ngày nay thực ra làm khá tốt nhiều việc đơn giản hóa logic.
We'll talk a little bit more about what are the underlying principles behind those, and how we can actually, as a designer, do some quick back-of-envelope calculation also very quickly to see whether this logic can be simplified further.
Chúng ta sẽ nói thêm một chút về các nguyên lý nền tảng đằng sau những việc đó, và làm thế nào, với tư cách là nhà thiết kế, chúng ta cũng có thể tính nhẩm nhanh để xem logic này có thể được đơn giản hóa thêm không.
So with that, let's take a look at ways, actually, to do logic simplification. It's basically applying Boolean simplification. We talked about different theorems actually existed in Boolean logic, right?
Vậy hãy xem các cách đơn giản hóa logic. Về cơ bản đó là áp dụng đơn giản hóa Boolean. Chúng ta đã nói về các định lý khác nhau có trong logic Boolean, đúng không?
So we're basically using Boolean algebra to do logic simplification.
Vậy về cơ bản chúng ta dùng đại số Boolean để đơn giản hóa logic.
But we'd like to do this more systematically, instead of remembering all the different theorems, whether we can do this in a more automatic and especially more visual pattern.
Nhưng chúng ta muốn làm việc này một cách có hệ thống hơn, thay vì phải nhớ tất cả các định lý khác nhau, liệu có thể làm theo cách tự động hơn và đặc biệt là trực quan hơn không.
A very important principle is the uniting theorem.
Một nguyên lý rất quan trọng là định lý hợp nhất (uniting theorem).
It's basically whether we can completely actually get rid of one operand or one input if the logic function that we're simplifying is basically following this pattern, right?
Về cơ bản là liệu chúng ta có thể loại bỏ hoàn toàn một toán hạng hay một đầu vào hay không, nếu hàm logic mà chúng ta đang đơn giản hóa tuân theo mẫu này, đúng không?
So basically, it doesn't matter what the value of y here in this combination, The real, basically the two fundamental operations this function is trying to do is basically getting the value of x, right?
Vậy về cơ bản, giá trị của y ở đây trong tổ hợp này không quan trọng. Thực chất, hai phép toán cơ bản mà hàm này đang thực hiện về cơ bản là lấy ra giá trị của x, đúng không?
So in this kind of patterns, we can actually potentially get rid of one input completely, and we also get rid of one, actually two bits, right?
Vậy trong những mẫu như thế này, ta thực sự có thể loại bỏ hoàn toàn một đầu vào, và cũng loại bỏ được một, thực ra là hai bit, đúng không?
We don't need this calculating this product, and we also don't need to calculate this cell, right? So this get rid of one input and get rid of two operations.
Ta không cần tính tích này, và cũng không cần tính ô này, đúng không? Như vậy là bỏ được một đầu vào và bỏ được hai phép toán.
So this is very commonly used. It's also very intuitive, right? We looked at our truth table here, right? So we look at our truth table here.
Vì thế cách này được dùng rất phổ biến. Nó cũng rất trực quan, đúng không? Ta xem bảng chân trị ở đây, đúng không? Hãy nhìn bảng chân trị này.
It's like no matter what's the value of b here, f is one, right? We talk about a product of sum, right?
Giống như dù giá trị của b là gì thì f vẫn bằng một, đúng không? Ta đang nói về tích của các tổng, đúng không?
No matter what the value is for b, the output is always one, right? Which means basically the output is only dependent on a instead of dependent on both a and b.
Dù b có giá trị nào thì đầu ra vẫn luôn bằng một, đúng không? Nghĩa là đầu ra chỉ phụ thuộc vào a chứ không phụ thuộc vào cả a và b.
So generally, when we actually look to simplification, we'll see in a minute there is actually a more graphic interface that we can actually do this systematically, but this is very powerful to reduce the number of factors in our product, sum of product terms, and also reduce the number of inputs that we actually need to simplify.
Nói chung, khi ta xét đến việc đơn giản hóa, lát nữa ta sẽ thấy có một giao diện đồ họa hơn để ta có thể làm việc này một cách có hệ thống, nhưng cách này rất hiệu quả để giảm số thừa số trong các số hạng tích, trong tổng các tích, và cũng giảm số đầu vào mà ta cần đơn giản hóa.
So this is the underlying theorem that we use a lot in our simplification. It's actually coming pretty handy when we do a lot of logic simplification. Let's take a look at an example here.
Đây là định lý nền tảng mà ta dùng rất nhiều khi đơn giản hóa. Nó khá tiện khi ta đơn giản hóa nhiều biểu thức logic. Hãy xem một ví dụ.
So again, we have been using this full adder multiple times, right? So it's a very important building block.
Ta đã dùng bộ cộng đầy đủ này nhiều lần rồi, đúng không? Đây là một khối xây dựng rất quan trọng.
We'll also talk a lot about how we actually build a very efficient adder, different ways of building adder later in the semester, right?
Ta cũng sẽ nói nhiều về cách xây dựng một bộ cộng thật hiệu quả, các cách khác nhau để xây dựng bộ cộng, ở phần sau của học kỳ.
So remember we can actually express, turn the truth table into a Boolean expression using the sum of product, right? Sum of product by basically we're looking for carry out, Right?
Hãy nhớ rằng ta có thể biểu diễn, chuyển bảng chân trị thành biểu thức Boolean bằng dạng tổng các tích, đúng không? Tổng các tích, ở đây ta đang xét carry out, đúng không?
We find all the rows where carry out is one, and then we write a term for each row accordingly, and then sum them together, right?
Ta tìm tất cả các hàng mà carry out bằng một, rồi viết một số hạng tương ứng cho mỗi hàng, rồi cộng chúng lại, đúng không?
So this is how we turn a truth table into a sum of products, into a Boolean expression. This is really the first step, right?
Đó là cách ta chuyển bảng chân trị thành tổng các tích, thành một biểu thức Boolean. Đây mới thực sự là bước đầu tiên, đúng không?
We get a Boolean expression, but this may not be the simplest, right? We have a lot of terms here.
Ta có một biểu thức Boolean, nhưng nó có thể chưa đơn giản nhất, đúng không? Ở đây có rất nhiều số hạng.
We also need to simplify a lot of, we also need to actually compute a lot of logic here. So what we want to ask ourselves is whether we can actually get a simplified version.
Ta cũng cần đơn giản hóa nhiều, ta cũng phải tính toán rất nhiều logic ở đây. Vì vậy điều ta muốn tự hỏi là liệu ta có thể có một phiên bản đơn giản hơn không.
Well, we want to simplify this.
Ta muốn đơn giản hóa biểu thức này.
One very important pattern, remember the uniting theorem that we just saw earlier: they try to find the pair where one of the pair actually doesn't change in the expression, but the other actually gets the inverted pattern.
Một mẫu rất quan trọng, hãy nhớ định lý hợp nhất mà ta vừa thấy: ta cố tìm cặp mà một trong hai phần tử của cặp không thay đổi trong biểu thức, còn phần tử kia thì bị đảo.
If we have this pair, right? So in this case, we have A, B, which stay the same, but we also have now C and the C bar.
Nếu ta có cặp như vậy, đúng không? Ở trường hợp này, ta có A, B giữ nguyên, nhưng bây giờ chúng ta cũng có C và C đảo.
So C is inverted in those pairs, but A, B actually stays the same. We look for this opportunity because whenever we see this, we can actually get rid of one of the inputs, right?
Vậy C bị đảo trong các cặp đó, còn A, B thì vẫn giữ nguyên. Chúng ta tìm cơ hội này vì bất cứ khi nào thấy nó, chúng ta có thể loại bỏ một trong các đầu vào, đúng không?
Because that input actually doesn't matter. So whenever we see this, what we can do is basically get rid of C and then we can just write A, B here, right?
Vì đầu vào đó thực ra không ảnh hưởng gì. Cho nên bất cứ khi nào thấy điều này, về cơ bản ta có thể bỏ C đi và chỉ cần viết A, B ở đây, đúng không?
So this is very useful. Again, we can get rid of one input completely. We can also cut the number of terms and simplify the logic. So we use this once, right?
Điều này rất hữu ích. Một lần nữa, ta có thể bỏ hoàn toàn một đầu vào. Ta cũng có thể giảm số lượng số hạng và đơn giản hóa logic. Vậy ta dùng nó một lần, đúng không?
But there are two other terms, right? We want to keep using that because we can actually create those patterns, right? And then we can do further simplification.
Nhưng vẫn còn hai số hạng khác, đúng không? Ta muốn tiếp tục dùng nó vì thực ra ta có thể tạo ra những dạng đó, đúng không? Và sau đó ta có thể đơn giản hóa thêm.
One thing is important to note, and for folks who are online, if you're not asking questions, please mute yourself.
Có một điều quan trọng cần lưu ý, và với các bạn học trực tuyến, nếu không đặt câu hỏi thì xin hãy tắt micro.
So one thing that is actually very important to note is that we really have this term. We can actually keep adding this term multiple times, and it also doesn't change the result, right?
Có một điều thực sự rất quan trọng cần lưu ý là chúng ta có số hạng này. Ta có thể thêm số hạng này nhiều lần, và nó cũng không làm thay đổi kết quả, đúng không?
Because a, b, c is already one of the terms, and this is a very useful term that we can use to do optimization. We can just write it multiple times.
Vì a, b, c vốn đã là một trong các số hạng, và đây là một số hạng rất hữu ích để ta tối ưu hóa. Ta có thể viết nó nhiều lần.
So in this case, we have a pair between those two components. We can also create a pair between those two components, and the last pair between these two components.
Vậy ở đây, ta có một cặp giữa hai thành phần này. Ta cũng có thể tạo một cặp giữa hai thành phần này, và cặp cuối cùng giữa hai thành phần này.
One of the patterns here is that for each of those pairs, we always have one part of the term actually stay the same, but the other part of the term actually flipped, right?
Một quy luật ở đây là với mỗi cặp như vậy, luôn có một phần của số hạng giữ nguyên, còn phần kia thì bị đảo, đúng không?
So it's always a good pattern that we can actually reduce it. So we do the first term we already saw earlier.
Vậy đây luôn là một dạng tốt để ta có thể rút gọn. Ta làm số hạng đầu tiên như đã thấy trước đó.
We only need a, b here, right? And then we do the second term. In this case, a, c stays the same, and then we have not b and b.
Ở đây ta chỉ cần a, b, đúng không? Rồi ta làm số hạng thứ hai. Trường hợp này, a, c giữ nguyên, và ta có not b và b.
So b is eliminated, so we have a, c. And finally, for this term, right?
Vậy b bị loại bỏ, và ta có a, c. Và cuối cùng, với số hạng này, đúng không?
So b, c stays the same, but we have not a in the first term and a in the last term, so we can actually get b, c, right?
b, c giữ nguyên, nhưng ta có not a ở số hạng đầu và a ở số hạng cuối, nên ta có thể được b, c, đúng không?
So basically, we just keep applying the uniting theorem, and then we get a much simpler function, b, c plus a, c plus a, b, right?
Về cơ bản, ta cứ tiếp tục áp dụng định lý hợp nhất, và ta được một hàm đơn giản hơn nhiều, b, c cộng a, c cộng a, b, đúng không?
So again, this is a carry-out function. We started with four terms, and each term has three inputs, and then we end with three terms.
Một lần nữa, đây là hàm carry-out. Ta bắt đầu với bốn số hạng, mỗi số hạng có ba đầu vào, và cuối cùng ta còn ba số hạng.
So we have simpler logic, and each term only has two inputs. So this is a lot simpler, and that's basically the simplification that we do. You will see this pattern a lot.
Vậy logic đơn giản hơn, và mỗi số hạng chỉ có hai đầu vào. Như vậy đơn giản hơn nhiều, và đó chính là phép đơn giản hóa mà ta thực hiện. Các bạn sẽ gặp dạng này rất nhiều.
Sometimes, especially when you do synthesis, you may also see a majority or match. So we'll never see a majority gate where people are talking about majority function.
Đôi khi, đặc biệt khi làm synthesis, bạn cũng có thể thấy majority hay match. Vậy chúng ta sẽ không bao giờ thấy một cổng majority người ta nói về hàm đa số.
It's basically this function. You have three inputs. Basically, any of the two, if any of the two inputs are true, the output is true, right?
Về cơ bản là hàm này. Bạn có ba đầu vào. Về cơ bản, nếu bất kỳ hai đầu vào nào là đúng, thì đầu ra là đúng, đúng không?
So it's basically doing a majority function, picking up the output is true if the majority of the inputs are true. So this is another way.
Vậy nó về cơ bản thực hiện một hàm đa số, đầu ra là đúng nếu đa số các đầu vào là đúng. Đây là một cách khác.
So our carry-out in full adder is basically implementing a majority function, and in some of the library, we'll see match. So that's basically the majority function.
Vậy ngõ ra nhớ (carry-out) trong bộ cộng đầy đủ về cơ bản là thực hiện một hàm đa số, và trong một số thư viện, ta sẽ thấy match. Vậy đó về cơ bản là hàm đa số.
Makes how we actually apply in the united Lucy.
Còn việc áp dụng thực tế trong định lý hợp nhất thì sao.
I think, well, in this case, yes, C is C, A is A, B and B. You can just map C, I is C. I guess that's the only thing different.
Tôi nghĩ trong trường hợp này thì C là C, A là A, B là B. Bạn chỉ cần ánh xạ C, I là C. Tôi đoán đó là điểm khác duy nhất.
Yeah, it's basically, yeah, especially we're doing a majority function, it doesn't really change which value is which, yeah.
Vâng, về cơ bản là, vâng, nhất là khi ta làm hàm đa số, thì việc giá trị nào là giá trị nào không thực sự thay đổi gì.
Maybe let's go through this example here, right? So basically, we are doing the turning truth table into a sum of product, right?
Có lẽ ta cùng xem ví dụ này nhé? Về cơ bản, ta đang biến bảng chân trị thành tổng các tích, đúng không?
We're looking for the product term for each row, right? So you will do this. This will be A, B and C bar, right, for this row.
Ta tìm số hạng tích cho mỗi hàng, đúng không? Bạn sẽ làm như vậy. Với hàng này sẽ là A, B và C bù.
Or C bar, A, B, if we want to. The same as well.
Hoặc C bù, A, B cũng được. Cũng như nhau.
Okay, so it's basically just turn, writing the, starting from the truth table to turn into a sum of products term here. Any other questions?
Được rồi, vậy là chỉ cần viết, xuất phát từ bảng chân trị để chuyển thành biểu thức tổng các tích ở đây. Còn câu hỏi nào khác không?
Okay, we see, again, we see how we can actually use this, go through this step by step to actually do the simplification.
Được rồi, ta lại thấy cách ta có thể dùng cái này, đi từng bước để thực hiện việc đơn giản hóa.
But there is actually a more graphical interface that we can do that easily, instead of actually keep writing different equations and also more intuitively. So how do we do that?
Nhưng thực ra có một cách trực quan hơn bằng đồ thị để làm việc này dễ dàng, thay vì cứ viết các phương trình khác nhau, và cũng trực giác hơn. Vậy ta làm thế nào?
This is also a more detailed walkthrough of the function. If you have time, you can also do that, but eventually we just keep doing, applying the unifying theory.
Đây cũng là một bài làm mẫu chi tiết hơn về hàm này. Nếu có thời gian, bạn cũng có thể làm vậy, nhưng rốt cuộc ta cứ tiếp tục áp dụng định lý hợp nhất.
So a more graphical way of doing the same simplification that we just discussed is what people call Karnaugh map or K-map.
Một cách trực quan hơn để thực hiện cùng việc đơn giản hóa mà ta vừa bàn là cái người ta gọi là bản đồ Karnaugh hay K-map.
Again, when people talk about this, this is not something very complex or whatever. This is really to do logic simplification.
Một lần nữa, khi nói về điều này, nó không phải thứ gì quá phức tạp. Nó thực sự dùng để đơn giản hóa logic.
So that's still doing simplification, trying to figure out how we can actually simplify it.
Vậy đây vẫn là đơn giản hóa, tìm cách để có thể đơn giản hóa nó.
Instead of what we discussed earlier, start with a full complete truth table and writing the sum of product term into a Boolean equation and simplify the Boolean equation, here is basically whether we can actually direct to some operation or optimization in a format that's very similar to a truth table.
Thay vì như ta bàn trước đó, bắt đầu với một bảng chân trị đầy đủ và viết số hạng tổng các tích thành một phương trình Boole rồi đơn giản hóa phương trình đó, ở đây là xem ta có thể thao tác trực tiếp hay tối ưu hóa ở một dạng rất giống bảng chân trị hay không.
So that's basically Karnaugh map. You can actually basically think about Karnaugh map as a way to view or as a way to organize the truth table.
Đó về cơ bản là bản đồ Karnaugh. Bạn có thể xem bản đồ Karnaugh như một cách để nhìn hay một cách để sắp xếp bảng chân trị.
It's a truth table, it's still a truth table, it's representing the truth table, but instead of having inputs and outputs in different columns here, we basically organize this into a two-dimensional pattern.
Nó là bảng chân trị, vẫn là bảng chân trị, biểu diễn bảng chân trị, nhưng thay vì có đầu vào và đầu ra ở các cột khác nhau, ta sắp xếp nó thành một mẫu hai chiều.
You can also see later, it can also even be three-dimensional, we'll not get to that, especially for this class, we're mostly focusing on the two-dimensional pattern here.
Sau này các bạn cũng sẽ thấy, nó thậm chí còn có thể là ba chiều, nhưng chúng ta sẽ không đi sâu vào phần đó, đặc biệt là với môn học này, chúng ta chủ yếu tập trung vào dạng hai chiều ở đây.
So here we have two inputs, two inputs and one output. So we can actually organize this into more like a matrix format, right?
Ở đây ta có hai đầu vào và một đầu ra. Vì vậy ta có thể sắp xếp nó theo dạng giống một ma trận hơn, đúng không?
One of the dimensions is one input, the other dimension, horizontally, is one input, another dimension, vertically, is a different input.
Một chiều, theo phương ngang, là một đầu vào, chiều còn lại là một đầu vào khác, theo phương dọc, là một đầu vào khác nữa.
So for the output of here, instead of writing into a separate row, the outputs are basically the values in the matrix.
Còn đầu ra ở đây, thay vì viết vào một hàng riêng, thì các đầu ra chính là các giá trị trong ma trận.
So you can think about input basically setting up the indexes of the matrix of the Karnaugh map, and the output is basically populating the values of the Karnaugh map.
Vậy bạn có thể coi các đầu vào về cơ bản là thiết lập các chỉ số của ma trận, tức bản đồ Karnaugh, còn đầu ra là điền các giá trị vào bản đồ Karnaugh.
So that's basically how we can actually turn a truth table into a Karnaugh map. Now you may be wondering, why do we want to do that, right? Isn't this just the same truth table?
Đó về cơ bản là cách ta biến một bảng chân trị thành một bản đồ Karnaugh. Có thể bạn đang thắc mắc, tại sao ta lại muốn làm vậy? Chẳng phải đây vẫn chỉ là bảng chân trị sao?
And then we actually, isn't it just the same truth table, just written in a different format? How does this actually help us?
Và chẳng phải đó vẫn là cùng một bảng chân trị sao, chỉ được viết theo một định dạng khác? Vậy nó giúp ích gì cho chúng ta?
This helps us because we can actually do what we did earlier, the simplification, reducing the number of inputs a little bit more intuitively.
Nó giúp ích vì ta có thể làm điều đã làm trước đó, tức là việc đơn giản hóa, rút gọn số đầu vào một cách trực quan hơn một chút.
So instead of trying to actually add more terms and look at different terms to see whether we can combine them or not, we can basically turn the simplification, the Boolean algebra, into an exercise of drawing circles.
Thay vì cố thêm các số hạng và xem xét các số hạng khác nhau để xem có thể kết hợp chúng hay không, ta có thể biến việc đơn giản hóa, tức đại số Boole, thành một bài tập vẽ các vòng tròn.
We're literally looking for a group of ones, so basically looking for the true condition, and whenever we see a group of ones, we can actually draw circles to eliminate that.
Ta thực sự đang tìm một nhóm các số một, tức là tìm các điều kiện đúng, và bất cứ khi nào thấy một nhóm các số một, ta có thể vẽ vòng tròn để loại bỏ nó.
One thing here is that the dimension of the group must be a power of two. Remembering the theorem that we saw before, we need a pair, right?
Một điều cần lưu ý là kích thước của nhóm phải là lũy thừa của hai. Nhớ lại định lý ta đã thấy trước đó, ta cần một cặp, đúng không?
Whenever we see a pair, we can actually do elimination, right? We always look for a pair. So what we can do is look for a pair of ones.
Bất cứ khi nào thấy một cặp, ta có thể thực hiện việc loại bỏ, đúng không? Ta luôn tìm một cặp. Vậy ta có thể tìm một cặp các số một.
Whenever we see a pair of ones, let's say in this case, A is one, right? You will look at this column.
Bất cứ khi nào thấy một cặp số một, giả sử trong trường hợp này A bằng một, đúng không? Bạn sẽ nhìn vào cột này.
No matter what the value of B is, the output is always one, right? So we can basically simplify that pair into a single element, into A.
Dù giá trị của B là gì, đầu ra luôn bằng một, đúng không? Vậy ta có thể đơn giản hóa cặp đó thành một phần tử duy nhất, là A.
And similarly, we can draw another pair here, horizontally. So you can draw the circle either horizontally or vertically. So here you can also, as long as it's a power of two group, right?
Tương tự, ta có thể vẽ một cặp khác ở đây, theo phương ngang. Vậy bạn có thể vẽ vòng tròn theo phương ngang hoặc phương dọc. Ở đây cũng vậy, miễn là nhóm có kích thước lũy thừa của hai, đúng không?
So here, if we draw this horizontally, no matter what the value is for A, right? As long as B is one, the output is one, right?
Vậy ở đây, nếu ta vẽ theo phương ngang, thì dù giá trị của A là gì, đúng không? Miễn là B bằng một, đầu ra bằng một, đúng không?
So then we can actually directly write the output function as A and B by going through the Karnaugh map, or the truth table Karnaugh map version of the truth table, directly, getting a simplified expression instead of applying Boolean algebra using equations.
Vậy ta có thể trực tiếp viết hàm đầu ra là A và B bằng cách đi qua bản đồ Karnaugh, hay phiên bản bản đồ Karnaugh của bảng chân trị, một cách trực tiếp, để có được một biểu thức đã đơn giản hóa thay vì áp dụng đại số Boole bằng các phương trình.
So this is basically, at the high level, what we want to do. We first draw the Karnaugh map, Right? Where each dimension is basically the input.
Vậy về cơ bản, ở mức tổng quát, đây là điều ta muốn làm. Đầu tiên ta vẽ bản đồ Karnaugh, đúng không? Trong đó mỗi chiều chính là một đầu vào.
And then the entries of each of the map is basically the outputs from the truth table. It's a different representation of the truth table.
Và các ô của bản đồ chính là các đầu ra lấy từ bảng chân trị. Đây là một cách biểu diễn khác của bảng chân trị.
All the optimization we're doing, basically the step three, is basically forming groups of ones, right? We're looking for power, like pairs of ones that we can actually apply in simplification.
Toàn bộ phần tối ưu hóa chúng ta làm, tức là bước ba, về cơ bản là tạo các nhóm số một, đúng không? Chúng ta tìm các lũy thừa của hai, chẳng hạn các cặp số một mà ta có thể áp dụng để rút gọn.
And then for each group, we can write a product term, and then we get the Boolean expression as a sum of product.
Sau đó với mỗi nhóm, ta viết một số hạng tích, và thu được biểu thức Boole dưới dạng tổng các tích.
It may seem a little bit complex with all the different steps, but it's fairly intuitive. You will actually go through a couple examples, just how it works.
Có thể nhìn thì hơi phức tạp vì có nhiều bước khác nhau, nhưng nó khá trực quan. Các bạn sẽ làm qua vài ví dụ để thấy nó hoạt động thế nào.
Again, the goal is still applying the uniting theorem to actually simplify the expression, get a simplified version, but instead of writing a lot of equations, we are basically drawing circles to see the patterns of the inputs so we can get an output more intuitively.
Một lần nữa, mục tiêu vẫn là áp dụng định lý hợp nhất để rút gọn biểu thức, thu được một phiên bản đơn giản hơn, nhưng thay vì viết nhiều phương trình, ta vẽ các vòng tròn để nhìn ra các mẫu của đầu vào để có thể tìm đầu ra một cách trực quan hơn.
So let's take a look at some of the examples here.
Vậy hãy xem một vài ví dụ ở đây.
So again, as we mentioned, it's a different way of representing the truth table, right?
Như đã nói, đây là một cách khác để biểu diễn bảng chân trị, đúng không?
So it's still the truth table, but then we're basically using the dimensions to set up the different coordinates of the truth table, of the K-map, and then populate entries with the output here.
Vẫn là bảng chân trị đó, nhưng ta dùng các chiều để thiết lập các tọa độ khác nhau của bảng chân trị, tức là K-map, rồi điền các đầu ra vào các ô.
One thing here, so far we talked about two inputs, right? So it's very straightforward. I can also do three inputs. We basically combine two inputs into one dimension, right?
Có một điều: cho đến giờ ta mới nói về hai đầu vào, đúng không? Như vậy rất đơn giản. Tôi cũng có thể làm với ba đầu vào. Ta gộp hai đầu vào vào cùng một chiều, đúng không?
One thing here is gray labeling, right?
Một điều cần lưu ý ở đây là cách gán nhãn Gray, đúng không?
So whenever I actually want to draw the circle, look for patterns, we want to see the cases where one of the components, one part of the components, stays the same, but the other actually flipped, right?
Mỗi khi muốn vẽ vòng tròn để tìm các mẫu, ta muốn thấy những trường hợp mà một thành phần, một phần của các thành phần, giữ nguyên, còn thành phần kia thì đảo giá trị, đúng không?
Whenever we see that pattern, meaning that we can do simplification.
Mỗi khi thấy mẫu đó, nghĩa là ta có thể rút gọn.
So here, when we actually have two inputs here, one thing to notice here is that in those two terms, we actually have b, instead of traditionally the way we draw binary, to binary encoding, we actually do gray coding here, where b stays the same and a flipped.
Vậy ở đây, khi có hai đầu vào, điều cần chú ý là trong hai số hạng đó, ta có b, thay vì cách viết nhị phân truyền thống, ở đây ta dùng mã Gray, trong đó b giữ nguyên còn a đảo giá trị.
So whenever we actually move to the next neighboring position, only one of the elements actually flipped, right? So then with that, we can always apply the optimization to simplify the term.
Vậy mỗi khi ta chuyển sang vị trí lân cận kế tiếp, chỉ có một phần tử đảo giá trị, đúng không? Nhờ đó ta luôn có thể áp dụng tối ưu hóa để rút gọn số hạng.
So whenever we move to the next element, only one of the components actually flipped. So you will look at between those two, right?
Mỗi khi ta chuyển sang phần tử kế tiếp, chỉ có một thành phần đảo giá trị. Vậy bạn sẽ xét giữa hai ô đó, đúng không?
So b stays the same as one and a is from zero to one, so that's one of the elements actually flipped. So that's one thing important.
b giữ nguyên là một còn a đi từ không lên một, tức là chỉ một phần tử đảo giá trị. Đó là một điều quan trọng.
When we actually draw the, just set up the problem, and then similarly when we do four inputs, right, we also have this instead of one zero and then one, we actually do one one first, so that only one of the entry actually changes between, in the neighbor transition.
Khi ta vẽ, tức là khi thiết lập bài toán, và tương tự khi làm với bốn đầu vào, chúng ta cũng có thứ tự này, thay vì không một rồi một, ta làm một một trước, để chỉ có một phần tử thay đổi giữa hai ô trong bước chuyển liền kề.
So let's see, in this example, we have, let's take a look at some of the examples.
Vậy hãy xem, trong ví dụ này, chúng ta cùng xem một vài ví dụ.
So this is a setup, how we actually use different inputs to set up the dimensions, the indices of the Karnaugh map, of the matrix.
Đây là cách thiết lập, cách ta dùng các đầu vào khác nhau để thiết lập các chiều, các chỉ số của bản đồ Karnaugh, của ma trận.
Let's take a look at some examples. So let's look at, let's do two inputs first. So we have a and b, right?
Hãy xem một số ví dụ. Trước hết hãy xem trường hợp hai đầu vào. Ta có a và b, đúng không?
So a is different, a set up the row index and b, a set up the column index and b set up the row index, right?
Vậy a khác, a thiết lập chỉ số hàng và b, a thiết lập chỉ số cột và b thiết lập chỉ số hàng, đúng không?
So a is zero and one, b is also zero and one. So in this truth table, we already convert the truth table into the Karnaugh map, right? So we have this pattern, right?
a có giá trị không và một, b cũng có giá trị không và một. Trong bảng chân trị này, ta đã chuyển bảng chân trị thành bản đồ Karnaugh rồi, đúng không? Ta có mẫu này, đúng không?
So first we're looking for group of one here, right? So whenever we see a group of one up here, of one, we draw a circle, we draw a circle here, right?
Đầu tiên ta tìm nhóm các số một ở đây, đúng không? Khi nào thấy một nhóm số một ở đây, ta vẽ một vòng tròn, ta vẽ một vòng tròn ở đây, đúng không?
So this basically means if we draw a circle vertically, it basically no matter what the value is across different rows for b, right? The output is always the same as a, Right?
Điều này về cơ bản có nghĩa là nếu ta vẽ vòng tròn theo chiều dọc, thì dù giá trị của b ở các hàng khác nhau là gì đi nữa, đúng không? Đầu ra luôn giống a, đúng không?
So we can actually directly convert this into f is the same as a, right?
Vậy ta có thể chuyển trực tiếp thành f bằng a, đúng không?
So that's basically, you can also do this with the uniting theorem, so if you write the original function before, it will be b bar a for this element and then b a for the second element, right?
Bạn cũng có thể làm việc này bằng định lý hợp nhất, nếu viết hàm gốc như trước, nó sẽ là b phủ định nhân a cho phần tử này và b nhân a cho phần tử thứ hai, đúng không?
The first element, the second element.
Phần tử đầu tiên, phần tử thứ hai.
You can also do the simplification directly in Boolean equation, but then if you actually do Karnaugh map, it's a little bit slightly easier because you don't need to write so many different terms.
Bạn cũng có thể rút gọn trực tiếp trong phương trình Boole, nhưng nếu dùng bản đồ Karnaugh, thì sẽ dễ hơn một chút vì bạn không cần viết nhiều số hạng khác nhau.
You can just draw a circle and eliminate it, right? Make sense? Kind of, I want to see a little bit more example, right? So let's look at another example, the second one here.
Bạn chỉ cần vẽ một vòng tròn và loại bỏ biến đi, đúng không? Hiểu chưa? Chắc là bạn muốn xem thêm vài ví dụ nữa, đúng không? Vậy hãy xem ví dụ khác, ví dụ thứ hai ở đây.
Again, still two inputs, right? So now instead we're drawing, instead of a pair of one laid out vertically, we have a pair of one layout horizontally. Any guesses what this function is?
Vẫn là hai đầu vào, đúng không? Bây giờ thay vì vẽ một cặp số một xếp theo chiều dọc, ta có một cặp số một xếp theo chiều ngang. Có ai đoán được hàm này là gì không?
Not b, not b, this is not b. Why?
Không phải b, không phải b, đây không phải b. Tại sao?
Exactly, so you can, especially for the simpler one, right? You can basically do this directly, right? From Karnaugh map, you can basically also draw a circle here, right?
Chính xác, nên đặc biệt với những hàm đơn giản hơn, đúng không? Bạn có thể làm trực tiếp như vậy, đúng không? Từ bản đồ Karnaugh, bạn cũng có thể vẽ một vòng tròn ở đây, đúng không?
So in this case, no matter what the value is for a, as long as b is zero, the output is one, right?
Trong trường hợp này, dù giá trị của a là gì, miễn là b bằng không thì đầu ra bằng một, đúng không?
So it's basically not b. So, so far we have been looking at two inputs, right? Let's take a look at three inputs. So now we have a, b, and c, right?
Vậy về cơ bản nó là b phủ định. Cho đến giờ ta mới xem hai đầu vào, đúng không? Hãy xem trường hợp ba đầu vào. Vậy bây giờ ta có a, b và c, đúng không?
We have three inputs, and one thing again to note when you actually also work with the exercise is that when we look at, when we populate the third term, right?
Ta có ba đầu vào, và một điều cần lưu ý nữa, khi các em làm bài tập, là khi ta nhìn vào, khi ta điền giá trị cho số hạng thứ ba, đúng không?
So it's Gray coding, only one of the inputs is actually flipped, right? So we have one, one in the third column, right?
Đó là mã Gray, chỉ có một trong các đầu vào bị đảo, đúng không? Vậy ta có một, một ở cột thứ ba, đúng không?
So what this function is trying to do, how do we draw circles here to do simplification?
Vậy hàm này đang cố làm gì, ta vẽ các vòng tròn ở đây như thế nào để rút gọn?
I can draw, let me use different colors for different, so we can draw a horizontal for different ones, like this, for the vertical ones.
Tôi có thể vẽ, để tôi dùng các màu khác nhau cho các nhóm khác nhau, vậy ta có thể vẽ một vòng ngang cho các số một, như thế này, và một vòng cho các số một theo chiều dọc.
So we have two circles, one is a horizontal one, one is a vertical one. What others people think?
Vậy ta có hai vòng tròn, một vòng ngang, một vòng dọc. Các bạn khác nghĩ sao?
Right, so yes, so one thing is what, what's your name?
Đúng rồi, vậy, có một điều là, bạn tên gì nhỉ?
Rubit. Okay, what Rubit mentioned is actually we are drawing two circles, the vertical one makes sense, and the horizontal one is actually, you have three elements there.
Rubit. Được, điều Rubit nói là ta đang vẽ hai vòng tròn, vòng dọc thì hợp lý, còn vòng ngang thì ở đó có ba phần tử.
The problem with three elements is that we cannot actually apply the unifying theory anymore, right? So we actually need two terms that we can cancel out each other, and you are Ethan, right?
Vấn đề với ba phần tử là ta không thể áp dụng định lý hợp nhất được nữa, đúng không? Vì ta cần hai số hạng có thể triệt tiêu lẫn nhau, và bạn là Ethan, đúng không?
So Ethan mentioned instead of drawing a big circle, we can actually split it into two small circles, and then we can actually apply the optimized unifying theory to do that, right?
Ethan nói rằng thay vì vẽ một vòng lớn, ta có thể tách nó thành hai vòng nhỏ, rồi ta có thể áp dụng định lý hợp nhất một cách tối ưu để làm điều đó, đúng không?
So that one thing very important with kernel math, it's not always the bigger circle, the better, right?
Vậy một điều rất quan trọng với bản đồ Karnaugh là không phải lúc nào vòng càng lớn càng tốt, đúng không?
So you always need to find a pair, a group with a power of two, so that we can actually do optimization. So any guesses? What's the final expression for this one? Ethan?
Ta luôn cần tìm một cặp, một nhóm có số phần tử là lũy thừa của hai, để ta có thể thực hiện tối ưu hóa. Vậy có ai đoán được biểu thức cuối cùng của hàm này không? Ethan?
A, B, or C, A, or C, B, right? So basically each term, each circle leads to a term, right?
A, B, hoặc C, A, hoặc C, B, đúng không? Vậy về cơ bản mỗi vòng tròn cho ra một số hạng, đúng không?
So this again is a majority function that we saw earlier, right? So there's this, and finally, let's look at the fourth one.
Đây lại là hàm đa số mà ta đã thấy trước đó, đúng không? Vậy là như thế, và cuối cùng, ta hãy xem hàm thứ tư.
Again, three inputs, we are always looking for neighboring pairs, and so this pattern is important. How do we optimize this one, Ruby? Just draw one big box, right?
Lại là ba đầu vào, ta luôn tìm các cặp kề nhau, và mẫu hình này rất quan trọng. Ta tối ưu hàm này như thế nào, Ruby? Chỉ cần vẽ một ô lớn, đúng không?
So now we have a big circle here, and then it's actually three, four elements, right? So we can actually do the simplification directly, right?
Vậy bây giờ ta có một vòng lớn ở đây, và nó có ba, bốn phần tử, đúng không? Vậy ta có thể rút gọn trực tiếp, đúng không?
So what's the simplified function for this one? It's just A, right? It doesn't really matter what's the value of A, B, right? Everything cancels out. We have just A in the end, right?
Vậy hàm rút gọn của hàm này là gì? Chỉ là A, đúng không? Giá trị của B không quan trọng, đúng không? Mọi thứ đều triệt tiêu. Cuối cùng ta chỉ còn A, đúng không?
So it may seem to be a very complex function.
Vậy nhìn có vẻ đây là một hàm rất phức tạp.
You would just look at the truth table, even if we look at the Boolean expression, but once we actually draw the Karnaugh map, it's actually very intuitive to see the optimization opportunities to get a much simpler function.
Chỉ cần nhìn vào bảng chân trị, ngay cả khi ta nhìn vào biểu thức Boolean, nhưng một khi chúng ta vẽ bản đồ Karnaugh, thì rất trực quan để thấy các cơ hội tối ưu hóa để có được một hàm đơn giản hơn nhiều.
Question?
Có câu hỏi không?
Is using this method giving you the most optimal expression in there? Is that the question? Yes, so this optimization will give you the simplest Boolean expression that can be actually implemented.
Dùng phương pháp này thì có cho ra biểu thức tối ưu nhất không? Đó là câu hỏi phải không? Vâng, tối ưu hóa này sẽ cho bạn biểu thức Boolean đơn giản nhất mà thực sự có thể được triển khai.
Simplest in the sense of smallest number of terms. To give you the smallest number of terms, it may not be the most implementation-wise efficient mechanism, because implementation, there are different ways.
Đơn giản nhất theo nghĩa có số số hạng ít nhất. Nó cho bạn số số hạng nhỏ nhất, nhưng có thể không phải là cách hiệu quả nhất về mặt triển khai, vì khi triển khai thì có nhiều cách khác nhau.
Maybe even small term, you get a bigger gate, it's actually less efficient than a group of smaller gates.
Có thể ngay cả một số hạng nhỏ lại cần một cổng lớn hơn, và điều đó kém hiệu quả hơn một nhóm các cổng nhỏ hơn.
That will be technology dependent, but just in terms of the number of terms that we actually will have, it will give you a smaller number, smallest number of terms.
Điều đó phụ thuộc vào công nghệ, nhưng chỉ xét về số số hạng mà chúng ta sẽ có, thì nó sẽ cho bạn số số hạng ít nhất.
Brian? Can you explain which parts are corresponding to which circles? So for three, so we are doing three, let me choose a different color.
Brian? Bạn có thể giải thích phần nào tương ứng với vòng tròn nào không? Với ba biến, chúng ta đang làm ba biến, để tôi chọn một màu khác.
So let's start with the vertical one, right? So vertical one basically means as long as A B is one one, it doesn't really matter what the value of C is, right?
Hãy bắt đầu với vòng dọc nhé? Vòng dọc về cơ bản nghĩa là miễn là A B bằng một một, thì giá trị của C không quan trọng, đúng không?
So this leads to the first term A B, right? And then let's do this term.
Vậy nên nó cho ra số hạng đầu tiên là A B, đúng không? Rồi ta làm số hạng này.
This basically means as long as C is one and also B is one, it doesn't really matter what the value is for A, right?
Nó có nghĩa là miễn là C bằng một và B cũng bằng một, thì giá trị của A không quan trọng, đúng không?
So this basically gives us the C B term, right? And similarly, we look at the last term.
Vậy nó cho ta số hạng C B, đúng không? Tương tự, ta xét số hạng cuối cùng.
Again, C is one, A is one, it doesn't really matter what the value of B is, so it gives you the last term. So every circle, a group eliminates one term, one input.
Một lần nữa, C bằng một, A bằng một, giá trị của B không quan trọng, nên nó cho ra số hạng cuối cùng. Vậy mỗi vòng tròn, mỗi nhóm loại bỏ một số hạng, một đầu vào.
When you say a group, it means when we draw a circle? Yeah. When we draw a circle, we basically find the smallest commonality across different terms.
Khi bạn nói nhóm, ý là khi ta vẽ một vòng tròn phải không? Vâng. Khi ta vẽ một vòng tròn, về cơ bản ta tìm điểm chung nhỏ nhất giữa các số hạng khác nhau.
So when you say smallest commonality, oh, what are the two for all, the across all the conditions, right? I think, yeah, you can think of that way when you draw a circle.
Khi bạn nói điểm chung nhỏ nhất, ồ, là những gì chung cho tất cả, trên mọi điều kiện, đúng không? Tôi nghĩ vâng, bạn có thể nghĩ như vậy khi vẽ một vòng tròn.
So it, I guess it's instead of smallest commonality, this is basically showing you what this term or the overall expression is really sensitive to.
Nhưng thay vì điểm chung nhỏ nhất, thực ra nó cho bạn thấy số hạng này hay toàn bộ biểu thức thật sự nhạy với điều gì.
Whenever we see a neighboring term, they are the same. It basically means it's not sensitive to things that are actually changing, right?
Mỗi khi thấy các số hạng lân cận giống nhau, điều đó có nghĩa là nó không nhạy với những thứ đang thay đổi, đúng không?
So we're basically not sensitive to that change, where I guess it's more like max. It's not the smallest, it's more like the large. We're just eliminating the term that actually doesn't matter.
Vậy ta không nhạy với thay đổi đó, nên có lẽ nó giống cực đại hơn. Không phải nhỏ nhất, mà giống lớn nhất hơn. Ta chỉ loại bỏ số hạng thật sự không quan trọng.
Yes, we only choose this thing that actually really matters, yes.
Vâng, ta chỉ chọn những thứ thật sự quan trọng.
Any other questions? Can you explain again like why we asked you?
Còn câu hỏi nào khác không? Bạn có thể giải thích lại vì sao ta hỏi bạn không?
Oh, because when we actually do the uniting theorem, we'll do the, right, so all we are doing is basically look for these patterns, right?
Ồ, vì khi ta áp dụng định lý hợp nhất, đúng không, nên tất cả những gì ta làm về cơ bản là tìm các mẫu này, đúng không?
And then we can actually do this uniting theorem, and then eliminating this term gives us a, right? So we need two terms to actually do that, right?
Và sau đó ta có thể áp dụng định lý hợp nhất này, rồi loại bỏ số hạng này thì ta được a, đúng không? Vậy ta cần hai số hạng để làm được điều đó, đúng không?
Because all we are doing, remember the earlier the majority function, what we are doing is a step-by-step of buying that.
Bởi vì tất cả những gì ta làm, nhớ lại hàm đa số lúc trước, là ta thực hiện từng bước việc gộp đó.
We're doing the same thing, just with a more graphical patterns, and we always need a pair.
Ta làm đúng điều tương tự, chỉ là với các mẫu trực quan hơn, và lúc nào cũng cần một cặp.
You mean we have a different order of laying out the truth table? Yeah, different order of label.
Ý bạn là ta bố trí bảng chân trị theo thứ tự khác phải không? Vâng, thứ tự nhãn khác.
Let's say for this truth table, instead A is row, B is column, we do B and A like this.
Giả sử với bảng chân trị này, thay vì A là hàng, B là cột, ta làm B và A như thế này.
For this, you mean a different labeling? The order of label.
Với cái này, ý bạn là gán nhãn khác đúng không? Thứ tự của nhãn.
Oh, I see, that's a good question.
À, tôi hiểu rồi, câu hỏi hay đấy.
You can have different orders, but it will eventually still follow this pattern, because when we have a particular order, we always need to make sure the neighboring component only has one element different.
Bạn có thể dùng các thứ tự khác nhau, nhưng cuối cùng vẫn theo mẫu này, vì khi ta có một thứ tự nhất định, ta luôn phải đảm bảo các thành phần kề nhau chỉ khác nhau một phần tử.
There's basically, eventually will be, you can basically rotate this order somehow, but always the neighboring components only have one bit flipped. That's always, you need to always guarantee that. Yeah.
Về cơ bản bạn có thể xoay thứ tự này đi theo cách nào đó, nhưng các thành phần kề nhau luôn chỉ khác nhau một bit. Điều đó luôn phải được đảm bảo. Vâng.
So if you have three, how can we have all of them together? Oh, we have actually more elements, that's what you mean.
Vậy nếu có ba thì làm sao gộp tất cả lại? À, ý bạn là ta có nhiều phần tử hơn.
Yeah, so I think we'll actually have a picture showing that. So this, yeah, this is the result. So there are also higher dimensional K-maps, basically exactly what's right, and your name is?
Vâng, tôi nghĩ ta sẽ có một hình minh họa cho việc đó. Đây, đây là kết quả. Vậy cũng có các K-map nhiều chiều hơn, đúng như điều bạn nói, và tên bạn là gì nhỉ?
Sam. Sam, what Sam and Ryan suggested earlier, right? So what do you, so, so far we basically get to four inputs, right?
Sam. Sam, như Sam và Ryan đã gợi ý lúc nãy, đúng không? Vậy, cho đến giờ ta mới có bốn đầu vào, đúng không?
So we can also get to five inputs or six inputs by basically having this vertical, a third dimension, the d dimension to be the third dimension, right?
Ta cũng có thể lên năm hay sáu đầu vào bằng cách thêm chiều dọc này, một chiều thứ ba, chiều d làm chiều thứ ba, đúng không?
You can keep doing that. Again, the same principle, it's getting pretty convoluted when we actually get there.
Bạn có thể tiếp tục như vậy. Vẫn cùng một nguyên lý, nhưng khi tới đó thì nó khá rối rắm.
I think some obsolete, like older midterm or final, we ask students to do that, but we don't ask you to do this.
Tôi nghĩ ở một số đề giữa kỳ hay cuối kỳ cũ, có yêu cầu sinh viên làm vậy, nhưng chúng tôi không yêu cầu các bạn.
So it's still possible if you can kind of visualize getting a 3D version of this, but it could be fun if you actually do that afterwards, but not required.
Vẫn có thể làm được nếu bạn hình dung ra phiên bản 3D của nó, và sẽ vui nếu sau này bạn tự làm, nhưng không bắt buộc.
So I think it's all four, five and six dimensions can still be represented in this K-map. Higher dimension is basically much harder. So that's a K-map discussion.
Vậy tôi nghĩ cả bốn, năm và sáu chiều vẫn có thể biểu diễn trong K-map này. Nhiều chiều hơn thì khó hơn nhiều. Đó là phần thảo luận về K-map.
So, so far we basically do the sum of products version K-map. You can also do this for the product of sums. It's just for your reference.
Vậy là cho đến giờ ta làm K-map dạng tổng các tích. Bạn cũng có thể làm tương tự cho dạng tích các tổng. Phần này chỉ để bạn tham khảo.
I will not spend too much time. It's very similar.
Tôi sẽ không dành nhiều thời gian. Nó rất giống.
You basically, you can also treat it as a DeMorgan again, but now one thing different is that instead of looking for group of one, we're actually looking for a group of zero that can cancel out.
Về cơ bản bạn cũng có thể coi nó là định lý DeMorgan lần nữa, nhưng điểm khác là thay vì tìm nhóm các số một, ta lại tìm các nhóm số 0 có thể triệt tiêu nhau.
But again, the pattern is the same. It's always Gray coding. And then when we write the output, it will be a product term instead of a sum term.
Nhưng một lần nữa, quy luật vẫn như vậy. Luôn luôn là mã Gray. Và khi viết đầu ra, ta sẽ có một số hạng tích thay vì số hạng tổng.
So this is basically how we can potentially use Karnaugh map to simplify some of the Boolean expression, Boolean simplification that we did manually before.
Vậy về cơ bản, đây là cách ta có thể dùng bản đồ Karnaugh để đơn giản hóa một số biểu thức Boole, việc đơn giản hóa Boole mà trước đây ta đã làm thủ công.
It's still manual even with Karnaugh map, but it's at least a little bit more intuitive, where you can actually see different patterns to do logic simplification.
Dùng bản đồ Karnaugh thì vẫn là làm thủ công, nhưng ít nhất nó trực quan hơn một chút, vì ta có thể thấy các mẫu khác nhau để đơn giản hóa logic.
So, a quick recap. We started our discussion on combinational logic. Again, it's basically, in combinational logic, the output only depends on the current value of the input. We don't have a state here.
Nào, tóm tắt nhanh. Ta đã bắt đầu thảo luận về logic tổ hợp. Nhắc lại, về cơ bản trong logic tổ hợp, đầu ra chỉ phụ thuộc vào giá trị hiện tại của đầu vào. Ở đây ta không có trạng thái.
So when we think about combinational logic, we can represent it in the truth table, Boolean expression, and then get a representation. We talked about how we convert between those and also do simplification there.
Vì vậy khi nghĩ về logic tổ hợp, ta có thể biểu diễn nó bằng bảng chân trị, biểu thức Boole, rồi thu được một cách biểu diễn. Ta đã nói về cách chuyển đổi qua lại giữa chúng và cả việc đơn giản hóa.
I talked a little bit about Boolean algebra and design, especially when it comes to simplification, logic simplification. We can use Boolean algebra directly in a lot of cases.
Tôi đã nói một chút về đại số Boole và thiết kế, đặc biệt là về đơn giản hóa, đơn giản hóa logic. Trong nhiều trường hợp ta có thể dùng trực tiếp đại số Boole.
It's actually a lot more handy to use Karnaugh map to do this simplification. A lot of job interviews ask this question.
Thực ra dùng bản đồ Karnaugh để đơn giản hóa thì tiện hơn nhiều. Rất nhiều buổi phỏng vấn xin việc hỏi câu này.
Again, a lot of this kind of underlying optimization, the tools actually do this pretty well. So it's already handled by the tools.
Nhưng nhiều việc tối ưu hóa nền tảng kiểu này, các công cụ làm khá tốt. Nên các công cụ đã xử lý sẵn rồi.
You don't need to actually do this manually, but it's still good to develop intuitions in terms of understanding what kind of logic this function actually fundamentally implements and how we can potentially simplify the logic using some principles there.
Bạn không cần phải làm thủ công, nhưng vẫn nên rèn trực giác để hiểu hàm này về bản chất thực hiện loại logic nào và làm sao ta có thể đơn giản hóa logic bằng một số nguyên tắc ở đó.
So that's the combinational logic. Any questions, thoughts, things you want to share? Ethan.
Đó là logic tổ hợp. Có câu hỏi, suy nghĩ hay điều gì muốn chia sẻ không? Ethan.
Oh, that's a good question.
Ồ, câu hỏi hay đấy.
Right, so they may actually not, because they actually start with different representation, right?
Đúng, có thể chúng sẽ không giống nhau, vì chúng bắt đầu từ các cách biểu diễn khác nhau, đúng không?
So they can always switch back to this using DeMorgan's law to actually switch back from a product of sums to the sum of products, but you may actually get a different number or different structure of the gates, because one is actually starting from AND and then doing a bunch of OR, one is the other, starting from OR to a bunch of AND.
Ta luôn có thể chuyển ngược lại bằng định lý DeMorgan để chuyển từ tích của các tổng về tổng của các tích, nhưng bạn có thể thu được số lượng khác hoặc cấu trúc cổng khác, vì một bên bắt đầu từ AND rồi đến một loạt OR, còn bên kia ngược lại, bắt đầu từ OR rồi đến một loạt AND.
Is there a way to getting the optimal minimized number of gates?
Có cách nào để đạt số cổng tối thiểu tối ưu không?
You mean, even a truth table, what is the minimum number of large big gates? I see.
Ý bạn là, với một bảng chân trị, số cổng lớn tối thiểu là bao nhiêu? Tôi hiểu rồi.
So you could write that truth table in product of sum, you could also write that truth table in sum of product.
Bạn có thể viết bảng chân trị đó dưới dạng tích của các tổng, cũng có thể viết dưới dạng tổng của các tích.
They will give you, if you just write it directly, they will give you a different number of terms, right? But then if you actually go through Karnaugh map optimization, let's see.
Nếu bạn viết trực tiếp, chúng sẽ cho số số hạng khác nhau, đúng không? Nhưng nếu thực sự tối ưu bằng bản đồ Karnaugh thì, để xem nào.
So if you actually go through Karnaugh map optimization, it will give you actually the smallest, based on the current combination is here.
Nếu thực sự thực hiện tối ưu bằng bản đồ Karnaugh, thì thực ra nó sẽ cho ta dạng nhỏ nhất, dựa trên tổ hợp hiện tại ở đây.
So for this one, so Karnaugh map will give you, for each, either a product of sum or sum of product, give you the minimum number of gates for each structure, assuming whether you're doing basic min term or max term.
Vậy với bài này, bản đồ Karnaugh sẽ cho ta, với mỗi cấu trúc, hoặc tích của các tổng hoặc tổng của các tích, số cổng tối thiểu cho từng cấu trúc, giả sử bạn đang dùng min term hay max term cơ bản.
They are not equivalent, you can't now say min term is actually bigger or smaller than max term.
Hai dạng này không tương đương, nên bạn không thể nói min term lớn hơn hay nhỏ hơn max term.
They basically have the, they will actually minimize, but you will minimize the different sets of min term or max term.
Về cơ bản chúng đều được tối thiểu hóa, nhưng bạn tối thiểu hóa các tập min term hoặc max term khác nhau.
You can convert that back and forth with the DeMorgan's theory, so eventually they will be the same, you will just use, apply the DeMorgan theory, but it shows different final results just because we start from different min term and max term.
Bạn có thể chuyển qua lại bằng định lý DeMorgan, nên cuối cùng chúng sẽ như nhau, bạn chỉ cần áp dụng định lý DeMorgan, nhưng kết quả cuối cùng trông khác nhau chỉ vì ta xuất phát từ min term và max term khác nhau.
Eventually it will be the same result, yeah, once you do the simplification.
Cuối cùng kết quả sẽ giống nhau, đúng vậy, khi bạn đã rút gọn xong.
Okay, good discussion. Some announcement. I hope you're having fun with lab two.
Được rồi, thảo luận hay đấy. Có vài thông báo. Hy vọng các bạn thấy thú vị với lab hai.
Most of you have already started lab two, a lot of things that we have, and I also heard most of you also finished lab two, so good job.
Hầu hết các bạn đã bắt đầu lab hai, có rất nhiều thứ chúng ta có, và tôi cũng nghe nói hầu hết các bạn đã làm xong lab hai, làm tốt lắm.
One thing, especially so early this semester, just don't fall behind. Making sure you finish lab, if you can actually finish lab during your lab hour, that's great.
Một điều, nhất là ngay đầu học kỳ này, đừng bị tụt lại phía sau. Hãy đảm bảo bạn hoàn thành lab, nếu bạn có thể làm xong lab trong giờ lab thì tốt quá.
If not, go to office hours or do it on your spare time to actually wrap up the lab as soon as possible, that's very important.
Nếu không, hãy đến giờ hỗ trợ hoặc tranh thủ thời gian rảnh để hoàn tất lab càng sớm càng tốt, điều đó rất quan trọng.
We also introduced a new lab, lab three, start this week. It's getting a little bit more involved, a lot more complex, but also very important moving forward for your final project.
Chúng ta cũng có lab mới, lab ba, bắt đầu từ tuần này. Nó phức tạp và đòi hỏi nhiều hơn một chút, nhưng cũng rất quan trọng cho đồ án cuối kỳ của các bạn.
The homework two will be due this week, and the new homework will also be released covering the combinational logic, K-map, and some of the FSM discussion.
Bài tập về nhà hai sẽ đến hạn nộp trong tuần này, và bài tập mới cũng sẽ được đăng, bao gồm mạch tổ hợp, K-map, và một số nội dung thảo luận về FSM.
So that's the things in this class, ongoing different components. Always, labs are very important; discussion, attend discussion, ask a lot of questions there; and also homework.
Đó là những phần đang diễn ra trong lớp này. Luôn luôn, lab rất quan trọng; hãy tham dự buổi thảo luận, đặt thật nhiều câu hỏi ở đó; và cả bài tập về nhà nữa.
Any other things or concerns about the class, labs, so far so good? Okay, well, let me know how things go, and our staff are very creative.
Còn điều gì khác hoặc lo ngại nào về lớp học, lab không, đến giờ vẫn ổn chứ? Được rồi, cứ cho tôi biết mọi việc diễn ra thế nào, và đội ngũ của chúng tôi rất sáng tạo.
This is our first time actually handling this big enrollment, so we are also learning. If there are anything that we can actually do better, help you navigate this class, let us know.
Đây là lần đầu chúng tôi xử lý lượng đăng ký lớn thế này, nên chúng tôi cũng đang học hỏi. Nếu có điều gì chúng tôi có thể làm tốt hơn để giúp các bạn theo kịp lớp này, hãy cho chúng tôi biết.
I think that is an interesting and also important learning experience for everyone on the team. Okay, so we talked a lot about combinational logic.
Tôi nghĩ đó là một trải nghiệm học tập thú vị và cũng quan trọng đối với mọi người trong nhóm. Được rồi, chúng ta đã nói nhiều về mạch tổ hợp.
Today we're also going to start our discussion on sequential logic, and sequential logic can be represented in finite state machine. We'll talk about the term in a minute.
Hôm nay chúng ta cũng sẽ bắt đầu thảo luận về mạch tuần tự, và mạch tuần tự có thể được biểu diễn bằng máy trạng thái hữu hạn. Lát nữa ta sẽ nói về thuật ngữ này.
Again, one thing very important with sequential logic is the notion of states, right? Instead of just purely combinational, input in, output out, we actually have state, we actually have storage there.
Một lần nữa, điều rất quan trọng với mạch tuần tự là khái niệm trạng thái, đúng không? Thay vì chỉ thuần túy tổ hợp, có đầu vào đi vào, đầu ra đi ra, thì ở đây chúng ta thực sự có trạng thái, có phần lưu trữ.
We'll briefly introduce a finite state machine. We'll also talk about two different ways to build a finite state machine, Moore machine and the Mealy machine, right?
Chúng ta sẽ giới thiệu ngắn gọn về máy trạng thái hữu hạn. Chúng ta cũng sẽ nói về hai cách khác nhau để xây dựng máy trạng thái hữu hạn, máy Moore và máy Mealy, nhé?
So a different style to represent this kind of state transition in sequential logic. With that, let's get started. So sequential logic is different from combinational logic, where combinational logic doesn't have any state, right?
Đó là hai kiểu khác nhau để biểu diễn loại chuyển trạng thái này trong logic tuần tự. Nào, chúng ta bắt đầu thôi. Logic tuần tự khác với logic tổ hợp, trong đó logic tổ hợp không có bất kỳ trạng thái nào, nhé?
There's no memory in combinational logic. When it comes to sequential logic, the most important thing is that now some things are stored, or some of the states are stored in memory components, right?
Logic tổ hợp không có bộ nhớ. Còn với logic tuần tự, điều quan trọng nhất là bây giờ có một số thứ được lưu lại, hay một số trạng thái được lưu trong các phần tử nhớ, nhé?
So now the output is not only depends on the input, But also depends on what the state I'm currently at, right? So it's a combination of input and current state to output, right?
Như vậy bây giờ đầu ra không chỉ phụ thuộc vào đầu vào, mà còn phụ thuộc vào trạng thái hiện tại mà tôi đang ở, nhé? Tức là đầu ra là sự kết hợp của đầu vào và trạng thái hiện tại, nhé?
You can also think about, like, when we actually see some of the discussions on, like, recurrent neural network, LSTM, they basically also have this notion of state, right, as a way to memorize or remember some of the prior input, right?
Các bạn cũng có thể hình dung giống như khi chúng ta thấy một số nội dung bàn về mạng nơ-ron hồi quy, LSTM, về cơ bản chúng cũng có khái niệm trạng thái, nhé, như một cách để ghi nhớ một số đầu vào trước đó, nhé?
So you can also approach this as, like, sequential logic: the state actually memorizes some of the behavior, some of the information that we received earlier, right? Distill the prior inputs into the state, right?
Vậy các bạn cũng có thể tiếp cận theo hướng logic tuần tự: trạng thái thực sự ghi nhớ một số hành vi, một số thông tin mà chúng ta đã nhận được trước đó, nhé? Chắt lọc các đầu vào trước đó vào trong trạng thái, nhé?
So states are generally stored in flip-flops. I will not talk too much about latches throughout the semester. Largely, I'll be basically talking about registers or flip-flops.
Các trạng thái thường được lưu trong flip-flop. Tôi sẽ không nói nhiều về latch trong suốt học kỳ. Phần lớn tôi sẽ nói về thanh ghi hay flip-flop.
So we have some elements to store the states. We still do combinational logic. We do computation there, but we also have elements to store the states.
Như vậy chúng ta có một số phần tử để lưu các trạng thái. Chúng ta vẫn có logic tổ hợp. Chúng ta thực hiện tính toán ở đó, nhưng cũng có các phần tử để lưu trạng thái.
So sequential logic are represented using finite state machine.
Vì vậy logic tuần tự được biểu diễn bằng máy trạng thái hữu hạn.
So basically, any kind of sequential logic are really talking about how we transition between different states, between different modes, and different modes will have different outputs, have different behavior of the circuit.
Về cơ bản, mọi loại logic tuần tự thực chất đều nói về việc chúng ta chuyển giữa các trạng thái khác nhau, giữa các chế độ khác nhau như thế nào, và các chế độ khác nhau sẽ có đầu ra khác nhau, có hành vi của mạch khác nhau.
Generally, when we think about the output, output basically depends on both input and the current state, while the state is actually determined by the prior input, right?
Nói chung, khi nghĩ về đầu ra, đầu ra về cơ bản phụ thuộc vào cả đầu vào và trạng thái hiện tại, trong khi trạng thái lại được xác định bởi các đầu vào trước đó, nhé?
So output still depends on the input, but not just the current input, but also the past input that has been, in some sense, encoded into the state, right?
Vậy đầu ra vẫn phụ thuộc vào đầu vào, nhưng không chỉ đầu vào hiện tại, mà còn cả đầu vào trong quá khứ, theo một nghĩa nào đó đã được mã hóa vào trạng thái, nhé?
So we'll first just see how we approach sequential logic by hand, how we actually think about different state transition.
Trước hết chúng ta sẽ xem cách tiếp cận logic tuần tự bằng tay, cách chúng ta suy nghĩ về các chuyển trạng thái khác nhau.
We'll also later cover how we actually articulate this kind of state transition in Verilog to actually really implement all the different logic.
Sau này chúng ta cũng sẽ tìm hiểu cách diễn đạt loại chuyển trạng thái này trong Verilog để hiện thực hóa tất cả các logic khác nhau.
So when it comes to a finite state machine, right, again, it's a sequential logic, a sequential circuit. It always have, we always need external inputs, Right? We also have outputs that's actually visible, right?
Vậy khi nói đến máy trạng thái hữu hạn, nhé, nó lại là một logic tuần tự, một mạch tuần tự. Nó luôn có, chúng ta luôn cần các đầu vào bên ngoài, nhé? Chúng ta cũng có các đầu ra mà bên ngoài có thể quan sát được, đúng không?
That's how we expose our states, how we expose our processing to external world, right? So we also have outputs. And then we have internal states.
Đó là cách chúng ta cho thấy các trạng thái của mình, cách chúng ta cho thế giới bên ngoài thấy quá trình xử lý của mình, đúng không? Vậy là chúng ta có các đầu ra. Và sau đó là các trạng thái bên trong.
Specifically, when we actually think about hardware, right, so there's always three components here. First is a state register, right? We always need something actually storing the states, right?
Cụ thể, khi nghĩ về phần cứng, đúng không, thì luôn có ba thành phần ở đây. Đầu tiên là thanh ghi trạng thái, đúng không? Chúng ta luôn cần một thứ gì đó để lưu các trạng thái, đúng không?
We always have register regs that actually store the current state. So that's the first part of the sequential element. There will be always two different sets of combinational logic here.
Chúng ta luôn có các thanh ghi để lưu trạng thái hiện tại. Đó là phần đầu tiên, phần tử tuần tự. Ở đây sẽ luôn có hai khối logic tổ hợp khác nhau.
The first combinational logic is basically the input, getting the input to determine what's the next state, right? We're talking about state transition, right? Different states, a different time step will have different states.
Khối logic tổ hợp thứ nhất về cơ bản nhận đầu vào, dùng đầu vào đó để xác định trạng thái kế tiếp là gì, đúng không? Chúng ta đang nói về chuyển trạng thái, đúng không? Mỗi bước thời gian khác nhau sẽ có trạng thái khác nhau.
We need a combinational logic to tell our system, to tell our circuit what the next state need to be, right? Because every time we actually also need to update our state.
Chúng ta cần một logic tổ hợp để cho hệ thống biết, để cho mạch biết trạng thái kế tiếp cần là gì, đúng không? Vì mỗi lần như vậy chúng ta cũng cần cập nhật trạng thái của mình.
So there is a combinational logic to actually tell us what the next state is. There is another combinational logic.
Vậy có một logic tổ hợp cho chúng ta biết trạng thái kế tiếp là gì. Có một logic tổ hợp khác.
Remember, we still also need to tell the outside world, right, what's going on inside this system, right?
Hãy nhớ rằng chúng ta vẫn cần cho thế giới bên ngoài biết, đúng không, bên trong hệ thống này đang diễn ra điều gì?
We also need another combinational logic to actually tell us, to dictate the output of the system, right?
Chúng ta cũng cần một logic tổ hợp khác để cho biết, để quy định đầu ra của hệ thống, đúng không?
So whenever it comes to any finite state machine, we need state register to store the current state, a combinational logic to calculate what the next state should be, and another combinational logic to actually dictate output of the system.
Vậy nên với bất kỳ máy trạng thái hữu hạn nào, chúng ta cần thanh ghi trạng thái để lưu trạng thái hiện tại, một logic tổ hợp để tính trạng thái kế tiếp phải là gì, và một logic tổ hợp khác để quy định đầu ra của hệ thống.
So we'll have three components: one state register, two combinational logic to compute the next state and the output. I'll see a couple examples in both today's lecture and the next lecture.
Vậy chúng ta có ba thành phần: một thanh ghi trạng thái, hai logic tổ hợp để tính trạng thái kế tiếp và đầu ra. Chúng ta sẽ xem một vài ví dụ trong cả bài giảng hôm nay và bài giảng tiếp theo.
What are some representative ways to think about it, why they matter, and how we actually can express a finite state machine, both using Boolean equations and also expressing them using Verilog.
Một số cách tiêu biểu để suy nghĩ về nó là gì, vì sao chúng quan trọng, và làm thế nào để biểu diễn một máy trạng thái hữu hạn, cả bằng các phương trình Boole lẫn bằng Verilog.
So let's take a look at an example again. Remember, whenever we think about sequential logic, state, two combinational logic to calculate next state and the output.
Vậy hãy cùng xem lại một ví dụ. Hãy nhớ, mỗi khi nghĩ về logic tuần tự, có trạng thái, hai logic tổ hợp để tính trạng thái kế tiếp và đầu ra.
Question? Flip-flop. Yeah, I guess we...
Có câu hỏi không? Flip-flop. Vâng, tôi đoán là chúng ta...
Right, so basic registers. So whenever we see a flip-flop, those are basically what we use to store the states. Okay, so with that, let's take a look at an example, a finite state example.
Đúng rồi, các thanh ghi cơ bản. Vậy mỗi khi thấy một flip-flop, về cơ bản đó là thứ chúng ta dùng để lưu các trạng thái. Được rồi, vậy hãy xem một ví dụ, một ví dụ về máy trạng thái hữu hạn.
So here, our finite state system of interest that we want to investigate is a cat's brain, right? Again, it's a very simplified cat's brain. So again, we're talking about components, right?
Ở đây, hệ thống trạng thái hữu hạn mà chúng ta quan tâm và muốn khảo sát là bộ não của một con mèo, đúng không? Một lần nữa, đó là một bộ não mèo rất đơn giản hóa. Vậy chúng ta lại nói về các thành phần, đúng không?
Whenever we think about any kind of system, we have inputs, and how we actually interact with the system, what are the inputs to the system, and output, what are the states that are observed from the external world, and the internal state, the internal mindset of the system, right?
Mỗi khi nghĩ về bất kỳ hệ thống nào, chúng ta có các đầu vào, tức là chúng ta tương tác với hệ thống bằng cách nào, các đầu vào của hệ thống là gì, và đầu ra, tức là những trạng thái mà thế giới bên ngoài quan sát được, và trạng thái bên trong, tức là trạng thái tinh thần bên trong của hệ thống, đúng không?
So there are three components, and they're in our simplified cat brain, right? So we have this very simple input as a way, well, there are not many ways that we can interact.
Vậy có ba thành phần, và chúng nằm trong bộ não mèo đơn giản hóa của chúng ta, đúng không? Vậy chúng ta có đầu vào rất đơn giản này như một cách, thật ra không có nhiều cách để tương tác.
We're basically either feeding the cat or petting the cat, right? So that's the input to our cat, right? Externally, unfortunately, the cat doesn't speak, right?
Về cơ bản, ta hoặc là cho mèo ăn, hoặc là vuốt ve mèo, đúng không? Đó chính là đầu vào của con mèo của chúng ta. Ở bên ngoài, tiếc là con mèo không biết nói, đúng không?
So we basically observe their eye movement and mouth movement, right? Whether they're eating, whether it's open or closed, whether their eyes are closed, so that's basically what can be observed externally.
Nên về cơ bản ta quan sát chuyển động của mắt và miệng của nó, đúng không? Xem nó có đang ăn không, miệng mở hay đóng, mắt có nhắm không, đó về cơ bản là những gì có thể quan sát được từ bên ngoài.
Internally, the state's elements, right? So again, in our very simplified cat's world, they are either in the eating mode or the sleeping mode or getting very annoyed.
Bên trong là các phần tử trạng thái, đúng không? Một lần nữa, trong thế giới mèo rất đơn giản hóa của chúng ta, nó hoặc ở chế độ ăn, hoặc chế độ ngủ, hoặc trở nên rất khó chịu.
So those are the three modes that our cat actually operates.
Đó là ba chế độ mà con mèo của chúng ta hoạt động.
So that's basically a setup, or system setup, that we want to see and how we can actually represent how this system behaves using a finite state machine example.
Vậy đó về cơ bản là một thiết lập, hay thiết lập hệ thống, mà ta muốn xem xét, và cách ta biểu diễn hành vi của hệ thống này bằng một ví dụ về máy trạng thái hữu hạn.
Before we move on, there's a question, a question on chat: would inputs also be connected to the lower section of the combinational logic? So that's a good question.
Trước khi tiếp tục, có một câu hỏi trong phần chat: liệu các đầu vào có cũng được nối với phần logic tổ hợp phía dưới không? Đó là một câu hỏi hay.
We'll actually get to it later, there's different ways of accessing, of describing finite state machine more than the Mealy machine. There are different, how inputs are used. We'll get there in a minute.
Lát nữa ta sẽ nói tới, có nhiều cách tiếp cận khác nhau, để mô tả máy trạng thái hữu hạn, không chỉ có máy Mealy. Có những cách khác nhau để sử dụng đầu vào. Chúng ta sẽ tới đó ngay.
So with this cat FSM example, what we're interested is how the state, how this machine, how this system actually transitions between different states, and how we actually observe the internal states through the output, that signal that we can observe.
Với ví dụ FSM con mèo này, điều ta quan tâm là trạng thái, tức là máy này, hệ thống này chuyển đổi giữa các trạng thái khác nhau như thế nào, và cách ta quan sát các trạng thái bên trong thông qua đầu ra, tức là tín hiệu mà ta có thể quan sát được.
So one thing we use a lot to describe the behavior of FSM is a state transition diagram, right? So this basically describes how a particular system actually transition between different states.
Một công cụ ta dùng rất nhiều để mô tả hành vi của FSM là sơ đồ chuyển trạng thái, đúng không? Sơ đồ này về cơ bản mô tả một hệ thống cụ thể chuyển đổi giữa các trạng thái khác nhau như thế nào.
So first, a couple of components in the state transition diagram. We always have states here, basically describe what the current state is.
Trước hết, sơ đồ chuyển trạng thái có một vài thành phần. Luôn có các trạng thái ở đây, về cơ bản mô tả trạng thái hiện tại là gì.
We use a circle and the way just to describe different states, right? So the circle represents a particular state or particular mode of the finite state machine.
Ta dùng một hình tròn để mô tả các trạng thái khác nhau, đúng không? Hình tròn biểu diễn một trạng thái cụ thể hay một chế độ cụ thể của máy trạng thái hữu hạn.
Let's say here, this is in the eating mode, right? We also have the output. We can also describe the output of the system.
Chẳng hạn ở đây là chế độ ăn, đúng không? Ta cũng có đầu ra. Ta cũng có thể mô tả đầu ra của hệ thống.
There are different, we'll talk about different ways of describing this based on the FSM that we're currently operating. But in this particular example, we can actually label the output inside each of the circle.
Có nhiều cách khác nhau, ta sẽ nói về các cách để mô tả điều này tùy theo loại FSM mà ta đang làm việc. Nhưng trong ví dụ cụ thể này, ta có thể ghi nhãn đầu ra ngay bên trong mỗi hình tròn.
So here we are labeled the eye and the mouth movement, but it can also be described in arc, basically the edges of the state transition diagram, if we're actually talking about Mealy FSM.
Ở đây ta ghi nhãn chuyển động của mắt và miệng, nhưng nó cũng có thể được mô tả trên các cung, tức là các cạnh của sơ đồ chuyển trạng thái, nếu ta đang nói về FSM kiểu Mealy.
We'll get to this later, but there are two places to actually can describe the output. If it's actually labeled in the circle, it's basically Moore FSM.
Lát nữa ta sẽ nói tới, nhưng có hai vị trí để mô tả đầu ra. Nếu được ghi nhãn trong hình tròn thì về cơ bản đó là FSM kiểu Moore.
Labeled externally, it will be a Mealy, we'll talk about that in a minute. And then inputs is described using edges, right?
Nếu ghi nhãn bên ngoài thì sẽ là Mealy, ta sẽ nói về điều đó ngay sau đây. Và sau đó các đầu vào được mô tả bằng các cạnh, đúng không?
So edges depends on the state transition, it may actually come back to the current state, or it may actually also go to different states.
Vậy các cạnh phụ thuộc vào chuyển trạng thái, nó có thể quay trở lại chính trạng thái hiện tại, hoặc cũng có thể đi sang các trạng thái khác.
So the inputs are actually on the edge, we label the inputs on the edges.
Vậy các đầu vào nằm trên cạnh, chúng ta ghi nhãn các đầu vào lên các cạnh.
So let's say for this example, we start with the eating stage for our cat, and the cat is eating, their eyes are open and their mouth is also open.
Giả sử với ví dụ này, ta bắt đầu từ trạng thái ăn của con mèo, và con mèo đang ăn, mắt nó mở và miệng nó cũng mở.
The input is feeding. The cat is always in the eating stage until we start petting the cat. So it's a different input, and then the cat transitions to a sleep stage, right?
Đầu vào là cho ăn. Con mèo luôn ở trạng thái ăn cho đến khi ta bắt đầu vuốt ve nó. Đó là một đầu vào khác, và con mèo chuyển sang trạng thái ngủ, đúng không?
So again, the state is actually in circles, and the edges or the arcs represent the input that actually triggered a transition.
Một lần nữa, các trạng thái nằm trong các hình tròn, còn các cạnh hay các cung biểu diễn đầu vào đã kích hoạt một lần chuyển trạng thái.
As we keep petting, we stay in the sleep state until we start, if we keep feeding that in a sleep state, we start petting, the cat gets annoyed, and if the cat is annoyed, their eyes are open, their mouth is closed, right?
Khi ta tiếp tục vuốt ve, ta vẫn ở trạng thái ngủ cho đến khi ta bắt đầu, nếu ta cứ cho ăn khi nó ở trạng thái ngủ, rồi ta bắt đầu vuốt ve, con mèo thấy khó chịu, và khi con mèo khó chịu, mắt nó mở, miệng nó đóng, đúng không?
And then we start eating again, then we transition back to the eat stage, right? So this is, again, a very simplified state transition diagram, describing a particular system.
Rồi ta lại bắt đầu cho ăn, thì ta chuyển ngược về trạng thái ăn, đúng không? Vậy đây, một lần nữa, là một sơ đồ chuyển trạng thái rất đơn giản hóa, mô tả một hệ thống cụ thể.
The state is actually in the middle of the circle, and the conditions, the inputs, are the edges that trigger state transitions.
Trạng thái nằm ở giữa hình tròn, còn các điều kiện, tức các đầu vào, là các cạnh kích hoạt chuyển trạng thái.
Sometimes we also have those self-edges, where we stay in the same state, it's not sensitive to this input, but for a particular input, we actually advance to a different state.
Đôi khi ta cũng có những cạnh tự quay về chính nó, nghĩa là ta ở nguyên trạng thái đó, nó không nhạy với đầu vào này, nhưng với một đầu vào cụ thể thì ta chuyển sang một trạng thái khác.
And in this example, the output is associated with the state, so we label the output in each of the circles.
Và trong ví dụ này, đầu ra gắn với trạng thái, nên ta ghi nhãn đầu ra trong từng hình tròn.
So that's a way to actually describe the behavior of this sequential logic or this finite state machine using this state transition diagram.
Đó là một cách để mô tả hành vi của mạch tuần tự này hay máy trạng thái hữu hạn này bằng sơ đồ chuyển trạng thái.
So once we have this state, before I move on, any questions? Ryan?
Vậy khi đã có trạng thái này, trước khi tiếp tục, có câu hỏi nào không? Ryan?
Yeah, it doesn't change the state. Yeah, you can think about, like, yeah, in some scenario, if you're just keeping feeding an input, they just stay the same, it's not sensitive to this input.
Vâng, nó không làm thay đổi trạng thái. Vâng, bạn có thể hình dung là, trong một số tình huống, nếu bạn cứ liên tục đưa vào một đầu vào, thì nó vẫn giữ nguyên, nó không nhạy với đầu vào này.
Yeah. So you can never feed and edit? In this setup, yes, we don't do that.
Vâng. Vậy là không bao giờ vừa cho ăn vừa vuốt ve được sao? Trong thiết lập này thì đúng, ta không làm vậy.
Again, so one thing very important is that in this setup, we don't do that, but in a different FSM, You may, maybe that will be a different input combination.
Một điều rất quan trọng là trong thiết lập này ta không làm vậy, nhưng trong một FSM khác thì có thể, có thể đó sẽ là một tổ hợp đầu vào khác.
We'll talk about encoding later, right? That could be a different, in this setup, we don't do that. Again, we're describing the simplified example.
Chúng ta sẽ nói về mã hóa sau, nhé? Đó có thể là một trường hợp khác, còn trong thiết lập này ta không làm vậy. Một lần nữa, chúng ta đang mô tả một ví dụ đơn giản hóa.
Okay, so start from the symbolic state, start from the state transition diagram. Again, one thing you remember, like we talked about the two combinational logic earlier, right?
Được rồi, vậy bắt đầu từ trạng thái dạng ký hiệu, bắt đầu từ sơ đồ chuyển trạng thái. Một điều nữa các bạn cần nhớ, như chúng ta đã nói về hai khối logic tổ hợp lúc trước, đúng không?
We want to see how we actually build those combinational logic, right? So we also actually want to describe those behaviors, again, start with from Boolean expressions and eventually into representation, right?
Chúng ta muốn xem làm thế nào để xây dựng các khối logic tổ hợp đó, đúng không? Vậy chúng ta cũng muốn mô tả các hành vi đó, một lần nữa, bắt đầu từ các biểu thức Boolean và cuối cùng đi đến biểu diễn, đúng không?
So once we have this, we can convert this state transition diagram into our symbolic table.
Vậy khi đã có cái này, ta có thể chuyển sơ đồ chuyển trạng thái này thành bảng ký hiệu của chúng ta.
Basically, you can think about this is, eventually we'll turn into a truth table, but before we actually give an encoding, right, we just write the different symbolic names first, right?
Về cơ bản, bạn có thể hình dung là cuối cùng nó sẽ trở thành một bảng chân trị, nhưng trước khi thực sự đưa ra một phép mã hóa, đúng không, ta chỉ viết các tên ký hiệu khác nhau trước, được chứ?
You can think about, like, similarly, we have inputs and outputs, right?
Các em có thể hình dung tương tự, ta có các đầu vào và đầu ra, đúng không?
So now inputs both include the inputs to the system, but also the current state, and the output for this combinational logic is basically the next state, right?
Bây giờ đầu vào bao gồm cả các đầu vào của hệ thống, lẫn trạng thái hiện tại, và đầu ra của khối logic tổ hợp này chính là trạng thái kế tiếp, đúng không?
As what we discussed earlier, let's say we are in the eating stage, eating state, right? You will keep feeding, right? We'll stay in the eating stage, basically this self-edge.
Như những gì ta đã bàn trước đó, giả sử ta đang ở giai đoạn ăn, trạng thái ăn, đúng không? Em sẽ tiếp tục cho ăn, đúng không? Ta sẽ ở lại trạng thái ăn, về cơ bản là cạnh tự lặp này.
You will actually start padding, we transition to the sleep state, right? So we transition to the sleep.
Em sẽ bắt đầu vỗ nhẹ, và ta chuyển sang trạng thái ngủ, đúng không? Vậy là ta chuyển sang trạng thái ngủ.
So we can basically go through each of the edges and then convert the state transition diagram into this symbolic table. Why we want this table, right?
Như vậy ta có thể lần lượt đi qua từng cạnh và chuyển sơ đồ chuyển trạng thái thành bảng ký hiệu này. Tại sao ta cần bảng này?
Because we, once we have this table and it can be turned into a truth table, we can express this computation in Boolean expression, right?
Vì một khi có bảng này, nó có thể được chuyển thành bảng chân trị, và ta có thể biểu diễn phép tính này bằng biểu thức Boolean, đúng không?
What we want to do next is basically convert this into a truth table by actually having encoded state, right?
Việc ta muốn làm tiếp theo là chuyển bảng này thành một bảng chân trị bằng cách mã hóa các trạng thái, đúng không?
So what we're encoding here, so let's say in our encoding, we have three states, right? Three states, we have, we want to have two bits here, right?
Vậy ta đang mã hóa gì ở đây, giả sử trong phép mã hóa của ta có ba trạng thái, đúng không? Ba trạng thái thì ta cần hai bit ở đây, đúng không?
So 0, 0 means eating, 0, 1 means sleeping, And 1, 0 means annoyed, right?
Vậy 0, 0 nghĩa là ăn, 0, 1 nghĩa là ngủ, và 1, 0 nghĩa là khó chịu, đúng không?
So then we can, and the input here, we basically use input to describe is either in the eating state, either doing the feeding or doing the padding, right?
Rồi ta có thể, và đầu vào ở đây, ta dùng đầu vào để mô tả em bé đang ở trạng thái ăn, hoặc là đang được cho ăn, hoặc là đang được vỗ nhẹ, đúng không?
We have a one-bit input, right? So this is the same, basically the same as the symbolic table, but now we actually add our encoding here, right?
Ta có một đầu vào một bit, đúng không? Vậy nên cái này về cơ bản giống bảng ký hiệu, nhưng bây giờ ta thêm phép mã hóa vào đây, đúng không?
So this looks more like a truth table now, right? Everything is in binary. So I will not do this, spend too much time, but we have all the expression here, right?
Giờ nó trông giống bảng chân trị hơn, đúng không? Mọi thứ đều ở dạng nhị phân. Tôi sẽ không dành quá nhiều thời gian cho phần này, nhưng ta có tất cả các biểu thức ở đây, đúng không?
So now you can also basically do what we already did, learned in the combinational logic, right? Turn this truth table into a Boolean expression and simplify it, right?
Giờ các em cũng có thể làm đúng những gì ta đã làm, đã học trong phần logic tổ hợp, đúng không? Chuyển bảng chân trị này thành biểu thức Boolean và rút gọn nó, đúng không?
So that's basically what we did in those, so we can actually get the combinational logic relationship of how we actually calculate next states right here, s0 prime and s1 prime, based on the inputs x and also the current state s0 and s1, right?
Đó về cơ bản là những gì ta đã làm trong các phần đó, nhờ vậy ta có thể thu được quan hệ logic tổ hợp về cách ta tính các trạng thái kế tiếp ngay tại đây, s0 phẩy và s1 phẩy, dựa trên các đầu vào x và cả trạng thái hiện tại s0 và s1, đúng không?
So this is, this is one of the truth table, right? So this is a truth table to calculate the next state, right?
Đây là một trong các bảng chân trị, đúng không? Đây là bảng chân trị để tính trạng thái kế tiếp, đúng không?
So we also have another, remember the three components: state, combinational logic to calculate the next state, and the combinational logic to calculate the output, right? We also need logic to actually calculate the output.
Ta còn một phần nữa, hãy nhớ ba thành phần: trạng thái, logic tổ hợp để tính trạng thái kế tiếp, và logic tổ hợp để tính đầu ra, đúng không? Ta cũng cần logic để tính đầu ra.
What are the signals that we want to expose to the output? Again, for the output, let's say we also have eyes and the mouth, right?
Những tín hiệu nào ta muốn đưa ra đầu ra? Một lần nữa, với đầu ra, giả sử ta có mắt và miệng, đúng không?
So that's our output. Again, this is another truth table, right?
Đó là đầu ra của ta. Một lần nữa, đây là một bảng chân trị khác, đúng không?
We also can encode, we can also encode our behaviors, output behaviors into a binary, and then once we have truth table, we can also write the Boolean expression of the output, how the output actually changes regarding the current state, right?
Chúng ta cũng có thể mã hóa, có thể mã hóa các hành vi của mình, tức là các hành vi đầu ra, thành dạng nhị phân, và một khi đã có bảng chân trị, chúng ta cũng có thể viết biểu thức Boolean của đầu ra, tức là đầu ra thực sự thay đổi như thế nào theo trạng thái hiện tại, đúng không?
So just a quick note, I think that's also one of the questions earlier, so in this, in this discussion, We assume with the design we have, the output is only dependent on the current state, right?
Xin lưu ý nhanh, tôi nghĩ đó cũng là một trong những câu hỏi lúc nãy, là trong phần thảo luận này, chúng ta giả sử với thiết kế mà chúng ta có, đầu ra chỉ phụ thuộc vào trạng thái hiện tại, đúng không?
If you are designing a different FSM, it's possible the output is also dependent on the input, and what I talked about separately as two different styles of describing a finite state machine.
Nếu bạn thiết kế một FSM khác, thì có thể đầu ra cũng phụ thuộc vào đầu vào, và đó là điều tôi đã nói riêng, như hai kiểu khác nhau để mô tả một máy trạng thái hữu hạn.
But for this way, the output is only dependent on the current state, right?
Nhưng với cách này, đầu ra chỉ phụ thuộc vào trạng thái hiện tại, đúng không?
So now, again, we have the state, we have our state encoding, we figure out the expression for our two combinational logic: how we calculate the next state, and how we calculate the output, right?
Vậy bây giờ, chúng ta đã có trạng thái, đã có cách mã hóa trạng thái, chúng ta tìm ra biểu thức cho hai khối logic tổ hợp: cách tính trạng thái kế tiếp, và cách tính đầu ra, đúng không?
With those expressions, we basically can represent, can draw our system into this category, right?
Với những biểu thức đó, về cơ bản chúng ta có thể biểu diễn, có thể vẽ hệ thống của mình theo mô hình này, đúng không?
We talk about how we, the combinational logic to calculate the next state, S0 prime and S1 prime, and the eyes and mouth as the output, right?
Chúng ta nói về cách logic tổ hợp tính trạng thái kế tiếp, S0 phẩy và S1 phẩy, còn mắt và miệng là đầu ra, đúng không?
So we have our state register here, that's the first part of our FSM, the state register.
Vậy chúng ta có thanh ghi trạng thái ở đây, đó là phần đầu tiên của FSM, thanh ghi trạng thái.
We have another part, this is basically the combinational logic to calculate the output of the FSM, right?
Chúng ta có một phần khác, về cơ bản đây là logic tổ hợp để tính đầu ra của FSM, đúng không?
And then we have our third part, everything going on here is basically another combinational logic to calculate the next state, right? So any FSM can be designed with the three components.
Và rồi chúng ta có phần thứ ba, mọi thứ diễn ra ở đây về cơ bản là một logic tổ hợp khác để tính trạng thái kế tiếp, đúng không? Vậy bất kỳ FSM nào cũng có thể được thiết kế với ba thành phần này.
We have our state registers, and then by figuring out the state transition, we can figure out the combinational logic to drive the output, and then we also figure out the combinational logic to drive the next state.
Chúng ta có các thanh ghi trạng thái, rồi bằng cách xác định chuyển trạng thái, chúng ta tìm ra logic tổ hợp để tạo đầu ra, và chúng ta cũng tìm ra logic tổ hợp để tạo trạng thái kế tiếp.
That basically builds our finite state machine representation for a complete system. Questions? Thoughts?
Điều đó về cơ bản xây dựng nên biểu diễn máy trạng thái hữu hạn cho một hệ thống hoàn chỉnh. Có câu hỏi hay ý kiến gì không?
Right, so how many rows in the state transition table, right? So it's, let's go, let's start with the symbolic one, right?
Vậy bảng chuyển trạng thái có bao nhiêu hàng? Chúng ta hãy bắt đầu với bảng dạng ký hiệu nhé.
So for this state transition table, it's basically a truth table, so we have inputs and outputs. So the complete number of rows basically depends on the number of inputs we have, right?
Bảng chuyển trạng thái này về cơ bản là một bảng chân trị, nên có các đầu vào và đầu ra. Vậy tổng số hàng đầy đủ về cơ bản phụ thuộc vào số đầu vào mà chúng ta có, đúng không?
So let's say, let's use the current state, this one is better. So here, the number of rows are basically determined by the number of inputs, right?
Giả sử, ta dùng trạng thái hiện tại, cách này tốt hơn. Ở đây, số hàng về cơ bản được xác định bởi số đầu vào, đúng không?
So here we have three bits inputs, right? So the number of rows, the maximum number of rows is basically by two to the three, right?
Ở đây chúng ta có đầu vào ba bit, đúng không? Vậy số hàng, số hàng tối đa về cơ bản là 2 mũ 3, đúng không?
We could have eight rows by just purely the three different inputs combination.
Chúng ta có thể có tám hàng chỉ từ các tổ hợp của ba đầu vào khác nhau.
Right, so those cases are, you just don't care, they are not actually valid in this setup, because for example, in the current state, right, we actually don't have a one-one state in this system, right?
Đúng rồi, những trường hợp đó là các trường hợp "don't care" (không quan tâm), vì chúng thực ra không hợp lệ trong thiết lập này, bởi vì ví dụ, ở trạng thái hiện tại, thực ra chúng ta không có trạng thái một-một trong hệ thống này, đúng không?
So in that case, this is one-one, it's basically, you can reset in your circuit, they will basically always be zero, right, because they are not actually valid.
Vậy trong trường hợp đó, đây là một-một, về cơ bản bạn có thể reset trong mạch của mình, chúng sẽ luôn bằng không, đúng không, vì chúng thực ra không hợp lệ.
So the maximum is basically two to the number of inputs, because this is a truth table, and in some scenario, it could be a subset, because we don't have, we haven't used all the different combinations.
Vậy giá trị tối đa là hai mũ số đầu vào, vì đây là một bảng chân trị, và trong một số trường hợp, nó có thể chỉ là một tập con, vì chúng ta chưa dùng hết tất cả các tổ hợp khác nhau.
Addison? Is it more accurate to interpret the possibility of the truth table as like a number of states times the possibility of completion?
Addison? Có chính xác hơn không nếu hiểu số khả năng của bảng chân trị là số trạng thái nhân với số khả năng hoàn thành?
Let's say we have three states and we have two possible integers.
Giả sử chúng ta có ba trạng thái và có hai số nguyên khả dĩ.
We have three states, yeah, you can also do that, because for each of the states, you basically, by giving different inputs, you will actually do different, yeah, so that's another way to do this.
Có ba trạng thái, vâng, bạn cũng có thể làm vậy, vì với mỗi trạng thái, bằng cách đưa vào các đầu vào khác nhau, bạn sẽ có các kết quả khác nhau, vâng, nên đó là một cách khác để làm việc này.
It's like a Cartesian plot. Exactly, it's, exactly, it's, this is number of states, this is number of actions, and then yeah, that's a good, good, good way to think about this.
Giống như một tích Descartes. Chính xác, đúng vậy, đây là số trạng thái, đây là số hành động, và vâng, đó là một cách rất hay để nghĩ về việc này.
Lucy?
Lucy?
Yeah, so the question is when do we actually use FSM? When do we actually follow this thought process, right?
Vâng, câu hỏi là khi nào chúng ta thực sự dùng FSM? Khi nào chúng ta thực sự làm theo cách suy nghĩ này?
It happens at the beginning of the design, when you approach any of today's design, it's very rare you have a fully combinational design.
Nó xảy ra ngay từ đầu quá trình thiết kế, khi bạn tiếp cận bất kỳ thiết kế nào ngày nay, rất hiếm khi bạn có một thiết kế hoàn toàn tổ hợp.
It's always some state when you actually design at least a digital system, right?
Luôn có trạng thái nào đó khi bạn thiết kế ít nhất là một hệ thống số, đúng không?
When you approach any of the designs, I genuinely recommend, students, unless you're very confident with your Verilog, you understand how to use that, always think about how many states there are, how they transition, before you start writing Verilog.
Khi tiếp cận bất kỳ thiết kế nào, tôi thực sự khuyên các bạn sinh viên, trừ khi bạn rất tự tin với Verilog và hiểu cách dùng nó, hãy luôn nghĩ xem có bao nhiêu trạng thái, chúng chuyển đổi như thế nào, trước khi bắt đầu viết Verilog.
So you always want to go through, understand, and how you want to encode things, right? Making sure you have thought through all the different steps before you start the design.
Vậy bạn luôn nên đi qua và hiểu rõ, và cả cách bạn muốn mã hóa mọi thứ, đúng không? Hãy đảm bảo bạn đã suy nghĩ kỹ tất cả các bước khác nhau trước khi bắt đầu thiết kế.
So this typically happens at the very beginning. The simplification is actually the same as what we already covered in combinational logic, so there's nothing new there.
Vì vậy việc này thường xảy ra ngay từ đầu. Việc đơn giản hóa thực ra giống hệt những gì chúng ta đã học trong logic tổ hợp, nên không có gì mới ở đó.
So once you actually understand how things are transitioned, you have the truth table, then that's the same as combinational logic that we discussed before.
Vậy khi bạn đã hiểu cách các trạng thái chuyển đổi, bạn có bảng chân trị, thì phần còn lại giống như logic tổ hợp mà chúng ta đã thảo luận trước đó.
So the simplification is not part of the, it's not a core part of this, it's really how you set up the problem.
Vậy việc đơn giản hóa không phải là một phần cốt lõi của việc này, mà cốt lõi là cách bạn thiết lập bài toán.
So this FSM, using different state transition description, is really setting up the problem.
Vậy FSM này, dùng các cách mô tả chuyển trạng thái khác nhau, thực chất là thiết lập bài toán.
Any other questions, thoughts?
Còn câu hỏi hay ý kiến nào khác không?
This table? Yeah. Right, so for output, right, this output, so we have state, this is the same as the encoding that we used before, right?
Bảng này à? Vâng. Đúng rồi, vậy với đầu ra, đúng không, đầu ra này, vậy chúng ta có trạng thái, cái này giống với phép mã hóa mà ta đã dùng trước đó, đúng không?
So we just populate here. So in this design, the output is basically associated with each state, right? So it's part of the circle.
Vậy ta chỉ cần điền vào đây. Trong thiết kế này, đầu ra về cơ bản gắn với từng trạng thái, đúng không? Tức là nó nằm trong vòng tròn.
We'll see there's an alternative design in a minute, but in this design, the output is associated with the state, right? I mean, the eating state, I basically have this particular combination of outputs, right?
Lát nữa ta sẽ thấy một thiết kế thay thế, nhưng trong thiết kế này, đầu ra gắn với trạng thái, đúng không? Ý tôi là, ở trạng thái ăn, tôi có tổ hợp đầu ra cụ thể này, đúng không?
So then the output only depends on the current state. And encoding-wise, right, so this is output encoding, right?
Vậy đầu ra chỉ phụ thuộc vào trạng thái hiện tại. Còn về mã hóa, đây là mã hóa đầu ra, đúng không?
So we have different combinations of eye and the mouth movement, and we encode it in this pattern, and that gets populated into the output table.
Ta có các tổ hợp khác nhau của chuyển động mắt và miệng, và ta mã hóa chúng theo mẫu này, rồi điền vào bảng đầu ra.
So the output table has two encodings: one is state encoding and the second is output encoding.
Vậy bảng đầu ra có hai phép mã hóa: một là mã hóa trạng thái và hai là mã hóa đầu ra.
Okay, I see, getting there, see the different concepts, see how they're put together, but we'll want to see a little bit more examples.
Được rồi, ta đang dần hiểu, thấy các khái niệm khác nhau và cách chúng được ghép lại với nhau, nhưng ta vẫn muốn xem thêm một vài ví dụ.
Right? So generally, when we actually think about design, that's basically what Lucy asked earlier, right? So this generally happens actually as a beginning of the design process, right?
Đúng không? Nói chung, khi ta thực sự nghĩ về thiết kế, đó chính là điều Lucy đã hỏi lúc nãy, đúng không? Điều này thường diễn ra ngay ở đầu quá trình thiết kế, đúng không?
We'll approach any kind of today's system, generally, I'll find a sequential logic with some state, some compute, right?
Khi tiếp cận bất kỳ hệ thống nào ngày nay, nhìn chung tôi sẽ tìm một mạch logic tuần tự có trạng thái và có phần tính toán, đúng không?
We want to understand what is this function, what is the function this circuit is trying to achieve, right? What are the inputs? What are the outputs? What are the internal states?
Ta muốn hiểu hàm này là gì, mạch này đang cố thực hiện chức năng gì, đúng không? Đầu vào là gì? Đầu ra là gì? Các trạng thái bên trong là gì?
And then we can actually draw the state transition diagram. That's basically internally how this FSM is actually organized, right? How we transition between different states. And then you'll have, we have encoding, right?
Sau đó ta có thể vẽ sơ đồ chuyển trạng thái. Về cơ bản đó là cách FSM này được tổ chức bên trong, đúng không? Cách ta chuyển giữa các trạng thái khác nhau. Rồi tiếp theo ta có mã hóa, đúng không?
We started with symbolic table, and then by doing encoding, we get to the encoding. There are like different ways you can do encoding. There's also a lot of flexibility, right?
Ta bắt đầu với bảng ký hiệu, rồi thực hiện mã hóa để có bảng mã hóa. Có nhiều cách mã hóa khác nhau. Cũng có rất nhiều sự linh hoạt, đúng không?
So we can do binary encoding. In our example, we did binary encoding. One-hot encoding, one-hot vector is also very popular use.
Ta có thể dùng mã hóa nhị phân. Trong ví dụ của ta, ta đã dùng mã hóa nhị phân. Mã hóa one-hot, vectơ one-hot, cũng được dùng rất phổ biến.
You need a little bit more bits, but you get, sometimes you may actually get a simplified expression. So there are different ways you can do the encoding.
Bạn cần nhiều bit hơn một chút, nhưng đôi khi bạn có thể thu được biểu thức đơn giản hơn. Vậy có nhiều cách khác nhau để mã hóa.
And after that, it's basically the same as what we did with combinational logic. We can simplify the Boolean expression, we get a simplified circuit, we can actually draw the circuit diagram, right?
Sau đó, về cơ bản mọi thứ giống với những gì ta đã làm với logic tổ hợp. Ta có thể rút gọn biểu thức Boolean, được mạch đơn giản hơn, rồi vẽ sơ đồ mạch, đúng không?
Whenever we get to circuit diagram, it's always, we have registers or a set of registers to hold the state.
Mỗi khi có sơ đồ mạch, nó luôn luôn là ta có thanh ghi hoặc một tập thanh ghi để lưu trạng thái.
We have two combinational logic, one to calculate the next state, and one to calculate the output, right? So three components of FSM, that's how we approach generally the FSM design problem.
Ta có hai khối logic tổ hợp, một khối tính trạng thái kế tiếp, và một khối tính đầu ra, đúng không? Vậy FSM có ba thành phần, và đó là cách ta nói chung tiếp cận bài toán thiết kế FSM.
So before I move on, any questions about FSM, encoding, state transition, triggering, different states?
Trước khi tiếp tục, có câu hỏi nào về FSM, mã hóa, chuyển trạng thái, kích hoạt, các trạng thái khác nhau không?
Okay, so those are basically, we talked about finite state machine, right? How we actually approach this using a simplified system.
Vâng, vậy là chúng ta đã nói về máy trạng thái hữu hạn (finite state machine), đúng không? Cách chúng ta thực sự tiếp cận nó bằng một hệ thống đơn giản hóa.
I think there are already a couple of questions showing up about the sensitivity of output, whether it's purely based on the state, which was the example that we saw earlier in the cat brain, Or there could be some complexity in terms of, it's not only depending on the state, but also depending on the input.
Tôi nghĩ đã có vài câu hỏi xuất hiện về độ nhạy của đầu ra, liệu nó hoàn toàn chỉ dựa trên trạng thái, như ví dụ chúng ta đã thấy trước đó với bộ não con mèo (cat brain), hay có thể phức tạp hơn, tức là nó không chỉ phụ thuộc vào trạng thái mà còn phụ thuộc vào đầu vào.
That's basically two different flavors of designing FSM, either using Moore's way or Mealy's way.
Về cơ bản đó là hai kiểu thiết kế FSM khác nhau, hoặc theo kiểu Moore, hoặc theo kiểu Mealy.
We'll talk a little bit more about what exactly these are actually trying to do. So there are two different FSM design decisions here.
Chúng ta sẽ nói kỹ hơn một chút về việc chính xác chúng làm gì. Vậy có hai lựa chọn thiết kế FSM khác nhau ở đây.
So it's basically trying to figure out how we compute the output of the circuit.
Về cơ bản là xác định cách chúng ta tính đầu ra của mạch.
Remember the three things: we have state, we have a next state logic, and we have the output combinational logic.
Hãy nhớ ba thành phần: trạng thái, logic trạng thái kế tiếp, và logic tổ hợp cho đầu ra.
In both setups, the next state is always determined by both the current state and also the current input. What they really differ in is actually the combinational logic to calculate the outputs here.
Trong cả hai cách, trạng thái kế tiếp luôn được xác định bởi cả trạng thái hiện tại và đầu vào hiện tại. Điểm khác nhau thực sự nằm ở logic tổ hợp để tính các đầu ra.
The Moore FSM's output is dependent only on the current state. So we look at a representation of a Moore FSM.
Đầu ra của FSM Moore chỉ phụ thuộc vào trạng thái hiện tại. Hãy xem biểu diễn của một FSM Moore.
So again, we have our first component, we have our state registers, we have our next state logic.
Một lần nữa, thành phần đầu tiên là các thanh ghi trạng thái, rồi đến logic trạng thái kế tiếp.
So next state logic is always determined by a combination of the current state and also the input. So it always has two inputs. And the third part is output logic.
Logic trạng thái kế tiếp luôn được xác định bởi sự kết hợp của trạng thái hiện tại và đầu vào. Vì vậy nó luôn có hai đầu vào. Phần thứ ba là logic đầu ra.
So here in a Moore FSM, the output logic is only dependent on the current state. So the output is only dependent on the current state, and then we actually get outputs directly.
Ở FSM Moore, logic đầu ra chỉ phụ thuộc vào trạng thái hiện tại. Tức là đầu ra chỉ phụ thuộc vào trạng thái hiện tại, và chúng ta nhận được đầu ra trực tiếp.
This is basically what we did with our cat brain. If you remember the cat brain example, you have a particular state, we actually determine the output. Another style is the Mealy FSM.
Về cơ bản đây là điều chúng ta đã làm với cat brain. Nếu bạn còn nhớ ví dụ cat brain, có một trạng thái cụ thể thì chúng ta xác định được đầu ra. Một kiểu khác là FSM Mealy.
The difference here is that the output actually depends on both the current state and the input. Again, you will get this diagram. The first, the state register, is the same.
Điểm khác ở đây là đầu ra phụ thuộc vào cả trạng thái hiện tại và đầu vào. Một lần nữa, bạn sẽ có sơ đồ này. Phần đầu tiên, thanh ghi trạng thái, giống nhau.
Second, the next state logic is also the same. So it's determined by both the current state and the input. The difference is the third part.
Phần thứ hai, logic trạng thái kế tiếp, cũng giống nhau. Tức là nó được xác định bởi cả trạng thái hiện tại và đầu vào. Điểm khác là ở phần thứ ba.
The output logic is not only dependent on the current state.
Logic đầu ra không chỉ phụ thuộc vào trạng thái hiện tại.
There could actually be a different edge actually coming in, so that output, it depends on, by a combination of input and the current states to get to the output.
Có thể có một cạnh khác đi vào, nên đầu ra phụ thuộc vào sự kết hợp của đầu vào và các trạng thái hiện tại để tạo ra đầu ra.
So there are two different flavors of designing that. They may actually need two different behaviors, complexities in terms of the size of logic and also the delay behaviors.
Vậy có hai kiểu thiết kế khác nhau. Chúng có thể cho hai hành vi khác nhau, với độ phức tạp khác nhau về kích thước logic và cả hành vi trễ.
This part is pretty important, and I don't want to rush it towards the end of the lecture. So we will pick it up next lecture.
Phần này khá quan trọng, và tôi không muốn vội vàng nói nó vào cuối buổi giảng. Vì vậy chúng ta sẽ tiếp tục vào bài giảng sau.
We'll actually dive deeper into how they differ, how they're different, and what are the different ways to think about it. But I want to plant the seeds first.
Chúng ta sẽ đi sâu hơn vào việc chúng khác nhau như thế nào, và những cách khác nhau để suy nghĩ về vấn đề này. Nhưng trước hết tôi muốn gieo mầm ý tưởng.
There are two different styles, and the only thing different is three components: registers, next state logic, and output logic. The last two parts are the same.
Có hai kiểu khác nhau, và điểm khác biệt duy nhất nằm ở ba thành phần: thanh ghi, logic trạng thái kế tiếp và logic đầu ra. Hai phần cuối là giống nhau.
The only thing different is actually the output logic, or the output logic is determined. Question.
Điểm khác biệt duy nhất thực ra là logic đầu ra, hay cách xác định logic đầu ra. Em có câu hỏi.
So depending on the specification of the system, so we'll see later that those two actually will lead to different timing behavior.
Vậy, tùy thuộc vào đặc tả của hệ thống, sau này chúng ta sẽ thấy hai kiểu này dẫn đến hành vi định thời khác nhau.
So it depends on how fast you'd like your output to respond to be based on the internal behavior. So they have different timing behavior. So you view, again, depend on.
Nó phụ thuộc vào việc bạn muốn đầu ra phản ứng nhanh đến mức nào dựa trên hành vi bên trong. Vì vậy chúng có hành vi định thời khác nhau. Như vậy, một lần nữa, điều đó còn tùy.
So when we do that, you as a designer have the flexibility to choose either Moore machine or Mealy machine to approach a problem.
Khi làm như vậy, bạn với tư cách người thiết kế có thể linh hoạt chọn máy Moore hoặc máy Mealy để giải quyết một bài toán.
The way you will design it differently, or whether you'll pick Moore or Mealy, is based on the problem specification. If problem has certain specification, you need to do this this way.
Cách bạn thiết kế sẽ khác nhau, hoặc việc bạn chọn Moore hay Mealy, dựa trên đặc tả của bài toán. Nếu bài toán có đặc tả nhất định, bạn cần làm theo cách này.
Problem has a different specification, you do that that way. So you have the flexibility to choose, but they do have different timing behaviors.
Bài toán có đặc tả khác, bạn làm theo cách kia. Vậy bạn có thể linh hoạt lựa chọn, nhưng chúng thực sự có hành vi định thời khác nhau.
So we'll talk about those behavior next lecture, because it's fairly important. With that, this is the end of today's lecture.
Chúng ta sẽ nói về các hành vi đó vào bài giảng sau, vì nó khá quan trọng. Đến đây là kết thúc bài giảng hôm nay.
I'll stick around if you have any questions, and we'll pick up some more on the Mealy machine next lecture, and how they are different, and how you can efficiently use them both.
Tôi sẽ ở lại nếu các em có câu hỏi, và bài giảng sau chúng ta sẽ tìm hiểu thêm về máy Mealy, chúng khác nhau thế nào, và làm sao sử dụng hiệu quả cả hai.
Good to see you all. I'll see you Thursday.
Rất vui được gặp các em. Hẹn gặp lại thứ Năm.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.