Kích thước bộ đếm và Tràn bộ đếm (Counter Size and Counter Overflow)

Kích thước bộ đếm (Counter Size)

• Phải chọn bộ đếm đủ lớn để tránh tràn (overflow).
• Kích thước 4 bit/bộ đếm được gợi ý bởi xấp xỉ Poisson (Poisson approximation).
• Tải trung bình dùng k = (ln 2)m/n bộ đếm là ln 2.
• Xác suất bộ đếm có tải ít nhất 16: ≈ e^-ln2 (ln 2)¹⁶ / 16! ≈ 6.78E-17.
• Ta xem xét 4 bit/bộ đếm cho so sánh.

Tràn bộ đếm (Counter Overflow)

• Khi bộ đếm tràn, nó có thể đạt giá trị tối đa.
• Tình huống này sau có thể gây dương tính giả (false negative) chỉ nếu cuối cùng bộ đếm giảm xuống 0 khi nó nên giữ khác 0.
• Thời gian kỳ vọng cho tình huống này rất lớn nhưng cần lưu ý cho ứng dụng không cho phép false negative.
• Để tránh tràn bộ đếm, kích thước phải đủ lớn. Đã thấy 4 bit mỗi bộ đếm là đủ.