本篇提出內容定址記憶體 (CAMs) 的高速測試技術。根據 CAM 陣列的故障模型對電路所造成之影響，我們將故障模型分成兩類－串列測試的錯誤 (STFs) 和平行測試的錯誤 (PTFs)，對 PTFs 而言 (例: stuck-mismatched fault)，CAM 中所有的行可同時進行測試，然而，STFs 卻需一行一行循序的進行測試，所以 STFs 在測試時間中佔有很大的比例，當 CAM 的行數目增加時，測試時間就會相對的增加，為了解決這問題，我們將 CAM 陣列切割成 b 個row bank，並在每個row bank加入切換模組 (steering module)，steering module 用來切換平行測試模式 (parallel test mode) 和循序測試模式 (serial test mode)，所以 b 個 STFs 可同時進行測試，
我們並將傳統的測試演算法加以平行化，並提出針對 BCAM 與 TCAM 提出對應之平行測試演算法，這技術可明顯地改善測試速度。在所提出的高速測試技術中，b 個row bank共用一個內建自我測試電路，所以這可將內建自我測試電路的面積最小化。我們實現了一個128 × 128 具有高速測試技術的二元內容定址模式記憶體 (BCAM) 陣列。
另外為了提高內容定址模式記憶體的良率，我們也提出用區塊層級 (block level) 為單位的替換技術，例如當 defect density = 0.1時，內容定址模式記憶體切割成 16 個列區塊，每個列區塊包含兩個備用的列區塊 (row block)，其良率約 70.68%。實驗結果顯示在 512 × 512 BCAM 陣列中測試時間的減少大概有 20.08%，在同樣位元大小的三元內容定址模式記憶體 (TCAM) 中，使用 Ttcam2 演算法測試約 18.75%。本篇論文同時分析額外硬體成本、良率與可靠度改善之情形，從分析結果中得知如果 CAM 陣列有較多的行數目，額外面積就幾乎可以忽略。

High-speed testing techniques and yield enhancement techniques for content-addressable memories are proposed in this thesis. According to the fault effects of the widely used fault models for CAM arrays, the fault models can be categorized into two types－serial testable faults (STFs) and parallel testable faults (PTFs). For PTFs (e.g., stuck-mismatched faults), all CAM columns can be tested in a parallel manner. Alternatively, STFs can only be tested sequentially column by column. Therefore the test time is dominated by STFs. This situation is getting worse if the number of columns increases. To cure this dilemma, the CAM array is first partitioned into b row banks and a steering module is added for each row block. The steering module switches between the parallel test mode (for PTFs) and the serial test mode (for STFs). Therefore, b STFs can be tested at the same time. This will greatly decrease the overall test time. For the proposed techniques, the BIST circuit can be shared by b row banks. Therefore, the area of the BIST area will be minimized.
As the density and capacity of CAMs increase, it is more prone to suffer from defects. Therefore, the fabrication yield will be very low. It is inevitable to seek for efficient fault-tolerance techniques for improving the yield of CAMs. In this thesis, instead of replacing faulty cells with an entire CAM word as used in the conventional techniques, the block-based approach is presented. Redundant columns are not added here for simplicity. According to simulation results, the hardware overhead is 1.31% for a 1024 × 1024-bit CAM array. We also compare the repair rates and reliabilities of our approach with previous fault-tolerant techniques. It is also found that our approach outperforms their results.

