In video coding, before arithmetic coding, we need to binarize the symbols that need to be transmitted. Today we will learn some common binarization methods.

Common binary coding algorithms are: Uniary code, truncated Uniary code, truncated Rice binary, K-order exponential Columbus coding, fixed-length coding, where fixed-length coding is not introduced.

Unicode

Reference resources:
https://en.wikipedia.org/wiki/Unary_coding

Unicode is a very simple binarization method. For non-negative integer N, its one-digit code is expressed as N 1 plus 1 0.
For example, N=5, the Unicode is 11 110 (5 1 plus 1 0), N=0, and the Unicode is 0.

HEVC code (actually the function is not called in the code):

//uiSymbol: Symbols to be coded
Void TEncSbac::xWriteUnarySymbol( UInt uiSymbol, ContextModel* pcSCModel, Int iOffset )
{
    //Using conventional coder, uiSymbol is 0, encoding is 0, otherwise encoding is 1
	m_pcBinIf->encodeBin( uiSymbol ? 1 : 0, pcSCModel[0] );
 
    //uiSymbol 0, end coding ()
	if( 0 == uiSymbol)
	{
		return;
	}
    
    //Encoding (uiSymbol-1) 1 plus 1 0 (plus the first encoding 1, that is, encoding uiSymbol 1 plus 1 0)
	while( uiSymbol-- )
	{
		m_pcBinIf->encodeBin( uiSymbol ? 1 : 0, pcSCModel[ iOffset ] );
	}
 
	return;
}

VVC code also does not use unary code, remove the function.

Truncated Unary

Reference resources:
https://blog.51cto.com/7335580/2070466

Truncated unary code is a variant of unary code. Given the maximum Nmax of the symbol to be coded, assuming that the current symbol to be coded is a non-negative integer N, if N < Nmax, the truncated Unicode is a unicode, and if N=Nmax, the truncated Unicode is N 1.
For example, known Nmax=5, N=3, truncated Unicode 1100, N=5, truncated Unicode 11111.

HEVC code (truncated monic code is used in mvp-index, delta-qp and other grammatical element encoding):

//uiSymbol: Symbols to be coded
//uiMaxSymbol: Maximum of known syntax elements to be coded
Void TEncSbac::xWriteUnaryMaxSymbol( UInt uiSymbol, ContextModel* pcSCModel, Int iOffset, UInt uiMaxSymbol )
{
	if (uiMaxSymbol == 0)
	{
		return;
	}
 
	 //Using conventional coder, uiSymbol is 0, encoding is 0, otherwise encoding is 1
	m_pcBinIf->encodeBin( uiSymbol ? 1 : 0, pcSCModel[ 0 ] );
	
    //uiSymbol 0, end coding ()
	if ( uiSymbol == 0 )
	{
		return;
	}
 
	// Judging whether truncation is necessary
	Bool bCodeLast = ( uiMaxSymbol > uiSymbol );
 
	//Coding (uiSymbol-1) 1
	while( --uiSymbol )
	{
		m_pcBinIf->encodeBin( 1, pcSCModel[ iOffset ] );
	}
	
	// Without truncation, add 0 directly at the end
	if( bCodeLast )
	{
		m_pcBinIf->encodeBin( 0, pcSCModel[ iOffset ] );
	}
 
	return;
}

Functions are modified in VC code:

//Symbol: symbol to be coded
void CABACWriter::unary_max_symbol( unsigned symbol, unsigned ctxId0, unsigned ctxIdN, unsigned maxSymbol )
{
  //Symbol > maxSymbol throws an exception, and the normal situation should be symbol <= maxSymbol
  CHECK( symbol > maxSymbol, "symbol > maxSymbol" );
  
  //Write out the total number of bin, when symbo < maxSymbol, truncated one-dollar code write symbo+1 bin; when symbo=maxSymbol, truncated one-dollar code write maxSymbol one bin.
  const unsigned totalBinsToWrite = std::min( symbol + 1, maxSymbol );
  
  //Symbol is binarized and coded with truncated unary code. When symbol=maxSymbol, total BinsToWrite = symbol will output symbols 1; when symbol < maxSymbol 0, total BinsToWrite = symbol + 1, will output symbols 1 plus 1 0.
  for( unsigned binsWritten = 0; binsWritten < totalBinsToWrite; ++binsWritten )
  {
    const unsigned nextBin = symbol > binsWritten;
    m_BinEncoder.encodeBin( nextBin, binsWritten == 0 ? ctxId0 : ctxIdN );
  }
}

