1978-PAL 可程式陣列邏輯#

案件摘要#

1978 年，Monolithic Memories Inc.（MMI）的 John Birkner 與 H.T. Chua 發明 PAL（Programmable Array Logic）：只保留可程式的 AND 平面，將 OR 平面固定化，換取更快的速度與更低的成本。採用一次性燒錄的 PROM 熔絲技術，PAL16L8、PAL16R8 等型號成為 1980 年代邏輯設計的工業標準。

前因 -- 為什麼會會有這個案子#

PLA 雖然靈活，卻有三個痛點：兩級平面都可程式，導致連接點數量多、晶片面積大；可程式開關串在訊號路徑上，速度慢（當時典型傳播延遲達 \(40\sim90\,\mathrm{ns}\) ）；價格高昂（82S100 售價數十美元）。MMI 的 John Birkner 在為微處理器系統設計周邊邏輯時，親身體會到需要用多顆 TTL 晶片拼裝位址譯碼與控制邏輯的痛苦，於是提出一個「反向取捨」的構想：大多數實際應用不需要每個乘積項都能被所有輸出共享——乾脆把 OR 平面固定，只讓 AND 平面可程式。

Birkner 與 H.T. Chua 據此設計出 PAL，採用 MMI 現成的 PROM 熔絲（鎳鉻或鈦鎢）技術，一次性燒錄、不可修改。1978 年推出後，PAL16L8（組合邏輯型）與 PAL16R8（暫存器型）迅速風靡業界。PAL 的成功還有一個祕密武器：伴隨推出的 PALASM 設計軟體，讓工程師用布林方程式描述電路，由軟體自動生成燒錄圖——這是 EDA 工具與可程式邏輯結盟的先聲。

線索與推理 -- 數學式、程式、理論#

PAL 與 PLA 的取捨：固定 OR 平面換什麼？#

PLA 的連接點總數為 \(2np + pm\) （ \(n\) 輸入、 \(p\) 乘積項、 \(m\) 輸出）。PAL 因 OR 平面固定、乘積項不共享，連接點只有 AND 平面：

但代價是每個輸出只能拿到固定的 \(k\) 個乘積項（PAL16L8 為每輸出 7 個）。取捨的量化推理：

推理核心：可程式 OR 平面的「開銷」是每個交叉點一個開關元件。若 \(f_1, f_2\) 共享一個乘積項，PLA 只需 2 個 OR 交叉點；但共享的收益 \(2\) 遠小於 OR 平面全部交叉點的固定成本 \(p \times m\) 。當平均每個輸出使用的乘積項數 \(\bar{k} \ll p\) 時，固定 OR 平面幾乎不損失任何表達能力，卻省下大量面積、縮短訊號路徑（少一級可程式開關的延遲）。這是一筆典型的工程交易：以「罕用彈性」換「全面速度與成本」。

PAL16L8 與 PAL16R8 架構#

PAL16L8：16 個輸入、8 個輸出、每輸出固定 7 個乘積項（其中 1 個用於三態控制）、低態有效（L）、可程式極性。

        ┌──────────────────────────────┐
  I0 ──▶│                              │──▶ O1 (TS)
  I1 ──▶│  可程式 AND 平面              │
  ...   │  (16 輸入 × 56 乘積項)        │──▶ ...
  I7 ──▶│                              │
  I/O ─▶│         固定 OR（每輸出）      │──▶ O8 (TS)
  CLK ─▶│                              │
        └──────────────────────────────┘

PAL16R8：將 8 個輸出改為暫存器輸出（D 型正反器），回饋至 AND 平面，可用於實作同步狀態機：

暫存器型的最高時脈由路徑延遲決定：

其中 \(T_{CO}\) 為正反器 clock-to-output 延遲、 \(T_{SU}\) 為經 AND 平面後的建立時間。

SOP 化簡：Karnaugh 圖與 Quine-McCluskey#

PAL 的乘積項是稀缺資源（每輸出僅 7 個），化簡成為設計必備工序。

Karnaugh 圖法（ \(n \le 5\) 時直觀）：將相鄰的最小項圈成 \(2^k\) 大小的群組，每組化為一個乘積項。例如 \(F(A,B,C) = \sum m(1,3,5,7) = \bar{A}\bar{B}C + \bar{A}BC + A\bar{B}C + ABC\) ，圈出 \(C=1\) 的整列可得：

由 4 個乘積項化簡為 1 個——化簡倍率 \(4\times\) 。

Quine-McCluskey 演算法（可程式化、適合任意 \(n\) ）：

