A simple mechanism to detect patterns in a sequence of bits, or taken/not taken events, is a shift register h with b bits and a table with 2^b saturated n-bit counters. h contains the history, i.e. the previous b events in the sequence.

Predicting the next branch: look at table[h]. If negative, predict "taken". If nonnegative, predict "not taken".

Updating the table: When the actual outcome of the branch is determined, update the table entry table[h]: If taken, decrement. If not taken, increment. Shift the bit representing the branch outcome into the register h.

(In the implementation, "taken" is represented as a 1, "not taken" is represented as 0.)