Binary numbers (And some other useful bases)

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 9/11/13 ‹#› Binary numbers (And some other useful bases) Tại sao sử dụng hệ nhị phân? • Máy tính sử dụng số nhị phân vì: – Dễ thực hiện mạch: 1=1V, 0=0V (in the past 3.3V or 5V) – Dễ thiết kế các mạch phức tạp với các cổng (transistors) • Có thể sử dụng nhiều mức điện áp?… – 1=1V, 2=2V, 3=3V, etc. – Nhiễu sẽ phá huỷ mạch – Digital logic is noise tolerant: • No noise: 1 + 0 → 1 • With noise: 0.9 + 0.4 → 1, not 1.3 – Analog circuits carry noise through: • 1.4V + 3.4V → 4.8V (closer to 5 than 4!) • What’s interesting about computer: Arithmetic is how much we can do with a limited number of bits Hệ cơ số 2 (binary) Các hệ cơ số LSBs và MSBs • LSB = Least Significant Bit - > Bit có trọng số thấp • MSB = Most Significant Bit -> bit có trọng số cao • Example: 0101 1101 1110 1001 MSB – largest value digit LSB– lowest value digit Phép cộng, nhớ, phép nhân Phép cộng và phép nhân Thiết kế bộ nhân • Bộ nhân NxN có tích số 2N bit ra – Câu hỏi: Phép nhân thực hiện như thế nào trong MIPS khi sử dụng thanh ghi 32 bit? – Trả lời: Hai thanh ghị đặc biệt Hi và Lo lưu kết quả phép nhân 32 bit mỗi thanh ghi • Phép nhân chiếm nhiều tài nguyên: Có thể cân đối về tài nguyên và thời gian Serial multiplication 1 Serial multiplication 2 Serial multiplication 3 Serial multiplication 4 Check LSB and add if 1 Serial multiplication 5 Serial multiplication 6 Check LSB and add if 1 Serial multiplication 7 Shift multiplicand left and multiplier right Serial multiplication 8 Check LSB and add if 1 Serial multiplication 9 • Nhân nối tiếp Serial multiplication does each partial product one ager another. • Mỗi bước là dịch và cộng nếu LSB bằng 1 → Cần 1 bộ cộng, nhưng thực hiện nhiều bước Bộ nhân song song • Cần n bộ cộng một lúc • Nhanh hơn nhưng tốn nhiều phần cứng hơn Ví dụ về bộ cộng Số có dấu Làm thế nào để biểu diễn số có dấu • Có 3 chuẩn biểu diễn – Trường dấu – Mã bù 1 – Mã bù 2 • Trong 3 chuẩn trên MSB là bit dấu (1 = negative) • Mã bù 1 không được sử dụng nhưng vẫn phải tính • Luôn sử dụng mã bù 2 cho số nguyên • Trường dấu được sử dụng biểu diễn số thực dấu phẩy động Trường dấu Đơn giản là bit đầu tiên là bit dấu: +/‐ Một số vấn đề về số có dấu Kiểm soát được dấu và trường dấu: – Nếu A âm và B âm, A+B → âm (A + B) – Nếu A dương và B dương, A+B → dương (A + B) Phức tạp hơn với đấu trừ: Tràn số trong mã bù 2 • Khác với các số không dấu (có carry out) • Tràn số có nghĩa là số không được biểu diễn • Trong phép cộng số bù 2: – Các số trái dấu nhau thì không tràn số – Tràn số nếu các số có cùng dấu lại cho kết quả khác dấu – Quy tắc: carry in đến bit dấu khác với carry out từ bit dấu • Trong cả hai ví dụ, carry in đến bit dấu == carry out So sánh các số Các toán hạng không dấu • Z: equality/inequality • C=0: A>=B • C=1: A=B – S XOR O = 1: A Số âm (S là 1 bít đầu tiên). e = 1000 00102 = 13010 -> E = 130 - 127 = 3 (e là 8 bít tiếp theo). m = 101011 -> M = 1.101011 (m là 23 bít còn lại, ở đây không cần quan tâm đến các bít 0 ở cuối vì khi ghép M = 1.m thì các số 0 này không cần viết vào) X = -1.101011 * 23 = -1101.011 = -13.375 1 10000010 1010110000000000000000 S e f Dạng chuẩn hoá Câu hỏi: Với 23 bit phần định trị và không chuẩn hoá, có bao nhiêu cách biểu diễn số Answer: 23. Lãng phí Bit! • Định dạng 1 trước phần thập phân – Cách biểu diễn số đơn giản như sau:(‐1)s x (1.f) x 2(e – 127) • Dạng không chuẩn hoá: – ví dụ: 3 giá trị thập phân ở phần định trị (‐1)S x 0.f1f2f3 x 2e • Làm thế nào để biểu diễn số 2? – (‐1)0 x 0.100 x 2(e=2) = 1/2 x 4 = 2 – (‐1)0 x 0.010 x 2(e=3) = 1/4 x 8 = 2 – (‐1)0 x 0.001 x 2(e=4) = 1/8 x 16 = 2 • Lãng phí bit dùng để biểu diễn một số theo nhiều cách Dạng chuẩn hoá chỉ có một cách: (‐1)0 x 1.000x2(e=1) =1x2=2 Phép cộng dấu phẩy động • Ví dụ: 2.1x1012 + 9.2x1010 1. Viết lại để cùng số mũ bằng việc dịch phần thập phân: 2.1x1012 + 0.092x1012 2. Cộng các phần thập phân với nhau: (2.1+0.092)x1012 = 2.192x1012 3. Làm tròn để phù hợp với số bit cần để biểu diễn: = 2.2x1012 • các bước thực hiện? – dịch (multiply) số nhỏ hơn để cùng số mũ the smaller number to match the exponents – cộng phần thập phân – làm tròn kết quả cuối cùng để phù hợp với số bit biểu diễn • phức tạp hơn tính toán số nguyên • có thể làm mất tính chính xác của các số nhỏ hơn khi cộng. Phép nhân dấu phẩy động • ví dụ: 2.1x1012 * 9.2x1010 1. nhân phần định trị (thập phân): 2.1 * 9.2 = 19.32 2. cộng các số mũ: 12 + 10 = 22 3. làm tròn (và dịch ở cơ số 10) để phù hợp với số bit cần biểu diễn: = 19.32x1022 = 1.9x1023 • các bước thực hiện? – Multiply the mantissas and add the exponents – Shift (normalize) to put the decimal point in the right place – Round at the end to fit in to the number of bits • đơn giản hơn phép cộng số thực dấu phảy động • cần bộ nhân lớn (23 bits for floats, 53 for doubles) Sai số trong dấu phẩy động • Xem xét: – Big + Small ≈ Big – 2.1x1020 + 9.2x105 = 2.1x1020+0.0000000000000092x1020 ≈ 2.1x1020 • Điều gì sẽ xảy ra khi trừ một số lớn? – có nhật được số nhỏ? – (Big + Small) – Big = ? – (Big + Small) ≈ Big – (Big + Small) – Big ≈ Big – Big = 0 – No, I get something very close to zero. • Now what happens if I try to divide by the result? – x/0 = … bad – Order of operations matters! – (Big – Big) + Small = Small • Good news: There are lots of truly excellent libraries that do the right thing for you. – This is why you do not write your own linear algebra code or FFT code Dịch để cùng số mũ trước khi cộng Floating point gives us non‐linear precision. (Remember the graph.) We only get 23 bits around one binary point. (Big or small.) Non‐integer number representation summary • Dấu phẩy cố định: xxxx.yyy – Just like integer math, but you specify how many bits for the fraction – Good if you know the range of your numbers beforehand • Dấy phẩy động (‐1)s x fff x 2eee – The fractional point is determined by the exponent – Mantissa = the fractional part – Exponent = determines where the fractional point is – Sign = positive or negative number (mantissa and exponent are not 2’s complement) – Non‐linear scale (more accuracy with smaller numbers) – Addition is complicated (need to shift to match exponents) – Multiplication is simple (just add exponents and multiple mantissas) – Division is not something you ever want to try to implement – Combining small and large numbers will lose precision • The real truth: – There are lots of nasty issues with floating point numbers. You can read about them on Wikipedia, but they will probably give you a headache Thiết kế mức logic số Mức logic số • Các kết nối logic – Các cổng – Logic → Bảng chân lý – Bảng chân lý → Các cổng(Karnaugh maps) – Các thành phần cơ bản: Bộ dồn kênh (Multiplexors), Bộ mã (encoders), bộ giải mã (decoders). • Các phần tử nối tiếp – Xây dựng bộ đếm. – Bộ nhớ và các mạch chốt. Phương trình toán học và bảng chân lý Các bảng chân lý định nghĩa trạng thái của cổng (đầu ra) với tất cả các kết nối có thể ở đầu vào. Phương trình logic và các cổng biểu diễn • A+1 = 1 • A•1 = A • A+0 = A • A•0 = 0 MUXes and DEMUXesBộ dồn kênh và phân kênh • Multiplexers (MUXes) – Lựa chọn nhiều đầu vào để ra một đầu ra tương ứng – Các tín hiệu được định tuyến • DE multiplexers (DEMUXes) – Chức năng ngược với bộ MUXes. • Các bus(tín hiệu multi‐bit) – Các bus có ký hiệu giống nhau – E.g., in là giá trị 8‐bit (8 dây) và out cũng là giá trị 8‐bit (8 dây) Encoders and decoders • Bộ giải mã (Decoders) – Chuyển đổi mã nhị phân thành 1‐hot – Số nhị phân10 == 0100 trong 1‐hot • Bộ mã hoá (Encoders) – Chuyển đổi cấu trúc 1‐ hot thành nhị phân – 1‐hot 00000010 = binary 001 Bộ nhớ • Bộ nhớ là mảng 2 chiều các phần tử bit. • Mỗi phần tử là 1 bit • Cho phép cả một hàng đọc ra một từ của dữ liệu • Chỉ có thể truy nhập một hàng tại một một thời điểm, hàng cho phép là 1 - hot Làm thế nào để xây dựng được một mảng nhớ Sử dụng địa chỉ nhị phân (binary address) để truy nhập bộ nhớ và mong muốn đầu ra là các bytes! Đọc một mảng nhớ Các mảng SRAM SRAM from ARM Các khối quan trọng • MUXes lựa chọn một đầu ra trong nhiều đầu vào: Đầu vào có thể là một bus (multiple bits) • DEMUXes chức năng ngược lại: chọn một đầu ra trong nhiều đầu ra tương ứng với một đầu vào. • DECODERS nhận giá trị nhị phân đầu vào chuyển đổi thành một đầu ra(1‐hot): giá trị nhị phân 010 biến đổi thành 1‐hot đầu ra #2 • ENCODERS nhận 1‐hot đầu vào chuyển đổi thành giá trị nhị phân: 1‐hot đầu vào #3 thành giá trị nhị phân 011 • ADDERS nhận đầu vào là A và B đầu ra là tổng (sum) – Half‐adder: A+B = {Sum, CarryOUT} – Full‐adder: A+B+CarryIN = {Sum, CarryOUT} Các phần tử trạng thái: bộ nhớ Trạng thái là gì? • Trạng thái ghi lại thông tin – Có thể thay đổi • Trạng thái bộ nhớ lưu trữ – Đầu ra thay đổi khi dữ liệu được cập nhật • Mức kết nối logic – đầu ra thay đổi ngay khi đầu vào thay đổi Ví dụ: Xây dựng một bộ đếm • Làm thế nào để tạo ra một bộ đếm? – Đếm 0, 1, 2, 3, 4, … – Tăng giá trị sau mỗi một xung đồng hồ clock signal (trạng thái thay đổi rõ rệt) • Công việc cụ thể: – Tính toán giá trị kế tiếp (e.g., 0→1, 1→2, etc.) – Lưu trữ giá trị hiện tại – Cập nhật giá trị tiếp theo • Các bước thực hiện: – Combinational: • next_value = current_value + 1 – Sequential (state): • No clock: current_value = current_value • On clock: current_value = next_value • Đây chính là cách bộ đếm chỉ đếm khi có tín hiệu đồng hồ. Tổ hợp logic của bộ đếm • Đếm như thế nào? – 0 →1, 1 → 2, 2 → 3 • Answer: An adder! • Công việc cụ thể: – Next_value = current_value + 1 • Tạo ra bộ cộng như thế nào? – SUM = A XOR B – CARRY = A AND B • Nếu lớn hơn 1 bit, ví dụ như cộng 3 bit? Input: 3 bits of A (A, A1, A2) Input: 3 bits of B (B, B1, B2) Output: 4 bits (SUM, SUM1, SUM2, COUT) Kết nối trong bộ cộng nhiều bit (ripple carry add) • Móc nối giá trị nhớ sang bộ cộng kế tiếp: – Carry out là bit 0 → Carry in là 1 • Cần bộ cộng đầy đủ!: – {CIN + A + B} → {SUM, COUT} Kiểm tra bộ cộng • Phép cộng : – 2 + 3 = 5 – A = 2 = 010 – B = 3 = 011 – Output 5 = 101 – Có nhớ ở bit thứ 3 Sử dụng bộ cộng để tạo bộ đếm • Giá trị kế tiếp: next_value = current_value + 1 – Có tất cả giá trị 3 bit • Nối dây đầu vào và đầu ra? – Kết nối các giá trị nhớ – B = 001 (+1) – A = current_value – SUM = next value Dùng mạch chốt để tránh vòng lặp hồi tiếp • Next_value = current_value + 1 • Cần phải cách ly giá trị current_value với next_value • Các mạch chốt chỉ dịch chuyển đầu ra tới đầu vào bằng tín hiệu đồng hồ : state element • Cập nhật current_value thành new_value khi có tín hiệu đồng hồ. Tín hiệu đồng hồ hoạt động như thế nào? Time → Khi clock 0→1 đầu vào của mạch chốt được lưu trữ và đầu ra sẽ được cập nhật lại tương ứng với đầu vào mới. Tốc độ tín hiệu đồng hồ • Khi sườn xung tăng (0→1) • Giá trị next_value được lưu lại như là giá trị hiện tại • Giá trị mới current_value được đưa vào bộ cộng để tạo ra giá trị mới của next_value Tổng quan: mức logic nối tiếp • Các bước thực hiện? – Phần tử trạng thái lưu giữ giá trị current state – Sử dụng tổ hợp logic để tính toán giá trị next state từ current state – Tạo ra vòng lặp hồi tiếp: • Với mỗi clock signal • The current state → next state • Đầu vào và ra tác động qua lại lẫn nhau. • Clock speed được xác định bằng việc mức logic kế tiếp cập nhật nhanh như thế nào. Summary: state elements • State elements (memories) store state • Only update at specified times (e.g., clock 0→1) • Use combinational logic (gates) to calculate the next value • Use state elements (memories) to store the current value • Update current value = next value on the clock