2014年5月29日 星期四

Boolean Theorems & DeMorgan's Theorem

基本定理加法運算乘法運算
對偶定理A+0=AA.1=A
吸收定理A+1=1A.0=0
全等定理A+A=AA.A=A
補數定理A+A1.gif (144 bytes) =1A. A1.gif (144 bytes) =0
自補定理A2.gif (148 bytes)=A

 布林代數是處理數位邏輯的代數運算式,布林定理(Boolean Theorems)就是根據邏輯運算原理整理而得的布林恆等式。我們可利用這些布林恆等式來化簡複雜的布林代數運算式,而得到簡化的邏輯關係。表3.3.1是單變數的布林恆等是,表3.3.2則是多變數的布林恆等式。

1.對偶定理( Duality Theorem):加法對偶定理是一變數(A)與0執行邏輯加法(OR)運算,其運算結果都等於原來值(A)。乘法對偶定理是一變數(A)與1執行邏輯乘法(AND)運算,其運算結果都等於原來值(A)。
2.
吸收定理(Absorbtive Theorem):加法吸收定理是一變數(A)與1執行邏輯加法(OR)運算其運算結果都等於1。乘法吸收定理是一變數(A)與0執行邏輯乘法(AND)運算,其運算結果都等於0。
3.
全等定理(Equal Theorem):加法全等定理是一變數(A)與其本身執行邏輯加法(OR)運算,其運算結果都等於原來值(A)。同理,乘法全等定理是一變數(A)與其本身執行邏輯乘法(AND)運算,其運算結果都等於原來值(A)。
4.補數定理(Complementary Theorem):加法補數定理是一變數(A)與反函數(A1.gif (144 bytes))執行邏輯加法(OR)運算,其運算結果都等於1。同理,乘法補數定理是一變數(A)與反函數(A1.gif (144 bytes))執行邏輯乘法(AND)運算,其運算結果都等於0。

