Idea: For each branch, count how many times it was taken and how often it was not taken. If it was taken more often than not, predict that it will be taken the next time, too.

Implementation: again, use the lower a bits of the branch instruction's address as the index into a table of 2^a n-bit counters. When a branch is fetched, take its address modulo 2^a and look at the corresponding table entry. If negative, predict taken. If nonnegative, predict not taken. Later, when the actual outcome of the branch is determined, update the counter: decrement if taken, increment if not taken. Use saturated operations on the counter: don't increment beyond the maximum value 2^n-1-1 and don't decrement below the minimum value -2^n-1.