Truncated Rice code

Reference resources:
https://blog.csdn.net/u012803718/article/details/16992915

Truncated Rice codes include prefix and suffix. The maximum upper limit cMax and Rice parameters are known. The coded symbol cVal is coded:
1. Calculate prefix:
Prefix = cVal > > cRice, for prefix, the use of truncated binary code is limited to cMax > cRice.

2. Calculate suffix:
If cVal < cMax: suffix = cVal - prefix > cRice.
If cVal >= cMax: suffix-free.
suffix is calculated as a fixed-length code with the digit cRice.

As you can see, when cRice=0, truncation of Rice code is actually truncation of unary code.

The truncated Les code in the code is only used when coding coefficients, and there is no independent function to implement it.

k-order exponential Columbus code

Reference resources:
https://baike.baidu.com/item/%E6%8C%87%E6%95%B0%E5%93%A5%E4%BC%A6%E5%B8%83%E7%A0%81/22742504?fr=aladdin
https://www.cnblogs.com/wangguchangqing/p/6297792.html

The k-order exponential Columbus code is also composed of prefix and suffix. The coding method is as follows:
1. Write the digit X in binary form, remove the lowest k bits, and then add 1 to get T.
2. To calculate the number of bits of T, we need to add T-1 zeros.
3. The lowest k bits removed will be compensated back to the end of the bit string.

The prefix is the complement of T-1 plus 1 (1 is added in step 1, so that T is greater than or equal to 1, which is sure to be found), and the remainder is the suffix. That is to say, the dividing line between prefix and suffix is the first 1, which is prefix with all the previous 0, and this 1 is suffix.
The prefix and suffix are not explained in detail here. It is recommended to see https://www.cnblogs.com/wangguchangqing/p/6297792.html.

for example
X=4, k=1 exponential Columbus code is:
1.4 binary code is 100, after removing 1 bit, add 1, T=11.
2.T has two places, one zero is added in front.
3. Add a 10 after T, that is 0110, of which 01 is the prefix and 10 is the suffix.

In HEVC and VC, the first-order exponential Columbus codes are generally used. It should be noted that the k-order exponential Columbus codes used in practice are different. The algorithm given in draft is illustrated here.

According to draft algorithm, we try to calculate the first-order exponential Columbus code of 4. The final code word is 1010, which is different from the previous method. There is no separate explanation for this in draft. I compared several groups of results:

Observation prefix (coarsened), HEVC coding results are contrary to the prefix of theoretical values, which I think is for easy storage and expression. Code, the encoding results are still stored in integers, high-bit 0 can not be stored and expressed, so the prefix is inversed, so high-bit must be 1, you can record the encoding results, very clever.

The HEVC code is as follows:

// uiSymbol: Symbols to be coded
// uiCount: Order K
Void TEncSbac::xWriteEpExGolomb( UInt uiSymbol, UInt uiCount )
{
	UInt bins = 0;
	Int numBins = 0;
 
	while( uiSymbol >= (UInt)(1<<uiCount) )
	{
		bins = 2 * bins + 1;
		numBins++;
		uiSymbol -= 1 << uiCount;
		uiCount  ++;
	}
	bins = 2 * bins + 0;
	numBins++;
	bins = (bins << uiCount) | uiSymbol;
	numBins += uiCount;
	assert( numBins <= 32 );
	m_pcBinIf->encodeBinsEP( bins, numBins );
}

The VC code has been slightly changed, replacing the multiply 2 operation with shift:

void CABACWriter::exp_golomb_eqprob( unsigned symbol, unsigned count )
{
  unsigned bins    = 0;
  unsigned numBins = 0;
  while( symbol >= (unsigned)(1<<count) )
  {
    bins <<= 1;
    bins++;
    numBins++;
    symbol -= 1 << count;
    count++;
  }
  bins <<= 1;
  numBins++;
  bins = (bins << count) | symbol;
  numBins += count;
  CHECK(!( numBins <= 32 ), "Unspecified error");
  m_BinEncoder.encodeBinsEP( bins, numBins );
}