5.

  • 自補定理(Involution Theorem):自補定理是一變數(A)經二次邏輯補數運算(NOT)後,其運算結果等於原來值(A)。


  • 布林代數定律與多變數定理
    1.結合律
    (Associative laws):是指三個變數(ABC)在執行三變數邏輯加法或乘法運算時,可先執行其中二變數的邏輯加法(A+BB+CA+C)或乘法(ABBCAC)後,其結果在與另一變數(CAB)執行邏輯加法或乘法運算,且執行結果與直接執行三變數的邏輯加法或乘法運算相同。
      2.交換律(Commutative laws):交換律是指二個變數(AB)在執行邏輯加法(OR)運算或邏輯乘法(AND)運算時,這二個變數(AB)的先後順序並不影響執行的結果

      3.
      分配律(Distributive laws):加法分配律是指一變數(A)與多變數的積項(BC)之和(A+BC),可以被展開為和項之積((A+B)(A+C))。乘法分配律是指一個變數(A)與多個變數和項(B+C)之積(A(B+C)),可以被展開為積項之和(AB+AC)。一般代數具有乘法分配律,而布林代數則具有加法分配律與乘法分配律。

      4.
      消去律(Elimination laws):加法消去律是指一變數(A)與含有該變數的多項變數積項(AB)之和(A+AB)等於該變數值(A)。乘法消去律是指一個變數(A)與含有該變數的多變數和項(A+B)之積A(A+B)等於該變數值(A)5.
      狄摩根定理
      (Demorgan’s Theorems):狄摩根是偉大的邏輯學家和數學家,他提出布林代數中二個重要的定理;第一定理是和的補數(E2.gif (232 bytes))等於補數的積(E13.gif (247 bytes)),第二定理是積(E14.gif (213 bytes))的補數等於補數的和(E15.gif (230 bytes))。狄摩根定理不只適用於二變數,同時它也適用於多變數。


      狄摩根第一定理
      ABE2.gif (232 bytes)A.gif (148 bytes)B.gif (158 bytes)E13.gif (247 bytes)
      001111
      010100
      100010
      110000
      狄摩根第二定理
      ABE14.gif (213 bytes)A.gif (148 bytes)B.gif (158 bytes)E15.gif (230 bytes)
      001111
      011101
      101011
      110000

       資料來源
      http://content.edu.tw/vocation/control/tp_nh/control/tp_nh/logic/ch3/p3.htm


      2014年4月24日 星期四

      漢明碼概論+減錯系統

      漢明碼(Hamming Code),是在電信領域的一種線性偵錯碼,以發明者理查德·衛斯里·漢明的名字命名。漢明碼在傳輸的訊息流中插入驗證碼,以偵測並更正單一位元錯誤。由於漢明編碼簡單,它們被廣泛應用於記憶體(RAM)。其 SECDED(single error correction, double error detection)版本另外加入一檢測位元,可以偵測兩個或以下同時發生的位元錯誤,並能夠更正單一位元的錯誤。因此,當傳送端與接收端的位元樣式的漢明距離 (Hamming distance) 小於或等於1時(僅有 1 bit 發生錯誤),可實現可靠的通信。相對的,簡單的奇偶檢驗碼除了不能糾正錯誤之外,也只能偵測出奇數個的錯誤。
      在數學方面,漢明碼是一種二元線性碼。對於每一個整數m>2,存在一個編碼,帶有m個奇偶校驗位2^m-m-1個數據位。該奇偶檢驗矩陣的漢明碼是通過列出所有米欄的長度是兩兩獨立 。

      奇偶

      奇偶校驗是一種添加一個奇偶位用來指示之前的數據中包含有奇數還是偶數個1的檢驗方式。如果在傳輸的過程中,有奇數個發生了改變,那麼這個錯誤將被檢測出來(注意奇偶位本身也可能改變)。一般來說,如果數據中包含有奇數個1的話,則將奇偶位設定為1;反之,如果數據中有偶數個1的話,則將奇偶位設定為0。換句話說,原始數據和奇偶位組成的新數據中,將總共包含偶數個1.
      奇偶校驗並不總是有效,如果數據中有偶數個位發生變化,則奇偶位仍將是正確的,因此不能檢測出錯誤。而且,即使奇偶校驗檢測出了錯誤,它也不能指出哪一位出現了錯誤,從而難以進行更正。數據必須整體丟棄並且重新傳輸。在一個噪音較大的媒介中,成功傳輸數據可能需要很長時間甚至不可能完成。雖然奇偶校驗的效果不佳,但是由於他只需要一位額外的空間開銷,因此這是開銷最小的檢測方式。並且,如果知道了發生錯誤的位,奇偶校驗還可以恢複數據。

      數據位位置1234567891011121314151617181920...
      編碼後數據位置p1p2d1p4d2d3d4p8d5d6d7d8d9d10d11p16d12d13d14d15
      奇偶校驗位
      覆蓋率
      p1XXXXXXXXXX
      p2XXXXXXXXXX
      p4XXXXXXXXX
      p8XXXXXXXX
      p16
      學生概述:
      以漢明碼構築與資料相關的系統,應用於減錯的概念用途
      以資料位元數判斷應使用的檢測模型,之後構築出的檢測器當有資料錯誤即於檢測位元結果顯示錯誤目標,若無錯誤即得全檢測碼為0,此為何謂{檢測&資料系統}中並無有權為資料0之資料

      資料來源:維基百科
                      高師大王蘭華老師上課教材&講述內容
                       學生概述由學生本人統整編述

      浮點數概論

      IEEE二進位浮點數算術標準IEEE 754)是20世紀80年代以來最廣泛使用的浮點數運算標準,為許多CPU浮點運算器所採用。這個標準定義了表示浮點數的格式(包括負零-0)與反常值(denormal number)),一些特殊數值(無窮(Inf)與非數值(NaN)),以及這些數值的「浮點數運算子」;它也指明了四種數值修約規則和五種例外狀況(包括例外發生的時機與處理方式)。
      IEEE 754規定了四種表示浮點數值的方式:單精確度(32位元)、雙精確度(64位元)、延伸單精確度(43位元以上,很少使用)與延伸雙精確度(79位元以上,通常以80位元實做)。只有32位元模式有強制要求,其他都是選擇性的。大部分程式語言都有提供IEEE浮點數格式與算術,但有些將其列為非必需的。例如,IEEE 754問世之前就有的C語言,現在有包括IEEE算術,但不算作強制要求(C語言的float通常是指IEEE單精確度,而double是指雙精確度)。
      該標準的全稱為IEEE二進位浮點數算術標準(ANSI/IEEE Std 754-1985),又稱IEC 60559:1989,微處理器系統的二進位浮點數算術(本來的編號是IEC 559:1989)[1]。後來還有「與基數無關的浮點數」的「IEEE 854-1987標準」,有規定基數為2跟10的狀況。現在最新標準是「IEEE 854-2008標準」。
      在六、七十年代,各家電腦公司的各個型號的電腦,有著千差萬別的浮點數表示,卻沒有一個業界通用的標準。這給資料交換、電腦協同工作造成了極大不便。IEEE的浮點數專業小組於七十年代末期開始醞釀浮點數的標準。在1980年,英特爾公司就推出了單片的8087浮點數協處理器,其浮點數表示法及定義的運算具有足夠的合理性、先進性,被IEEE採用作為浮點數的標準,於1985年發行。而在此前,這一標準的內容已在八十年代初期被各電腦公司廣泛採用,成了事實上的業界工業標準。

      二進位浮點數是以符號數值表示法的格式儲存——最高有效位被指定為符號位(sign bit)
      ;「指數部份」,即次高有效的e個位元,儲存指數部分;最後剩下的f個低有效位的位元
      ,儲存「尾數」(significand)的小數部份(在非規約形式下整數部份默認為0,其他情況
      下一律默認為1)

      結論:(學生描述)
      浮點數為使用來簡化龐大的資料(LIKE指數)
      整串32位元,依序表示:性質符號(即正負性)佔1位元--偏移指數8位元(127-標準化次方數,2進位表示佔滿8位元)--其餘資料位23位元(補足,剩餘補0)

      資料來源:維基百科                               高師大王蘭華老師授課內容               學生整理概述

      計概--錄音測試作業

      作業網址位置: http://st84605zx.podomatic.com/entry/2014-04-24T20_18_13-07_00


       使用Audacity 錄製音檔(轉檔編碼器另外於選取對話方塊點取下載)
       再於PodOmatic上傳完成






      2014年3月25日 星期二

      0307進度:二進位 八進位 十六進位 十進位數字表示法

      這次課程主要是介紹基本的數字系統。老師從最基本的N進位數導入觀念

      任何一個屬於K進位系統的正數N都可以表示成如下多項式








      如同我們熟悉的十進位事由1~9組成,而每當增至該進位數(此時即10)跳至下位
      以此類推:二進位即0~1組成,而當增至2時就進位而得10(不是十呦)

      N進位數組成
      當然每進一位,該新增位代表多N進位之次方數(由0次起跳)
      例:一10進位數12
               10進位:1*10^1+2*10^0=12
                2進位: :1*2^3+1*2^2+0*2^1+0*2^0=1100

      十進位換二進位
      進位交換主要賴於次方關係觀念
      1.小數點前:
      就由10進位轉2進位為例,做長除法拆解(與普通長除法略不同,用欲轉位數做除數而餘數提至一旁)
      如同前段所提每位數是由次方累加,所以在長除法中愈下方所得之餘數代表愈高次方數,以此推斷所得餘數由下而上一次寫出即惟最後轉換位數

      2.小數點後:
      如同上法概念:由高位數用長除法拆開小位數組合形式
      小數點後方唯獨不同在於:從小數點出方之位數是遞減次數(即不斷降次)
      相較於增次的除法,降次當然是乘法
      到這位數判斷有概念了吧!
      取出的餘數順序當然是由上而下取(次方愈小愈至下方)

      二進位  八進位  十六進位
      這三個進位法的關係應用,不用我說也猜到次方位數關係吧
      2^1--2^3--2^4
      他們互換間有特別關係,如在2進位中由小數點出發取數組由3位組成的數轉為8進位表達
      以此類推2轉16進位即取2進位中數組由4位組成
      另外16進位當中有跳躍數字9的表達法:
      16進位計數基底:1,2,3,4,5,6,7,8,9,A,B,C,D,E,F


      資料來源:高師大王蘭華老師簡報內容
                       其餘解說歸納重點皆由學生我所著