›

Bài giảng Binary numbers

pptx 62 trang huongle 5300
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Binary numbers", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_binary_numbers.pptx

Nội dung text: Bài giảng Binary numbers

  1. Binary numbers (And some other useful bases)
  2. 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
  3. Hệ cơ số 2 (binary)
  4. Các hệ cơ số
  5. 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 LSB– lowest value digit value digit
  6. Phép cộng, nhớ, phép nhân
  7. Phép cộng và phép nhân
  8. 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
  9. Serial multiplication 1
  10. Serial multiplication 2
  11. Serial multiplication 3
  12. Serial multiplication 4 Check LSB and add if 1
  13. Serial multiplication 5
  14. Serial multiplication 6 Check LSB and add if 1
  15. Serial multiplication 7 Shift multiplicand left and multiplier right
  16. Serial multiplication 8 Check LSB and add if 1
  17. 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
  18. 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
  19. Ví dụ về bộ cộng
  20. Số có dấu
  21. 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
  22. Trường dấu Đơn giản là bit đầu tiên là bit dấu: +/‐
  23. 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ừ:
  24. 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
  25. So sánh các số Các toán hạng không dấu Mã bù hai • Z: equality/inequality • Z: equality/inequality • C=0: A>=B • C: no meaning • C=1: A =B – S XOR O = 1: A<B • so sánh A và B, thực hiện A‐B • kiểm tra kết quả: ZERO, CARRY, SIGN, OVERFLOW
  26. Số không nguyên: số thực dấu phẩy động và cố định
  27. Các số không nguyên • Hệ cơ số 10 : 1 0 ‐1 ‐2 – 12.2510 = 1x10 + 2x10 + 2x10 + 5x10 • Hệ cơ số 2: 3 2 ‐2 – 12.2510 = 1100.01 = 1x2 + 1x2 + 1x2 • Đây là dấu phẩy cố định: – abc.def = a*22 + b*21 + c*20 + d*2‐1 + e*2‐2 + f*2‐3 – E.g., 011.110 = 2 + 1 + 1/2 + 1/4 = 3.75 • Dấu phẩy nhị phân đặt ở đâu? – Có 6 bit để biểu diễn: – xxx.yyy → max = 111.111 = 7.875, min = 000.001 = 0.125 – xxxxx.y → max = 11111.1 = 63.5, min = 00000.1 = 0.5 – x.yyyyy → max = 1.11111 = 1.96875, min = 0.00001 = 0.03125
  28. Tính toán là giống nhau đối với dấu phẩy cố định Phép cộng và phép trừ (số bù 2) là giống nhau
  29. Nhưng tồn tại một số vấn đề sau • Dấu phẩy cố định tính toán rất tốt nếu biết độ rộng – E.g., Biết số nằm trong khoảng từ +16 đến ‐16 hoặc 1.5 đến 0 → Có thể lựa chọn số bít nhị phân bên phải. – Thường sử dụng trong xử lý tín hiệu (DSPs in cell phones, etc.) – Tuy nhiên không phải lúc nào cũng biết một số có độ lớn là bao nhiêu? • Đấu phẩy động giải quyết vấn đề này: – Sử dụng một số bít để lựa chọn dấu phẩy động nhị phân – Ví dụ: Nếu có 20 bít, sử dụng 4 bit để đặt dấu phải nhị phân.
  30. Dấu phẩy động • Sử dụng một vài bít để lựa chọn dấu phẩy nhị phân – Tạo ra số lớn hoặc nhỏ bằng việc dịch chuyển dấu phẩy nhị phân. – Sử dụng các bit hiệu quả hơn! • Tổng quát một số thực X được biểu diễn theo kiểu số dấu phẩy động như sau: X = M*Re. • Trong đó: ² E là phần mũ (Exponent), E = e – 127 ² M là phần định trị (Mantissa) ² R là cơ số (Radix)
  31. Tiêu chuẩn đấu phẩy động của IEEE • Bit dấu S – Có một bit dấu: 0=positive 1=negative • Số mũ e – Giá trị không dấu, độ lệch bias “‐127” – Dễ dàng so sánh (xem xét ở phần định trị) • Phần thập phân f – Giá trị không dấu – Là các số nhị phân với dấu phẩy nhị phân bên cạnh bit có trọng số lớn nhất.
  32. Ví dụ về dấu phẩy động 32 bit 1 10000010 1010110000000000000000 S e f • S = 1 -> 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
  33. Dạng chuẩn hoá Câu hỏi: Với 23 • Định dạng 1 trước phần thập phân bit phần định trị – Cách biểu diễn số đơn giản như sau:(‐1)s x (1.f) x 2(e – 127) và không chuẩn hoá, có bao nhiêu • Dạng không chuẩn hoá: cách biểu diễn số – ví dụ: 3 giá trị thập phân ở phần định trị S e Answer: 23. (‐1) x 0.f1f2f3 x 2 Lãng phí Bit! • Làm thế nào để biểu diễn số 2? Dạng chuẩn hoá – ( 1)0 x 0.100 x 2(e=2) = 1/2 x 4 = 2 chỉ có một cách: ‐ 0 (e=1) 0 (e=3) (‐1) x 1.000x2 – (‐1) x 0.010 x 2 = 1/4 x 8 = 2 =1x2=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
  34. 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.
  35. 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)
  36. Sai số trong dấu phẩy động Dịch để cùng số mũ trước • Xem xét: khi cộng – 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? Floating point gives us non‐linear – có nhật được số nhỏ? precision. (Remember the graph.) – (Big + Small) – Big = ? We only get 23 bits around one binary – (Big + Small) ≈ Big point. (Big or small.) – (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
  37. 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
  38. Thiết kế mức logic số
  39. 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.
  40. 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.
  41. 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
  42. MUXes and DEMUXes Bộ 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)
  43. 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
  44. 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
  45. 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!
  46. Đọc một mảng nhớ
  47. 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}
  48. Các phần tử trạng thái: bộ nhớ
  49. 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
  50. 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ồ.
  51. 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)
  52. 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}
  53. 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
  54. 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
  55. 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ồ.
  56. 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.
  57. 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
  58. 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.
  59. 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