1. 列舉最小項：將函數寫為 \(\sum m_i\) 。
2. 分組：按最小項中 1 的個數分組。
3. 合併：相鄰組之間，僅一位元不同的兩項合併（消去該位元，記為 \(-\) ），重複直到無法合併，倖存者即為蘊含項（implicants）。
4. 找質蘊含項：未被任何合併吸收的項為質蘊含項（prime implicants）。
5. 質蘊含圖覆蓋：建立質蘊含項—最小項覆蓋表，先取「必要質蘊含項」（唯一覆蓋某最小項者），再用 Petrick 法或貪婪法補齊剩餘覆蓋。

範例： \(F = \sum m(0,1,2,5,6,7)\) （三變數）。

• 合併過程： \((0,1)\to 00-\) 、 \((0,2)\to 0-0\) 、 \((1,5)\to -01\) 、 \((2,6)\to -10\) 、 \((5,7)\to 1-1\) 、 \((6,7)\to -11\) 。
• 二次合併：無法再合併，全部為質蘊含項。
• 覆蓋表：

必要質蘊含項無一（每行皆多重覆蓋），需以覆蓋問題求解；一個最小解為 \(\{0-0, -11, 1-1\}\) ... 但組合搜尋後可知最簡解為：

這個 3 項解恰好落在 PAL 每輸出 7 項的限制內。若化簡後仍超限，設計者就得犧牲輸出、拆分函數或改用 PLA——乘積項數是 PAL 時代的硬約束。

熔絲瞬斷的原理#

PAL 的可程式點是鎳鉻（NiCr）或鈦鎢（TiW）熔絲，與 PROM 的位元熔絲同源。燒錄原理：

• 出廠時熔絲全部導通。設熔絲初始電阻 \(R_f \approx 100\,\Omega\) （導通態）。
• 燒錄器施加 \(V_{prog} \approx 10\sim21\,\mathrm{V}\) 脈衝，使電流達 \(I \approx 50\sim100\,\mathrm{mA}\) ，遠超正常工作電流。
• 焦耳熱 \(Q = I^2 R_f \Delta t\) 在數十毫秒內將熔絲加熱至熔點以上，金屬汽化、斷開，殘餘電阻 \(R_f' > 1\,\mathrm{M}\Omega\) （開路態）。

其中 \(\rho c V_{fuse}\) 為熔絲體積的熱容。斷開後該路徑在邏輯上等效於「不連接」：

• AND 平面：對輸入而言，斷開即「此變數不參與此乘積項」；
• 由於 PAL 輸入驅動的是 AND 閘的多射極輸入，燒錄一次後物理上不可逆——這就是 PAL 名稱中「一次性」的來源，也是它便宜的原因：不需要任何特殊的可重寫結構。

「瞬斷」的另一面是不可回復：燒錯一枚 PAL 就是報廢一枚。業界因此發展出「先在模擬器驗證、再燒錄」的工作流程，也催生了後續可擦除技術的需求——這正是 1985 年 GAL 案件的引信。

結案 -- 後果與影響#

PAL 以「固定 OR 平面」的取捨換來速度、成本與量產良率，成為 1980 年代邏輯設計的工業標準。MMI 在 1980 年代初被 AMD 收購，PAL 系列延續多年；PALASM 則開啟了「布林方程式輸入 → 自動化簡 → 燒錄檔輸出」的 EDA 工作流。PAL 的成功也反證了一件事：可程式邏輯的市場足夠大，值得專門的元件、工具與供應鏈。

影響條列：

• 確立「化簡演算法 + 硬體約束」的設計流程，Quine-McCluskey 與 Espresso 從學術走向工業必需品。
• PAL16R8 使可程式邏輯跨入時序（狀態機）領域，不再侷限於組合譯碼。
• 一次性熔絲的痛點直接催生 GAL／EEPROM 技術（1985 年案件）。
• PAL 的命名與「PLD」生態（JEDEC 格式、燒錄器、設計軟體）成為後續 FPGA 生態的模板。

關鍵人物與文獻#

• John Birkner（MMI）：PAL 的發明人，後來創立 Vantis 續掌 PLD 事業。
• H.T. Chua（MMI）：PAL 的共同發明人與電路設計核心。
• Monolithic Memories Inc.（MMI）：PAL 的孕育者，1980 年代被 AMD 併購。
• Birkner & Chua 專利：U.S. Patent 4,124,899「Programmable logic array circuit」（1978），PAL 架構的法律基石。
• PALASM（MMI）：首代 PLD 設計軟體，布林方程式自動化簡與燒錄圖生成。
• E. J. McCluskey：《Logic Design Principles》（Prentice Hall, 1986），Quine-McCluskey 與覆蓋演算法的權威整理。
• R. Brayton 等：《Logic Minimization Algorithms for VLSI Synthesis》（Kluwer, 1984），Espresso 化簡器，取代手繪卡諾圖的工業標準。