{"id":458,"date":"2007-09-06T19:57:51","date_gmt":"2007-09-07T02:57:51","guid":{"rendered":"http:\/\/multimedia.cx\/eggs\/how-many-multiplications\/"},"modified":"2007-09-06T19:58:23","modified_gmt":"2007-09-07T02:58:23","slug":"how-many-multiplications","status":"publish","type":"post","link":"https:\/\/multimedia.cx\/eggs\/how-many-multiplications\/","title":{"rendered":"How Many Multiplications?"},"content":{"rendered":"

While many are still dogged by the quandary of how many licks it takes to get to the chewy center of a certain popular confection<\/a>, I found myself wondering how many multiplication operations it takes to decode a frame of certain video codecs. Multiplication tends to be one of the more intensive parts of video decoding and much effort is spent minimizing the number of multiplications that are absolutely necessary. If my numbers and assumptions are correct, a 320×240 VP3<\/a>\/Theora<\/a> intraframe requires 747,680<\/strong> multiplications to decode. It goes something like this:<\/p>\n

Each 8×8 block of the image needs to be transformed and dequantized. How many blocks are in the image?<\/p>\n

\r\n Y plane: (320 * 240) pixels \/ (8 * 8) pixels\/block = 1200 blocks\r\n U plane: (160 * 120) pixels \/ (8 * 8) pixels\/block =  300 blocks\r\n V plane: (160 * 120) pixels \/ (8 * 8) pixels\/block =  300 blocks\r\n<\/pre>\n
So there are 1800 blocks<\/strong> in the frame. Each block needs to be run through an inverse discrete cosine transform (IDCT). Each of the 64 samples requires 64 mults. That means each block requires 642<\/sup> mults. However, optimizations (usually by factoring out redundant mults) result in a transform that can be performed with N*log2<\/sub>(N) mults.<\/p>\n
\r\n  64 * log2<\/sub>(64) = 384 mults\/block<\/strong>\r\n<\/pre>\n
This assumes that all of the blocks in the intraframe have enough non-zero coefficients that more optimal IDCTs (like 1-, 3-, and 10-element) are not warranted. Then there is the matter of dequantization. Assuming an average of 16 non-zero coefficients in need of dequantization, the number of mults per block rises to 400<\/strong>.<\/p>\n
\r\n 400 mults\/block * 1800 blocks\/frame = 720000 mults\/frame<\/strong>\r\n<\/pre>\n
The same number would hold true for JPEG images or MPEG-1 intraframes, given the same (possibly fraudulent) assumptions. I am not sure if 16 non-zero coefficients per block is too generous and too conservative an estimate. However, the vast majority of the blocks in a VP3\/Theora intraframe will also require 3 multiplications in order to reverse the DC prediction. So I’ll just wave my hand and factor DC prediction in with the dequantization budget of 16 mults\/block.<\/p>\n
Now, if we want to deploy the recommended post processing method, that requires 8 more multiplications per edge, where ‘edge’ is a boundary between 2 blocks that have been rendered in this frame (and all blocks are rendered for an intraframe). How many edges are in the frame?<\/p>\n
    \n
  • vertical edges = (width_in_blocks – 1) * (height_in_blocks)<\/li>\n
  • horizontal edges = (width_in_blocks) * (height_in_blocks – 1)<\/li>\n<\/ul>\n
    \r\n Y plane: 40x30 blocks, (40 - 1) * 30 + 40 * (30 - 1) = 1170 + 1160 = 2330 edges\r\n U plane: 20x15 blocks, (20 - 1) * 15 + 20 * (15 - 1) =  285 +  280 =  565 edges\r\n V plane: 20x15 blocks, (20 - 1) * 15 + 20 * (15 - 1) =  285 +  280 =  565 edges\r\n \r\n 3460 edges\/frame * 8 PP mults\/edge = 27680 PP mults\/frame<\/strong>\r\n<\/pre>\n
    Thus:<\/p>\n
    \r\n 720000 mults\/frame + 27680 mults\/frame = 747680 mults\/frame<\/strong>\r\n<\/pre>\n
    It should be noted that VP3\/Theora’s method for post-processing involves a 4-tap filter with coefficients of (1, -1, 3, -3). Trivially, the multiplication by 3 can be factored out (which is how the assumption of one mult per sample, or 8 per edge, is derived). Further, it can easily be broken down to a bit shift and addition (3*n = (n << 1) + n) so that the post processing phase does not strictly require any multiplications.\n\nNaturally, the parameters for a nominal VP3\/Theora interframe vary wildly and it's a little harder to produce an average number of multiplications for that case.\n\nI'm sure someone will be along in the comments if I messed up the math or, more likely, the assumptions.\n<\/p>\n","protected":false},"excerpt":{"rendered":"
    While many are still dogged by the quandary of how many licks it takes to get to the chewy center of a certain popular confection, I found myself wondering how many multiplication operations it takes to decode a frame of certain video codecs. Multiplication tends to be one of the more intensive parts of video […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[33],"tags":[],"class_list":["post-458","post","type-post","status-publish","format-standard","hentry","category-vp3theora"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t