Name Algorithm

Table of Contents

1 Barrel shifter

A barrel shifter is a digital circuit that can shift a data word by a specified number of bits in one clock cycle.

16260221182_53a096f18c_o.png

In the above image, x is input and y is output.

For shift 1, all the erjiguan on the green line exist, while others not.

1.1 shift register

16074934899_03921f148b_o.png

F0、F1、F2、F3是四个边沿触发的D触发器，每个触发器的输出端Q接到右边一个触发器的输入端D。 因为从时钟信号CP的上升沿加到触发器上开始到输出端新状态稳定地建立起来有一段延迟时间， 所以当时钟信号同时加到四个触发器上时， 每个触发器接收的都是左边一个触发器中原来的数据(F0接收的输入数据D1)。 寄存器中的数据依次右移一位。

2 Bloom Filter

It is used to judge whether an item is in a set or not.

If bloom() return false, it is false. But if bloom() return true, it may not be true.

The basic idea is, hash(item), map it in a vector of m size. The vector is 0 initially. v[hash(item)] is set to 1. To reduce fault rate, use k hash functions.

To verify, only if all k hash functions has 1 in the vector will it return true. Otherwise return false.

3 Linear congruential generator

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers.

pseudorandom number generator algorithms(PRNG).

\(X_{n+1} = (aX_n+c) mod m\)

X array is the pseudorandom.

  • \(X_0\): seed
  • m: modulus
  • a: multiplier
  • c: increment

If c = 0, the generator is often called a multiplicative congruential generator (MCG), or Lehmer RNG. If c ≠ 0, the method is called a mixed congruential generator.