[1] M. Fujimoto and K. Kariya, “Data compression for CAM with weighted double
tracing method,” in Proc. International Conference on Industrial Electronics
Control and Instrumentation, vol. 2, pp. 1171-1175, Sept. 1994.
[2] M. I. Sezan, H. Stark, and S. J. Yeh, “A signal processing perspective to the
operational characteristics of perceptron and Hopfield associative memory neural
networks,” in Proc. International Conference Acoustics, Speech, and Signal
Processing (ICASSP), vol. 3, pp. 1771-1774, May 1989.
[3] Y. C. Shin, R. Sridhar, V. Demjanenko, P. W. Palumbo, and S. N. Srihari, “A
special-purpose content addressable memory chip for real-time image processing,”
IEEE Journal of Solid-State Circuits, vol. 27, no. 5, pp. 737-744, May 1992.
[4] P. F. Lin and J. B. Kuo, “A 1-V 128-kb four-way set-associative CMOS cache
memory using wordline-oriented tag-compare (WLOTC) structure with the
content-addressable-memory (CAM) 10-transistor tag cell,” IEEE Journal of
Solid-State Circuits, vol. 36, no. 4, pp. 666-675, April 2001.
[5] L. Tarassenko, J. N. Tombs, and J. H. Reynolds, “Neural network architectures for
content-addressable memory,” in Proc. IEEE, vol. 138, no. 1, pp. 33-39, Feb. 1991.
[6] K. J. Lin and C. W. Wu, “Testing content-addressable memories using functional
fault models and march-like algorithms,” IEEE Trans. Computer-Aided Design of
Integrated Circuits and Systems, vol. 19, no. 5, pp. 577-588, May 2000.
[7] J. F. Li, R. S. Tzeng, and C. W. Wu, “Testing and diagnosing embedded content
addressable memories,” in Proc. IEEE VLSI Test Symposium (VTS), Monterey, CA,
pp. 389–394, Apr. 2002.
[8] United States Patent 6,496,950 B1, Whitehall et al, Dec. 17, 2002 “Testing content
addressable static memories.”
[9] J. F. Li, R. S. Tzeng, and C. W. Wu, “Testing and diagnosis methodologies for
embedded content addressable memories,” Journal Electron. Testing: Theory and
Applications, vol. 19, no. 2, pp. 207–215, Apr. 2003.
[10] D. K. Bhaysar, “A built-in self-test method for write-only content addressable
memories,” in Proc. IEEE VLSI Test Symposium (VTS), pp. 9–14, May 2005.
[11] J. F. Li and C. K. Lin, “Modeling and testing comparison faults for ternary content
addressable memories,” in Proc. IEEE VLSI Test Symposium (VTS), Palm Springs,
CA, pp. 60–65, May 2005.
[12] X. Du, S. M. Reddy, J. Rayhawk, and W. T. Cheng, “Testing delay faults in
embedded CAMs,” in Proc. IEEE Asian Test Symposium (ATS), pp. 378–383, Nov.
2003.
[13] H. H. Wu, J. N. Lee, M. C. Chiang, P. W. Liu, and C. F. Wu, “A comprehensive
TCAM test scheme: An optimized test algorithm considering physical layout and
combining scan test with at-speed BIST design,” in Proc. International Test
Conference (ITC), pp.1–10, Nov. 2009.
[14] J. F. Li, “Testing ternary content addressable memories with comparison faults
using March-Like tests,” IEEE Trans. Computer-Aided Design of Integrated
Circuits and Systems, vol. 26, no. 5, pp. 919–931, May 2007.
[15] D. Wright and M. Sachdev, “Transistor-level fault analysis and test algorithm
development for ternary dynamic content addressable memories,” in Proc.
International Test Conference (ITC), pp. 39–47, Oct. 2003.
[16] United States Reissued Patent US RE41, 659 E, Gupta et al. Sept. 7, 2010,“Methods and circuitry for built-in self-testing of content addressable memories.”
[17] J. F. Li, “Testing priority address encoder faults of content addressable memories,”
in Proc. International Test Conference (ITC), pp. 1–10, Nov. 2005.
[18] Y. J. Huang and J. F. Li, “Testing Active Neighborhood pattern-sensitive faults of
ternary content addressable memories,” in Proc. IEEE European Test Symposium
(ETS), Southampton, U. K., pp. 55–60, May 2006.
[19] Y. J. Huang and J. F. Li, “Testing ternary content addressable memories with active
neighborhood pattern-sensitive faults,” IET Proc. Computer Digital Techniques, vol.
1, no. 3, pp. 246–255, May 2007.
[20] R. Nadkarni, I. Arsovski, R. Wistort, and V. Chickanosky, “Improved match-line
test and repair methodology including power-supply noise testing for content-addressable memories,”in Proc. International Test Conference (ITC), pp.
1-9, Oct. 2006.
[21] S. Hanzawa, T. Sakata, K. Kajigaya, R. Takemura, and T. Kawahara, “A large-scale
and low-power CAM architecture featuring a one-hot-spot block code for
IP-address lookup in a network router,” IEEE Journal Solid-State Circuits, vol. 40,
no. 4, pp. 853–861, Apr. 2005.
[22] I. Arsovski and R. Nadkarni, “Low-noise embedded CAM with reduced slew-rate
match-lines and asynchronous search-lines,” in Proc. IEEE Custom Integrated
Circuits Conference (CICC), pp. 447–450, Sept. 2005.
[23] K. Pagiamtzis and A. Sheikholeslami, “A low-power content-addressable memory
(CAM) using pipelined hierarchical search scheme,” IEEE Journal Solid-State
Circuits, vol. 39, no. 9, pp. 1512–1519, Sept. 2004.
[24] K. Pagiamtzis and A. Sheikholeslami, “Pipelined match-lines and hierarchical search-lines for low-power content-addressable memories,” in Proc. IEEE Custom
Integrated Circuits Conference (CICC), pp. 383–386, Sept. 2003.
[25] United States Patent US 7,414,872 B2, J. S. Wang, Aug. 19, 2008, “Segmented
search line circuit device for content addressable memory.”
[26] J. S. Wang, C. C. Wang, and C. Yeh, “TCAM for IP-address lookup using tree-style
and-type match lines and segmented search lines,” in Proc. IEEE International
Solid-State Circuits Conference Digital Techniques Papers, pp. 577–586, Feb.
2006.
[27] S. K. Lu and G. Q. Lin, “Built-in self-repair techniques for content addressable
memories,” in Proc. IEEE International Symposium on VLSI Design, Automation
and Test (VLSI-DAT), pp. 267-270, Apr. 2009.
[28] United States Patent 6,920,525, Chadwick et al. July 19, 2005, “Method and
apparatus of local word-line redundancy in CAM.”
[29] K. Pagiamtzis and A. Sheikholeslami, “Content-addressable memory (CAM)
circuits and architectures: a tutorial and survey,” IEEE Journal of Solid-State
Circuits, vol. 41, no. 3, pp. 712–727, March 2006.
[30] K. H. Cheng, C. H. Wei, and S. Y. Jiang, “Static divided word matching line for
low-power content addressable memory design,” in Proc. International Symposium
on Circuits and Systems, pp. 629–632, May 2004
[31] H. H. Wu, J. F. Li, C. F. Wu, and C. W. Wu, “Camel: An efficient fault simulator
with coupling fault simulation enhancement for CAMs,” in Proc. Asian Test
Symposium (ATS), pp. 355–360, Oct. 2007.
[32] Y. S. Kang, J. C. Lee, and S. Kang, “Parallel BIST architecture for CAMs,”
Electronics Letters, vol. 33, no. 1, pp. 30–31, Jan. 1997.