text:
#### You may also like

A quadrilateral changes shape with the edge lengths constant. Show the scalar product of the diagonals is constant. If the diagonals are perpendicular in one position are they always perpendicular?

As a quadrilateral Q is deformed (keeping the edge lengths constnt) the diagonals and the angle X between them change. Prove that the area of Q is proportional to tanX.

### Air Routes

Find the distance of the shortest air route at an altitude of 6000 metres between London and Cape Town given the latitudes and longitudes. A simple application of scalar products of vectors.

# Cross with the Scalar Product

##### Stage: 5 Challenge Level:

Always remember the key geometrical facts about scalar and cross products for non-zero vectors ${\bf u}$ and ${\bf v}$:

1) ${\bf u}\cdot {\bf v}=0$ if and only if ${\bf u}$ and ${\bf v}$ are perpendicular.

2) ${\bf u}\times {\bf v}=0$ if and only if ${\bf u}$ and ${\bf v}$ are parallel.

3) ${\bf u}\times {\bf v}$ is perpendicular to both ${\bf u}$ and ${\bf v}$.

This problem uses mathematical concepts covered in the later Further Pure Mathematics A Level Modules.


text:
SERVING THE QUANTITATIVE FINANCE COMMUNITY

• 1
• 2

yondaime
Topic Author
Posts: 3
Joined: May 18th, 2020, 8:46 pm

### Interpolation of a Implied Volatility Surface

Hi,

I have an Implied volatility surface. I was using cubic spline interpolation to estimate the volatility at the in between points. However, the volatility data I have is a bit extreme because of rare events like Brexit. This is why the cubic spline isn't working everytime as there are arbitrage opportunities created.

Can you suggest better interpolation techniques such as those probably used by banks to combat such real cases?

Alan
Posts: 10462
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: Interpolation of a Implied Volatility Surface

There is a nice method by
Note the distinction between interpolating splines and smoothing splines.

Cuchulainn
Posts: 63371
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Interpolation of a Implied Volatility Surface

Cubic splines overshoot for sparse data. This is well known.

http://finmod.co.za/Interpolation%20Summary.pdf

I reckon you need a monotonicity-preserving method.

Cuchulainn
Posts: 63371
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Interpolation of a Implied Volatility Surface

There is a nice method by
Note the distinction between interpolating splines and smoothing splines.

Alan
Posts: 10462
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: Interpolation of a Implied Volatility Surface

There is a nice method by
Note the distinction between interpolating splines and smoothing splines.
Just tried it in Chrome -- loaded fine.
If not working for you, the title is "Arbitrage-Free Smoothing of the Implied Volatility Surface"

Cuchulainn
Posts: 63371
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Interpolation of a Implied Volatility Surface

Seems to be working now.Thanks.

fomisha
Posts: 67
Joined: December 30th, 2003, 4:28 pm

### Re: Interpolation of a Implied Volatility Surface

If you need an industrial-strength solution you can check out Vola Dynamics (disclaimer - I am affiliated).

Here is an example of a fully automated fit right before Brexit:

The fits are parametric, arb-free, very robust, and fairly fast.

jkg77
Posts: 6
Joined: September 5th, 2020, 8:46 am

### Re: Interpolation of a Implied Volatility Surface

If you need an industrial-strength solution you can check out Vola Dynamics (disclaimer - I am affiliated).

Here is an example of a fully automated fit right before Brexit:

The fits are parametric, arb-free, very robust, and fairly fast.
Impressive.  I cannot believe any parametric models can achieve such robust results.. liquid or illiquid, ATM or wings..  Are there any public models that can achieve anything similar.. or closer..?

Alan
Posts: 10462
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: Interpolation of a Implied Volatility Surface

If you need to extrapolate the IV time slices outside the available strikes, I have some nice fits here. See pages  30, 31.

I am using Gaussian mixture model fits, which have some nice properties, esp. for my application (equity risk premium), and lead to interesting extrapolations.

However, calendar arb removal, which is discussed in the paper, is somewhat ad hoc, and would require more work to assure. That was a peripheral issue for me, so haven't pursued it beyond the discussion in the paper. The two solutions discussed above are apparently arb-free.

jkg77
Posts: 6
Joined: September 5th, 2020, 8:46 am

### Re: Interpolation of a Implied Volatility Surface

If you need to extrapolate the IV time slices outside the available strikes, I have some nice fits here. See pages  30, 31.

I am using Gaussian mixture model fits, which have some nice properties, esp. for my application (equity risk premium), and lead to interesting extrapolations.

However, calendar arb removal, which is discussed in the paper, is somewhat ad hoc, and would require more work to assure. That was a peripheral issue for me, so haven't pursued it beyond the discussion in the paper. The two solutions discussed above are apparently arb-free.
Hi Alan, my main objective is to get a smoothed vol smile (I don't worry about the entire vol surface for this particular purpose) that can fits within bid/ask for all the quoted strikes in all cases (ATM/wings, liquid or illiquid). The best result I have so far is Fengler that you recommended above. However there are still many cases that the smoothed vols stay outside of bid/ask no matter how I tune the smoothing factor..

Alan
Posts: 10462
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: Interpolation of a Implied Volatility Surface

Hi, perhaps you can post a plot that shows a problematic case, showing the IV_bid - IV_ask intervals at each strike. Also, sometimes the cost-of-carry method is a source of problems, so you might explain how you handled that.

jkg77
Posts: 6
Joined: September 5th, 2020, 8:46 am

### Re: Interpolation of a Implied Volatility Surface

Hi, perhaps you can post a plot that shows a problematic case, showing the IV_bid - IV_ask intervals at each strike. Also, sometimes the cost-of-carry method is a source of problems, so you might explain how you handled that.
I wasn't able to find an example quickly.. I observed this many times intraday on some illiquid names. You may be right as some underlyings were often hard-to-borrow which I probably didn't factor-in in the model properly. Sometimes I want to have a simple view on "BS implied vol without cost-of-carry".. [I know this is clearly 'wrong' but this is sometimes easier and more convenient for me to make trading decision.]

Is there any better approach to calibrate the model to find optimal smoothing parameter? The AIC in the paper is based on unconstrainted smoother (i.e, not the optimal choice) and tends to over-smooth so practically not very useful to me. This was explained in the paper but nothing better was recommended. Any thoughts?  Many thanks

Alan
Posts: 10462
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: Interpolation of a Implied Volatility Surface

I would suggest just using judgment on where the smoothed smiles should lie in relation to the market IV(bid)-IV(ask). In liquid names (AAPL, TSLA) you can likely use Fengler's method to smoothly fit inside every quote. Learn what smoothing parameters accomplish that.

jkg77
Posts: 6
Joined: September 5th, 2020, 8:46 am

### Re: Interpolation of a Implied Volatility Surface

I watch many markets simultaneously so the automatic calibration on the smoothing parameter is kinda important. It's fine to have the calibrated smoothing parameter a bit off from my judgement but at least it should be close (i.e. fit everything within bid/ask)

Alan
Posts: 10462
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: Interpolation of a Implied Volatility Surface

I watch many markets simultaneously so the automatic calibration on the smoothing parameter is kinda important. It's fine to have the calibrated smoothing parameter a bit off from my judgement but at least it should be close (i.e. fit everything within bid/ask)

Well, I give an objective function that I like at eqn (18) of my paper that I cited. Perhaps you could choose the smoothing parameter to minimize that and see if you like the results. Now, $C^{model}_i$ would be the Fengler fits as a function of the smoothing parameter. Note C stands for the out-of-the-money puts or calls, puts on the downside strikes and calls on the upside. But, you likely need more careful cost-of-carrys to use that formula.

format: plain


text:
## The Question :

354 people think this question is useful

I am creating a program that will download a .jar (java) file from a web server, by reading the URL that is specified in the .jad file of the same game/application. I’m using Python 3.2.1

I’ve managed to extract the URL of the JAR file from the JAD file (every JAD file contains the URL to the JAR file), but as you may imagine, the extracted value is type() string.

Here’s the relevant function:

def downloadFile(URL=None):
import httplib2
h = httplib2.Http(".cache")
resp, content = h.request(URL, "GET")
return content

However I always get an error saying that the type in the function above has to be bytes, and not string. I’ve tried using the URL.encode(‘utf-8′), and also bytes(URL,encoding=’utf-8’), but I’d always get the same or similar error.

So basically my question is how to download a file from a server when the URL is stored in a string type?

• @alvas, A bounty for this? The answerer is still (and quite) active on SO. Why not just add a comment and ask?
• Cos a good answer that lasts the test of time is worth awarding. Also, we should start doing this for a lot of other questions to check whether answers are relevant today. Especially when the sorting of SO answers are rather crazy, sometimes the out-dated or even worst answer goes to the top.

693 people think this answer is useful

If you want to obtain the contents of a web page into a variable, just read the response of urllib.request.urlopen:

import urllib.request
...
url = 'http://example.com/'
response = urllib.request.urlopen(url)
data = response.read()      # a bytes object
text = data.decode('utf-8') # a str; this step can't be used if data is binary

The easiest way to download and save a file is to use the urllib.request.urlretrieve function:

import urllib.request
...
# Download the file from url and save it locally under file_name:
urllib.request.urlretrieve(url, file_name)

import urllib.request
...
# Download the file from url, save it in a temporary directory and get the
# path to it (e.g. '/tmp/tmpb48zma.txt') in the file_name variable:

But keep in mind that urlretrieve is considered legacy and might become deprecated (not sure why, though).

So the most correct way to do this would be to use the urllib.request.urlopen function to return a file-like object that represents an HTTP response and copy it to a real file using shutil.copyfileobj.

import urllib.request
import shutil
...
# Download the file from url and save it locally under file_name:
with urllib.request.urlopen(url) as response, open(file_name, 'wb') as out_file:
shutil.copyfileobj(response, out_file)

If this seems too complicated, you may want to go simpler and store the whole download in a bytes object and then write it to a file. But this works well only for small files.

import urllib.request
...
# Download the file from url and save it locally under file_name:
with urllib.request.urlopen(url) as response, open(file_name, 'wb') as out_file:
data = response.read() # a bytes object
out_file.write(data)

It is possible to extract .gz (and maybe other formats) compressed data on the fly, but such an operation probably requires the HTTP server to support random access to the file.

import urllib.request
import gzip
...
# Read the first 64 bytes of the file inside the .gz archive located at url
url = 'http://example.com/something.gz'
with urllib.request.urlopen(url) as response:
with gzip.GzipFile(fileobj=response) as uncompressed:
file_header = uncompressed.read(64) # a bytes object
# Or do anything shown above using uncompressed instead of response.

159 people think this answer is useful

I use requests package whenever I want something related to HTTP requests because its API is very easy to start with:

first, install requests

\$ pip install requests

then the code:

from requests import get  # to make GET request

# open in binary mode
with open(file_name, "wb") as file:
# get request
response = get(url)
# write to file
file.write(response.content)

18 people think this answer is useful

I hope I understood the question right, which is: how to download a file from a server when the URL is stored in a string type?

import requests

url = 'https://www.python.org/static/img/python-logo.png'
fileName = 'D:\Python\dwnldPythonLogo.png'
req = requests.get(url)
file = open(fileName, 'wb')
for chunk in req.iter_content(100000):
file.write(chunk)
file.close()

11 people think this answer is useful

You can use wget which is popular downloading shell tool for that. https://pypi.python.org/pypi/wget This will be the simplest method since it does not need to open up the destination file. Here is an example.

import wget

10 people think this answer is useful

Here we can use urllib’s Legacy interface in Python3:

The following functions and classes are ported from the Python 2 module urllib (as opposed to urllib2). They might become deprecated at some point in the future.

Example (2 lines code):

import urllib.request

url = 'https://www.python.org/static/img/python-logo.png'
urllib.request.urlretrieve(url, "logo.png")

2 people think this answer is useful

Yes, definietly requests is great package to use in something related to HTTP requests. but we need to be careful with the encoding type of the incoming data as well below is an example which explains the difference

from requests import get

# case when the response is byte array
url = 'some_image_url'

response = get(url)
with open('output', 'wb') as file:
file.write(response.content)

# case when the response is text
# Here unlikely if the reponse content is of type **iso-8859-1** we will have to override the response encoding
url = 'some_page_url'

response = get(url)
# override encoding by real educated guess as provided by chardet
r.encoding = r.apparent_encoding

with open('output', 'w', encoding='utf-8') as file:
file.write(response.content)

0 people think this answer is useful

# Motivation

Sometimes, we are want to get the picture but not need to download it to real files,

For example, If I use the machine learning method, train a model that can recognize an image with the number (bar code).

When I spider some websites and that have those images so I can use the model to recognize it,

and I don’t want to save those pictures on my disk drive,

# Points

import requests
from io import BytesIO
response = requests.get(url)
with BytesIO as io_obj:
for chunk in response.iter_content(chunk_size=4096):
io_obj.write(chunk)

basically, is like to @Ranvijay Kumar

# An Example

import requests
from typing import NewType, TypeVar
from io import StringIO, BytesIO
import matplotlib.pyplot as plt
import imageio

URL = NewType('URL', str)
T_IO = TypeVar('T_IO', StringIO, BytesIO)

chunk_size = option.get('chunk_size', 4096)  # default 4KB
max_size = 1024 ** 2 * option.get('max_size', -1)  # MB, default will ignore.
if response.status_code != 200:
raise requests.ConnectionError(f'{response.status_code}')

instance_io = StringIO if isinstance(next(response.iter_content(chunk_size=1)), str) else BytesIO
io_obj = instance_io()
cur_size = 0
for chunk in response.iter_content(chunk_size=chunk_size):
cur_size += chunk_size
if 0 < max_size < cur_size:
break
io_obj.write(chunk)
io_obj.seek(0)
""" save it to real file.
with open('temp.png', mode='wb') as out_f:
"""
return io_obj

def main():
'Accept': 'text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3',
'Accept-Encoding': 'gzip, deflate',
'Accept-Language': 'zh-TW,zh;q=0.9,en-US;q=0.8,en;q=0.7',
'Cache-Control': 'max-age=0',
'Connection': 'keep-alive',
'Host': 'statics.591.com.tw',
'User-Agent': 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/78.0.3904.87 Safari/537.36'
}
headers,  # You may need this. Otherwise, some websites will send the 404 error to you.
with io_img:
plt.rc('axes.spines', top=False, bottom=False, left=False, right=False)
plt.rc(('xtick', 'ytick'), color=(1, 1, 1, 0))  # same of plt.axis('off')
plt.show()

if __name__ == '__main__':
main()

0 people think this answer is useful

If you are using Linux you can use the wget module of Linux through the python shell. Here is a sample code snippet

import os
url = 'http://www.example.com/foo.zip'
os.system('wget %s'%url)

-3 people think this answer is useful
from urllib import request

def get(url):
with request.urlopen(url) as r:


text:
# Multistage Survey Sample for Sock Color

Here is the setup:

We want to estimate the proportion of people in a country who wear black socks versus not-black socks. We have 100 cities (primary sampling units) in the country. In each city there are a certain number of blocks (secondary sampling unit) and in each block there are a certain number of houses (tertiary sampling units). We do not know the number of blocks, houses, or people before sampling begins. Once we select a house we do a census of all occupants to determine their sock colors. The sock color for each occupant will be reported as bs=1 for black socks and bs=0 for not-black socks.

The sampling commences by randomly selecting a number of cities, 10 for example. In each selected city we enumerate the number of blocks in that city. In each of the selected cities a number of blocks (say 5) are chosen at random. In each of the selected blocks the number of houses on that block is enumerated. Finally, a number of houses (say 5) on each chosen block is selected at random and the sock-color census performed in each of these houses. Given this information we can assign a sampling probability p to each house selected. The datafile will consist of a row for each person, listing the city.ID, block.ID, house.ID, p, and bs.

And here are the questions:

(1) Is this a valid sampling design, i.e., given the information provided can we get reasonable estimates of the proportion of people in the country who wear black socks and the standard error of the estimate?

(2) Is this how one might specify the design in R and Stata and calculate the result?

design <- svydesign(~city.ID+block.ID+house.ID,probs=~p,data=sampfile)
svymean(~bs,design)

gen wt = 1/p
svyset city.ID [pweight=wt], vce(linearized) singleunit(missing) || block.ID || house.ID
svy: mean bs

• This doesn't appear to even be a multistage design. You're selecting a single unit then repeating selections from the PSU stage, with no apparent relationship to the unit/s already selected. – RoryT Mar 30 '18 at 10:06
• @RoryT, it was not. See if the revised question is any better. – Thomas Mar 30 '18 at 16:53

It is a perfectly valid design, but at each stage, you would need to specify the number of units in the population at that stage:

1. number of cities you sample from,
2. number of block in a city you sample from, specific for each city,
3. number of housing units in a block, specific to that block.

That would be

design <- svydesign(id=~city.ID+block.ID+house.ID,
fpc=~num.cities+num.blocks+num.houses,
probs=~p,data=sampfile)
svymean(~bs,design)

in R (see section 3.2 of Thomas Lumley's book (https://www.amazon.com/Complex-Surveys-Guide-Analysis-Using/dp/0470284307), or

svyset city_ID [pweight=wt], fpc(num_cities) || ///
block_ID, fpc(num_blocks) || house_ID, fpc(num_houses)

in Stata (the dots in the variable names will freak it out, I replaced them with undescores)

Without the finite population corrections (FPC), either software will assume sampling with replacement, and ignore the subsequent stages.

• Note that you need to protect against the missing data on people who always go barefoot. If people in four houses out five don't wear socks, this would appear like a singleton PSU. Just a fair warning. – StasK Mar 30 '18 at 17:00
• I was more concerned about the individuals wearing one black sock and one non-black sock (based on personal experience). – Thomas Mar 30 '18 at 17:04


text:
BIP-37

# BIP-37

BIP: 37
Layer: Peer Services
Title: Connection Bloom filtering
Author: Mike Hearn <[email protected]>
Matt Corallo <[email protected]>
Status: Final
Type: Standards Track
Created: 2012-10-24

## Abstract

This BIP adds new support to the peer-to-peer protocol that allows peers to reduce the amount of transaction data they are sent.
Peers have the option of setting ‘‘filters’’ on each connection they make after the version handshake has completed.
A filter is defined as a Bloom filter on data derived from transactions.
A Bloom filter is a probabilistic data structure which allows for testing set membership - they can have false positives but not false negatives.

This document will not go into the details of how Bloom filters work and the reader is referred to Wikipedia for an introduction to the topic.

## Motivation

As Bitcoin grows in usage the amount of bandwidth needed to download blocks and transaction broadcasts increases.
Clients implementing ‘‘simplified payment verification’’ do not attempt to fully verify the block chain, instead just checking that block headers connect together correctly and trusting that the transactions in a chain of high difficulty are in fact valid.
See the Bitcoin paper for more detail on this mode.

Today, clients have to download the entire contents of blocks and all broadcast transactions, only to throw away the vast majority of the transactions that are not relevant to their wallets.
This slows down their synchronization process, wastes users bandwidth (which on phones is often metered) and increases memory usage.
All three problems are triggering real user complaints for the Android “Bitcoin Wallet” app which implements SPV mode.
In order to make chain synchronization fast, cheap and able to run on older phones with limited memory we want to have remote peers throw away irrelevant transactions before sending them across the network.

## Design rationale

The most obvious way to implement the stated goal would be for clients to upload lists of their keys to the remote node.
We take a more complex approach for the following reasons:

• Privacy: Because Bloom filters are probabilistic, with the false positive rate chosen by the client, nodes can trade off precision vs bandwidth usage.
A node with access to lots of bandwidth may choose to have a high FP rate, meaning the remote peer cannot accurately know which transactions belong to the client and which don’t.
A node with very little bandwidth may choose to use a very accurate filter meaning that they only get sent transactions actually relevant to their wallet, but remote peers may be able to correlate transactions with IP addresses (and each other).
• Bloom filters are compact and testing membership in them is fast.
This results in satisfying performance characteristics with minimal risk of opening up potential for DoS attacks.

## Specification

### New messages

We start by adding three new messages to the protocol:

• filterload, which sets the current Bloom filter on the connection
• filteradd, which adds the given data element to the connections current filter without requiring a completely new one to be set
• filterclear, which deletes the current filter and goes back to regular pre-BIP37 usage.

Note that there is no filterremove command because by their nature, Bloom filters are append-only data structures.
Once an element is added it cannot be removed again without rebuilding the entire structure from scratch.

The filterload command is defined as follows:

Field Size Description Data type Comments
? filter uint8_t[] The filter itself is simply a bit field of arbitrary byte-aligned size. The maximum size is 36,000 bytes.
4 nHashFuncs uint32_t The number of hash functions to use in this filter. The maximum value allowed in this field is 50.
4 nTweak uint32_t A random value to add to the seed value in the hash function used by the bloom filter.
1 nFlags uint8_t A set of flags that control how matched items are added to the filter.

See below for a description of the Bloom filter algorithm and how to select nHashFuncs and filter size for a desired false positive rate.

Upon receiving a filterload command, the remote peer will immediately restrict the broadcast transactions it announces (in inv packets) to transactions matching the filter, where the matching algorithm is specified below.
The flags control the update behaviour of the matching algorithm.

The filteradd command is defined as follows:

Field Size Description Data type Comments
? data uint8_t[] The data element to add to the current filter.

The data field must be smaller than or equal to 520 bytes in size (the maximum size of any potentially matched object).

The given data element will be added to the Bloom filter.
A filter must have been previously provided using filterload.
This command is useful if a new key or script is added to a clients wallet whilst it has connections to the network open, it avoids the need to re-calculate and send an entirely new filter to every peer (though doing so is usually advisable to maintain anonymity).

The filterclear command has no arguments at all.

After a filter has been set, nodes don’t merely stop announcing non-matching transactions, they can also serve filtered blocks.
A filtered block is defined by the merkleblock message and is defined like this:

Field Size Description Data type Comments
4 version uint32_t Block version information, based upon the software version creating this block
32 prev_block char[32] The hash value of the previous block this particular block references
32 merkle_root char[32] The reference to a Merkle tree collection which is a hash of all transactions related to this block
4 timestamp uint32_t A timestamp recording when this block was created (Limited to 2106!)
4 bits uint32_t The calculated difficulty target being used for this block
4 nonce uint32_t The nonce used to generate this block… to allow variations of the header and compute different hashes
4 total_transactions uint32_t Number of transactions in the block (including unmatched ones)
? hashes uint256[] hashes in depth-first order (including standard varint size prefix)
? flags byte[] flag bits, packed per 8 in a byte, least significant bit first (including standard varint size prefix)

See below for the format of the partial merkle tree hashes and flags.

Thus, a merkleblock message is a block header, plus a part of a merkle tree which can be used to extract identifying information for transactions that matched the filter and prove that the matching transaction data really did appear in the solved block.
Clients can use this data to be sure that the remote node is not feeding them fake transactions that never appeared in a real block, although lying through omission is still possible.

### Extensions to existing messages

The version command is extended with a new field:

Field Size Description Data type Comments
1 byte fRelay bool If false then broadcast transactions will not be announced until a filter{load,add,clear} command is received. If missing or true, no change in protocol behaviour occurs.

SPV clients that wish to use Bloom filtering would normally set fRelay to false in the version message, then set a filter based on their wallet (or a subset of it, if they are overlapping different peers).
Being able to opt-out of inv messages until the filter is set prevents a client being flooded with traffic in the brief window of time between finishing version handshaking and setting the filter.

The getdata command is extended to allow a new type in the inv submessage.
The type field can now be MSG_FILTERED_BLOCK (== 3) rather than MSG_BLOCK.
If no filter has been set on the connection, a request for filtered blocks is ignored. If a filter has been set, a merkleblock message is returned for the requested block hash.
In addition, because a merkleblock message contains only a list of transaction hashes, transactions matching the filter should also be sent in separate tx messages after the merkleblock is sent.
This avoids a slow roundtrip that would otherwise be required (receive hashes, didn’t see some of these transactions yet, ask for them).
Note that because there is currently no way to request transactions which are already in a block from a node (aside from requesting the full block), the set of matching transactions that the requesting node hasn’t either received or announced with an inv must be sent and any additional transactions which match the filter may also be sent.
This allows for clients (such as the reference client) to limit the number of invs it must remember a given node to have announced while still providing nodes with, at a minimum, all the transactions it needs.

### Filter matching algorithm

The filter can be tested against arbitrary pieces of data, to see if that data was inserted by the client.
Therefore the question arises of what pieces of data should be inserted/tested.

To determine if a transaction matches the filter, the following algorithm is used.
Once a match is found the algorithm aborts.

1. Test the hash of the transaction itself.
2. For each output, test each data element of the output script.
This means each hash and key in the output script is tested independently.
Important: if an output matches whilst testing a transaction, the node might need to update the filter by inserting the serialized COutPoint structure.
See below for more details.
3. For each input, test the serialized COutPoint structure.
4. For each input, test each data element of the input script
(note: input scripts only ever contain data elements).
5. Otherwise there is no match.

In this way addresses, keys and script hashes (for P2SH outputs) can all be added to the filter.
You can also match against classes of transactions that are marked with well known data elements in either inputs or outputs, for example, to implement various forms of Smart property.

The test for outpoints is there to ensure you can find transactions spending outputs in your wallet, even though you don’t know anything about their form.
As you can see, once set on a connection the filter is not static and can change throughout the connections lifetime.
This is done to avoid the following race condition:

1. A client sets a filter matching a key in their wallet.
The part of the chain that the client is missing is requested using getblocks.
2. The first block is read from disk by the serving peer.
It contains TX 1 which sends money to the clients key.
It matches the filter and is thus sent to the client.
3. The second block is read from disk by the serving peer.
It contains TX 2 which spends TX 1.
However TX 2 does not contain any of the clients keys and is thus not sent.
The client does not know the money they received was already spent.

By updating the bloom filter atomically in step 2 with the discovered outpoint, the filter will match against TX 2 in step 3 and the client will learn about all relevant transactions, despite that there is no pause between the node processing the first and second blocks.

The nFlags field of the filter controls the nodes precise update behaviour and is a bit field.

• BLOOM_UPDATE_NONE (0) means the filter is not adjusted when a match is found.
• BLOOM_UPDATE_ALL (1) means if the filter matches any data element in a scriptPubKey the outpoint is serialized and inserted into the filter.
• BLOOM_UPDATE_P2PUBKEY_ONLY (2) means the outpoint is inserted into the filter only if a data element in the scriptPubKey is matched, and that script is of the standard “pay to pubkey” or “pay to multisig” forms.

These distinctions are useful to avoid too-rapid degradation of the filter due to an increasing false positive rate.
We can observe that a wallet which expects to receive only payments of the standard pay-to-address form doesn’t need automatic filter updates because any transaction that spends one of its own outputs has a predictable data element in the input (the pubkey that hashes to the address).
If a wallet might receive pay-to-address outputs and also pay-to-pubkey or pay-to-multisig outputs then BLOOM_UPDATE_P2PUBKEY_ONLY is appropriate, as it avoids unnecessary expansions of the filter for the most common types of output but still ensures correct behaviour with payments that explicitly specify keys.

Obviously, nFlags == 1 or nFlags == 2 mean that the filter will get dirtier as more of the chain is scanned.
Clients should monitor the observed false positive rate and periodically refresh the filter with a clean one.

### Partial Merkle branch format

A ‘‘Merkle tree’’ is a way of arranging a set of items as leaf nodes of tree in which the interior nodes are hashes of the concatenations of their child hashes.
The root node is called the ‘‘Merkle root’’.
Every Bitcoin block contains a Merkle root of the tree formed from the blocks transactions.
By providing some elements of the trees interior nodes (called a ‘‘Merkle branch’’) a proof is formed that the given transaction was indeed in the block when it was being mined, but the size of the proof is much smaller than the size of the original block.

#### Constructing a partial merkle tree object

• Traverse the merkle tree from the root down, and for each encountered node:
• Check whether this node corresponds to a leaf node (transaction) that is to be included OR any parent thereof:
• If so, append a ‘1’ bit to the flag bits
• Otherwise, append a ‘0’ bit.
• Check whether this node is a internal node (non-leaf) AND is the parent of an included leaf node:
• If so:
• Descend into its left child node, and process the subtree beneath it entirely (depth-first).
• If this node has a right child node too, descend into it as well.
• Otherwise: append this node’s hash to the hash list.

#### Parsing a partial merkle tree object

As the partial block message contains the number of transactions in the entire block, the shape of the merkle tree is known before hand.
Again, traverse this tree, computing traversed node’s hashes along the way:

• Read a bit from the flag bit list:
• If it is ‘0’:
• Read a hash from the hashes list, and return it as this node’s hash.
• If it is ‘1’ and this is a leaf node:
• Read a hash from the hashes list, store it as a matched txid, and return it as this node’s hash.
• If it is ‘1’ and this is an internal node:
• Descend into its left child tree, and store its computed hash as L.
• If this node has a right child as well:
• Descend into its right child, and store its computed hash as R.
• If L == R, the partial merkle tree object is invalid.
• Return Hash(L || R).
• If this node has no right child, return Hash(L || L).

The partial merkle tree object is only valid if:

• All hashes in the hash list were consumed and no more.
• All bits in the flag bits list were consumed (except padding to make it into a full byte), and no more.
• The hash computed for the root node matches the block header’s merkle root.
• The block header is valid, and matches its claimed proof of work.
• In two-child nodes, the hash of the left and right branches was never equal.

### Bloom filter format

A Bloom filter is a bit-field in which bits are set based on feeding the data element to a set of different hash functions.
The number of hash functions used is a parameter of the filter.
In Bitcoin we use version 3 of the 32-bit Murmur hash function.
To get N “different” hash functions we simply initialize the Murmur algorithm with the following formula:

nHashNum * 0xFBA4C795 + nTweak

i.e. if the filter is initialized with 4 hash functions and a tweak of 0x00000005, when the second function (index 1) is needed h1 would be equal to 4221880218.

When loading a filter with the filterload command, there are two parameters that can be chosen.
One is the size of the filter in bytes.
The other is the number of hash functions to use.
To select the parameters you can use the following formulas:

Let N be the number of elements you wish to insert into the set and P be the probability of a false positive, where 1.0 is “match everything” and zero is unachievable.

The size S of the filter in bytes is given by (-1 / pow(log(2), 2) * N * log§) / 8.
Of course you must ensure it does not go over the maximum size (36,000: selected as it represents a filter of 20,000 items with false positive rate of < 0.1% or 10,000 items and a false positive rate of < 0.0001%).

The number of hash functions required is given by S * 8 / N * log(2).

This document is placed in the public domain.


text:
# Math Help - How to determine coefficient in irreducible polynomial? HELP!!

1. ## How to determine coefficient in irreducible polynomial? HELP!!

Here is my problem:

Say if I have a irreducible polynomial for $GF(2^2)$ that is $x^2 + Nx + 1$, (N = elements of $GF(2)$) how do I determine the possible values of N ? Given the irreducible polynomial for $GF(2)$ is $x^2 + x + 1$

thanks alot!

2. Originally Posted by classic_phohe
Here is my problem:

Say if I have a irreducible polynomial for $GF(2^2)$ that is $x^2 + Nx + 1$, (N = elements of $GF(2)$) how do I determine the possible values of N ? Given the irreducible polynomial for $GF(2)$ is $x^2 + x + 1$

thanks alot!
Here is a field of order 4, $F=\mathbb{Z}_2[t]/(t^2+t+1)$. Therefore, $F = \{ 0,1,\alpha,\alpha+1\}$ where $\alpha = t + (t^2+t+1)$ and $\alpha^2 = \alpha + 1$.

For $x^2 + Nx+1$ to be irreducible it means it cannot have any zeros in $F$. The possible polynomials are: $x^2+1,x^2+x+1,x^2+\alpha x+1, x^2+(\alpha+1)x+1$. Which of these polynomials has zeros in $F$? The ones that do not are the irreducible ones.

3. Originally Posted by ThePerfectHacker
Here is a field of order 4, $F=\mathbb{Z}_2[t]/(t^2+t+1)$. Therefore, $F = \{ 0,1,\alpha,\alpha+1\}$ where $\alpha = t + (t^2+t+1)$ and $\alpha^2 = \alpha + 1$.

For $x^2 + Nx+1$ to be irreducible it means it cannot have any zeros in $F$. The possible polynomials are: $x^2+1,x^2+x+1,x^2+\alpha x+1, x^2+(\alpha+1)x+1$. Which of these polynomials has zeros in $F$? The ones that do not are the irreducible ones.

can I conclude that N can only either be 1 or 3 which is $\alpha$ and $\alpha +1$?

but I realize if I would like to derive elements of field 16 using that irreducible polynomial $x^2+\alpha x+1, x^2+(\alpha+1)x+1$, it cant be done.

unless I use $x^2+\alpha x+\alpha, x^2+(\alpha+1)x+(\alpha+1)$ then only I can produce 16 elements from the polynomials.

can you guide/advise me with this?

4. Originally Posted by classic_phohe
can I conclude that N can only either be 1 or 3 which is $\alpha$ and $\alpha +1$?

but I realize if I would like to derive elements of field 16 using that irreducible polynomial $x^2+\alpha x+1, x^2+(\alpha+1)x+1$, it cant be done.

unless I use $x^2+\alpha x+\alpha, x^2+(\alpha+1)x+(\alpha+1)$ then only I can produce 16 elements from the polynomials.

can you guide/advise me with this?
The polynomial $x^2+1$, it has a zero $x=1$.
The polynomial $x^2+x+1$, it has a zero $x=\alpha$.
The polynomial $x^2 + \alpha x + 1$, it has no zero - so irreducible.
The polynomial $x^2+(\alpha+1)x+1$, it has no zero - so irreducible.

Therefore, $F[x]/(x^2+\alpha x + 1)\text{ and }F[x]/(x^2+(\alpha+1)x+1)$ give rise to finite fields of 16 elements.

5. Ok! I agree what you explained. Now let sat I choose $x^2 + \alpha x + 1$ to be the irreducible polynomial, hence I use this to produce the elements in field of 16:

$x^0 = 1$
$x^1 = x$
$x^2 = \alpha x+ 1$
$x^3 = \alpha x + \alpha$
$x^4 = x + \alpha$
$x^5 = 1$

From there Im stuck. Can you give some tips how should I proceed with this? or I have already done wrongly at the first place?!

6. Originally Posted by classic_phohe
Ok! I agree what you explained. Now let sat I choose $x^2 + \alpha x + 1$ to be the irreducible polynomial, hence I use this to produce the elements in field of 16:

$x^0 = 1$
$x^1 = x$
$x^2 = \alpha x+ 1$
$x^3 = \alpha x + \alpha$
$x^4 = x + \alpha$
$x^5 = 1$

From there Im stuck. Can you give some tips how should I proceed with this? or I have already done wrongly at the first place?!
Any element in $F[x]/(x^2+\alpha x + 1)$ is $A+Bx + (x^2+\alpha x + 1)$. Let $\beta = x + (x^2+\alpha x + 1)$. Then $\text{GF}(2^4)$ would be $A + B\beta$ where $A,B\in \{0,1,\alpha,\alpha+1\}$ and $\beta$ has the property that $\beta^2 = \alpha \beta + 1$ (since it solves $x^2+\alpha x + 1$).

7. Originally Posted by ThePerfectHacker
Any element in $F[x]/(x^2+\alpha x + 1)$ is $A+Bx + (x^2+\alpha x + 1)$. Let $\beta = x + (x^2+\alpha x + 1)$. Then $\text{GF}(2^4)$ would be $A + B\beta$ where $A,B\in \{0,1,\alpha,\alpha+1\}$ and $\beta$ has the property that $\beta^2 = \alpha \beta + 1$ (since it solves $x^2+\alpha x + 1$).
thanks for the reply, but honestly I dont quite get it. Can you please explain further?

$A+Bx + (x^2+\alpha x + 1)$, with $\beta = x + (x^2+\alpha x + 1)$ how to become $A + B\beta$? wont this make the element become $A + Bx + B(x^2+\alpha x + 1)$ ?

8. Originally Posted by classic_phohe
thanks for the reply, but honestly I dont quite get it. Can you please explain further?

$A+Bx + (x^2+\alpha x + 1)$, with $\beta = x + (x^2+\alpha x + 1)$ how to become $A + B\beta$? wont this make the element become $A + Bx + B(x^2+\alpha x + 1)$ ?
The field with 16 elements is the set $\{ [A+Bx]:A,B\in \mathbb{F}_4 \}$ where $[ A + Bx]$ is the equivalent class modulo $x^2+\alpha x+1$. Notice that $[A+Bx] = A[1] + B[x]$ where $[1]$ is the equivalence class of $1$ modulo $x^2+\alpha x +1$ and $[x]$ is the equivalence class of $x$ modulo $x^2+\alpha x + 1$. Thus, what I am saying is that let $\beta = [x]$ then every element has form $A + B\beta$ (here we thinking of $A$ as an entire equivalence class).

9. Originally Posted by ThePerfectHacker
The field with 16 elements is the set $\{ [A+Bx]:A,B\in \mathbb{F}_4 \}$ where $[ A + Bx]$ is the equivalent class modulo $x^2+\alpha x+1$. Notice that $[A+Bx] = A[1] + B[x]$ where $[1]$ is the equivalence class of $1$ modulo $x^2+\alpha x +1$ and $[x]$ is the equivalence class of $x$ modulo $x^2+\alpha x + 1$. Thus, what I am saying is that let $\beta = [x]$ then every element has form $A + B\beta$ (here we thinking of $A$ as an entire equivalence class).
thank you very much!!!

so field with 16 elements is the set $\{ [A+Bx]:A,B\in \mathbb{F}_4 \}$so I will have 16 combination of A and B and hence produce 16 elements of field 16 with modulo the irreducible polynomial ; $\beta^2 = \alpha \beta + 1$ as $\beta = [x]$.

let say I proceed to field 256, I have the irreducible polynomial as $x^2 + x + \nu$ and I just use the same method you mentioned earlier reply to determine the possible value of $\nu$ ?

then I shall have the elements define as $\{ [A+Bx]:A,B\in \mathbb{F}_{16} \}$ ?

10. I believe the one you explain to me are all in polynomial basis. What if I would like to use Normal basis? Can you brief me how can it be done??

And also, the 16 elements produced by $x^2 + \alpha x + 1$ are in polynomial forms, each of them represent number from 0 to 15 right? let say i would like to identify number 2 and 14, is there any direct way to find which element representations are they in?


text:
# Random processes in time and frequency – attempt for an infograpic

Some time ago, I got fascinated by a few infographics from absorptions. The dial-up modem poster deserves special attention!

I have been looking at some topics on noise recently and decided to attempt assembling my first intentional infographic. Here it is:

Random Processes in Time and Frequency

The background is a 24 hour full spectrum scan (waterfall chart, 6 MHz – 2.2 GHz) which I captured with my SDR dongle last summer up in the Balkan mountains. Here you can find another version.

It ended up being a bit messy and probably not very useful, neither for novices, nor for professionals in the field. Nevertheless, I have accumulated ideas for another infographic which should be very entertaining. Stay tuned for a follow-up post.

# Chiseling out The Chip!

This post may be a bit redundant with the info I added in the other place, but I am excited, so I felt the need to rewrite some of it here.

Le Chip! This work took a while. To celebrate, I thought it deserves a few words in the blogs. During the past year or so, I was/have-been/will-continue-to-be working on an image sensor ADC testchip. It was finally taped out yesterday! What’s left now is some additional gastronomical work on the tapeout cake and the drainage of a rusty bottle of champagne.

The chip in all its ugly majesty with all these redundant power pads and LVDS pairs.

The core of the testchip is a fast 12-bit column-parallel ramp ADC at 5u pitch, utilizing some special counting schemes to achieve the desired 1us ramp time at slow clock rates. Alongside, to be able to fully verify the pipelined CDS functionality and crosstalk, I’ve built a pixel array in line-scan configuration, some fast LVDS drivers, clock receivers, references, state machines, a few 8-bit iDACs, bond pads, ESD, and some other array-related stuff, all from scratch! The chip has a horizontal resolution of 1024 and 128 lines with RGBW color filters and microlenses.

On the top-left corner there are some experimental silicon photomultipliers and SPAD diodes. These I plan to measure for fun and I promise to post the results in any of the two blogs.

Unfortunately, this chip wouldn’t yield tons of publicaiton work, apart from the core ADC architecture and comparator. To test the ADC one needs a whole bunch of other fast readout blocks, which in the end are not something novel, but yet, one needs them and designing these takes time. Finishing up this test system was a lot of work and I realize that it might be a bit risky and ambitious to be doing this as part of a doctorate. What if it fails to work because a state machine had an inverted signal somewhere? Or the home-made ESD and pads suffer from latch-up? Or the LVDS driver CMFB is unstable and I cannot readout data out? Or there is a current spike erasing the content of the SRAM? Or, or, or ?

We university people don’t have the corporate power to tapeout metal fixes twice a month until we’re there. I probably have another two or three chip runs for my whole doctorate. It may therefore be better (and more fun) to stick with small but esoteric modules, which one can verify separately and have time to analyze in detail. But hey, I’ll quote a colleague here: “It is what it is, let’s think how we can improve things.”

Finally, I have added this little fella who I hope will be my lucky charm.

Mr Le Duck!

With his 15um of height, could he compete in the annual “smallest duck on the planet” contest? Cheers!

# Applied chaos theory

Today I am having fun with a very nerdy circuit – Chua’s circuit. An electronic circuit that exhibits chaotic behaviour. I had a hard time getting this circuit to oscillate, but finally, after some prayers, throwing beans and doing black magic here it is:

Chua’s circuit

Heheh, looks terrible, but works. Here are some cool pictures of the Lorenz attractor. I was not able to spread the two twirls further, as my LC tank (in fact gyrator-capacitor tank) would stop oscillating.

Lorenz attractor curves tiral 1

Lorenz attractor curves tiral 2

Lorenz attractor curves tiral 3

Lorenz attractor curves tiral 4

And in case you also want to see how it sounds like and what my setup was here’s a short video clip:

# Visible light communications

Not long ago I listened to a talk led by Dr Sujan Rajbhandari giving a brief overview of visible light communications and some in-depth details about one of the latest projects happening at the optical wireless communications group here.

Let me give you a brief outline of their system and some of the main challenges in visible light communication (from now on abbreviated as VLC). Let’s start by stating some of the challenges:

1. VLC can not be established through solid medium i.e. visible light is blocked by walls, obstacles etc…

2. P.1 may be considered as something positive as it allows us to implement a very secure communication link; light does not escape the room as opposed to an RF Wi-Fi signal for example. On the other hand, the former obstructs us from achieving high coverage too.

3. Visible light sources (bar some lasers) have a quite low bandwidth as compared to what is possible to achieve with an RF modulator. I.e. Dr. Rajbhandari noted that the highest bandwidth LED they used, which was by the way custom made, had a BW of ~50MHz (on top of my head, may be more?). 50MHz gives us a maximum theoretical link BW of 25MSPS at one pulse-amplitude level (on-off keying). Adding-up the receiver (photodiode) bandwidth limitations, communication medium, noise, etc… drops down the link bandwidth dramatically.

4. External light happens to be a severe noise contributor to the link. I.e. we want to be in a bright lit room and still use a VLC link, however the white? daylight shines the receiver (photodiode) too, we are thus getting a huge interference and practically a failure to establish a link

5. What if my lamp (transmitter) does not shine my receiver directly, but via a reflection? More SNR losses and an increase of the bit error rate (BER).

From the few points above it becomes obvious that inventing a good VLC system is not an easy task. Even so, the group here reported connection speeds of 3Mbps at a distance of one meter, which currently appears to be a world speed record in VLC systems.

I would like to share some pictures of their excellent work (huge thanks to the group for letting me have a look at their device and for organizing the interesting weekly seminars in optical communications).

The visible light communication link setup.

VLC Transmitter – Left; VLC Receiver – right; link distance – 1m

A close view of the transmitter and its colimating lens

TX driver with pulse-amplifde modulation controller

The RX side, lens and active photodiode sensor RX matrix.

Link demo, sinewave-driven LEDs and thresholded receiver output.

The group tried various channel transmission schemes, such as Multiple-Input Multiple-Output (MIMO) or Single-Input Single-Output (SISO) schemes. The beauty here is that the colimating lens allow us to use MIMO link setup, as to effectively increase the bandwidth of the system.

Such smart schemes would hopefully mature enough so that can be implemented in the real world. I.e. they even tried using 2, 4 or 8 pulse-amplitude-modulation levels for achieving an even higher bandwidth. Have a look at their publications if you have curiosities about their system.

# Signals, transistors and music

Hej hopp! Not long ago (well, technically last year) I was helping out a fellow in the lab next door with his RF LNA simulations. All of a sudden our afternoon turned into a discussion about various guitar distortion effect pedals and their circuit implementations. Today I want to show you one of the simplest possible active circuits for distorting a signal.

So what do we call distortion? Distortion is the deviation of an output signal waveform from some sort of reference signal. Said in such a way one might argue that an amplified signal is also a distortion of sorts, however when we speak about distortion we normally refer to the time-domain (wave shape bending) and not simply an amplitude scale-up.

In mathematics and engineering the sine wave is the simplest possible waveform in a sense that one can generate any other type of waveforms by adding-up multiple (infinite?) number of sine waves. In practice we can not add an infinite number of sine waves together and thus we are limited to what we can generate. Out of the scope of this topic, have a look at the Gibbs phenomenon if you want to escape the ideal world of mathematicians and are interested in practical waveform generation, yet somewhat involving maths again. In music, normally there aren’t such instruments that produce pure single sine wave tones (bar some tuning forks at e.g. 440 and 880Hz) but for the ease of explanation the rest of my writing would be using pure sine wave signals as a reference.

Back to circuits, here is the simplest possible electronic distorter circuit I can currently think of:

A half wave rectifier.

This circuit removes a part of the fundamental frequency (half wave pass-through) but introduces a more noticeable proportional octave frequencies which might often be very desirable.

Moving into an active element solution, a d-effect of most electronic amplifiers can be utilized for achieving desirable distortion. The phenomenon is often called clipping. Here is an illustration:

Sine wave clipping

To give a better overview and not waste much time I decided to hook-up a simulink model and fetch some plots. However after some frustration with this amateur tool, I decided to go back to my dear good old friend Virtuoso and hook-up a common source amplifier at a 180nm process node. Here is the common source amplifier testbench I used for my examples.

An NMOS common source amplifier.

An input-output transfer function, input bias voltage DC sweep.

First I did a DC sweep to find the suitable operating point. Have a look at the amplifier’s transfer function (right), even though that we often assume that at a certain region it is linear, we can still see that it actually isn’t (green curve), not with this 180nm CMOS process at least. I have put a fairly high impedance load of 1MOhm as to increase the gain of this circuit which is approximately equal to $A_{0} = g_{m} \times R_{L}$. So, even if it is properly (in the mid output range) biased at ~550mV and applying a 1kHz sine wave with a reasonable swing so we don’t overdrive the amplifier one can still observe some minimal distortion. On the left side the input (red) ideal sine wave and output (green) amplified sine wave can be seen. To the right is an FFT spectrum plot of the amplified (green) sine wave. You can also see some FFT spectral leakage as I was too lazy to set-up a Fourier transform with coherent sampling.

A fairly low-distortion output sine wave.

However, what happens when we overdrive the amplifier? As we have a limited by the power supply output swing the output starts to saturate and thus we start to clip the sine wave. The higher the input drive swing the higher the clipping and distortion at the ouput. One can observe on the FFT that the fundamental tone power of 1KHz is now re-distributed at a number of octaves.

A higher overdrive.

Heavy distortion, note that the second octave is about 1/3 of the fundamental tone power:

Very high overdrive, a heavy distortion

Seeing all these pictures we can conclude that the various combinations of harmonics give us all these different (some pleasurable, others not so) sound effects. Various amplifier/distorter circuits sound different and it is up to the musician/designer’s taste. Back in the old days of modern music (e.g. Pink Floyd et.al.) musicians were to some extent circuit designers/experimenters, tuning-up the perfect circuit implementation which suits their needs. In the past 20 years direct digital synthesis and signal processing has offered a number of benefits to musicians, however the discrete tunability nature of these devices provides a number of limitations when it comes to distortion effects. I was aiming to find a way to play my sine waves (this is why I initially approached simulink, as it has an audio sink function) however it is a somewhat lengthier operation and I am leaving it to your imagination.

It is fascinating to see that such a simple electronic phenomenon has dramatically added-up to the variety of music available today. I offer you an example of a very slight distortion in combination with a German flute and some digital delay and harmonization. Only 50 years ago one couldn’t even imagine such sounds. Hmm, what would music sound like by the time I reach retirement age?

# Psychoacoustics and the auditory masking phenomenon

Happy New Year dear fellow geeks!

Many new year celebrations around the world involve at some point listening to the national anthem, or any other background music. During new year’s eve I had an intriguing discussion with friends on music, and data compression. I have decided to take the handle and transfer a part of our discussion into this post.

We are constantly surrounded by sounds and it is our brain’s task to distinguish between various tones, take the important for us and filter out what we (it) decides to be useless. The first part of this post aims to give a brief overview the psychoacoustic phenomenon named “auditory masking”, while the second elaborates on the perceptual coding schemes used for lossy music data compression. In the next few lines you will not see any formulas or complicated modelling, since I want to focus on the principle and draw some conclusions.

We all know that the human ear can normally hear sounds with frequencies from 20 Hz up to around 20 kHz and the latter limit can vary with age. To illustrate a bit, here is how a “bode” plot of the human ear looks like:

An equal loudness human ear sensitivity plot.

The perceived frequency resolution can vary within the hearable range, however its finest region appears to be within 1-4 kHz, which also matches the pitch of most human speech. This property together with the “masking” phenomenon would help us understand what the human ear can not perceive and therefore can be excluded from the music information we store.

So what is auditory masking? Imagine being on a bus station, talking to a friend while suddenly a noisy bus arrives at the bus stop. You are then no longer able to hear your friend, but you can clearly see his lips moving and he is in fact producing audible speech. His speech has been masked by the noise from the bus engine. Here is an example, narrowed down to two / a few tones:

Auditory masking phenomenon example.

Beyond a certain amplitude (marked as mask threshold) we can no longer perceive the weaker tone of interest. This is known as the auditory masking phenomenon:

Auditory masking phenomenon, a more general case.

It is observed that depending on the frequency of the masker tones and tone of interest, the mask threshold varies and the further away the masker tones are from the main tone, the higher the mask threshold is.

Knowing this phenomenon associated with the human ear, back in 1995 Fraunhofer Institute for Integrated Circuits in Erlangen came-up with a clever idea known as perceptual coding. Perceptual coding is a lossy audio encoding scheme reducing quantization steps for sounds which are inaudible and contained in the music/sound data. The nowadays popular mp3 encoding scheme utilizes perceptual coding and the masking phenomenon for lossy audio compression.

Because I like drawing, here is a simple block diagram of the perceptual coding scheme:

A principle diagram of the perceptual coding scheme.

The core of the encoder is the perceptual human ear model, based on the latter, a number of bandpass filter banks are tuned (depending on the ear’s critical bandwidth at various frequencies). We need these to be able to on a later step reduce specific information (bands) detail. The used frequency tone spacing (filters) determines the masking threshold.
The perceptual model steers a variable quantization and sampling rate control block. In practice, the quantization steps of an inaudible tone falling into the corresponding filter bank (band-pass filter) would be greatly reduced. Digital arithmetic number rounding or truncation is normally used for information reduction, however a variable sampling rate control can also be sometimes utilized. After information reduction, some additional noiseless encoding (e.g. look at huffman coding) is performed, before the final bit-stream packing.

Ideally, if the perceptual human ear model has infinite precision, such coding schemes should appear perfect/lossless. Unfortunately this is not the case in reality, but hey, nevertheless, mp3 has changed the world. Isn’t this an incredibly elegant invention of the 20th century? Here is my example for an application of this clever lossy compression scheme 🙂

# Dithering and is no noise a good noise? – Part one.

The technique which I will try to briefly describe in this post is often referred to as dithering. The term according to Wikipedia comes from the old English word “didder”, meaning to shiver, shake.

During continuous to discrete-time signal conversion a so called quantizer component is used. Quantization in signal processing is a process of converting the information from a fine continuous-time (analog) signal to one represented in finite amplitude steps by sampling. It is important to mention that time sampling (ideally w/o quantization) does not generate noise and if one ensures that the sampling frequency exceeds the Nyquist rate, then a smooth signal is again obtained and no information is lost. In reality however in a sampled system we can not save each sample with its exact value, but instead we often need to quantize (digitize) it and store it with a limited number representation (bits). Having a limited set of numbers means that in reality there would be a discrepancy between the real analog signal and the quantized (digitized) one. Here is a quick sketch showing what I actually mean:

An analog signal and its quantization

The analog signal is quantized in a finite set of steps and the error between the real sampled and the converted (quantized) values is shown in the hatched area. Now, it has been shown that with the help of oversampling techniques one can statistically increase the resolution of a quantizer by generally speaking accumulation and averaging.

My post aims to show how the effect of oversampling and therefore Signal to Noise (SNR) ratio can be increased by injecting even more noise into the system. At first glance one might say – no way! However, that’s not always the case. If the quantizer is coarse (so that no circuit thermal noise would influence it much) and if the injected noise (dither) has the right magnitude we can gain a lot. Let’s have a look at a simple and intuitive example. Here is an overview of our system consisting of a signal source $x$ random uniform noise source $d$ and a quantizer (2-bit) to ease-up our drawings later-on.

Analog additive dither and a quantizer

Let’s apply a sinewave $x$ as our input signal and skip adding a dither signal $d$ , then the input and output of the quantizer would look like this:

An ideal quantized sinewave

Now if we inject random uniform (a key role, to be discussed in Part 2 of this post) noise $d$ with an amplitude of one least-significant bit (LSB) we can observe the following picture:

A quantized sinewave with additive dither

It comes to ones intuition that if we try to average the samples we might actually have done a higher resolution quantization. Think low-pass filtering. However to give a very clear illustration I’ll introduce a numerical example. Consider a DC signal of 2.5 Volts and an ideal quantizer of 2 bits:

An example of DC signal oversampling with and without dither injection.

We can see that without any dither the average conversion value is still 3, while by adding dither we randomize the error and after averaging we have gained additional resolution. Obviously my 2.5V example is a bit too idealistic and there is an awful lot more to this, but I just wanted to make my trial at introducing this concept here. Some other day I will write some about analog additive and digital subtractive dither, as well as its impact on images.


text:
# Math Help - Transformations of Exponential Functions -

1. ## Transformations of Exponential Functions -

Problem:

2=4^x-1

So For this transformation I thought you would complete a horizontal shift right one unit by adding 1 to all x-values and then a vertical shift up 2 units by adding 2 to the y-values -
our begining points are (0,1) (1,4) and (-1, 1/4) Im getting stuck transforming those points and my answers arent at all what they should be.... am I missing something?

thanks!

2. Originally Posted by woeckbr
Problem:

2=4^x-1

So For this transformation I thought you would complete a horizontal shift right one unit by adding 1 to all x-values and then a vertical shift up 2 units by adding 2 to the y-values -
our begining points are (0,1) (1,4) and (-1, 1/4) Im getting stuck transforming those points and my answers arent at all what they should be.... am I missing something?

thanks!
Do you mean $y = 4^{x-1} - 2
$

If so from the graph of $4^x$ shift it 1 unit to the right and then move it 2 units down.

Therefore the asymptote at $y=0$ is now at $y=-2$

edit: see graph attached

3. Originally Posted by woeckbr
Problem:

2=4^x-1

So For this transformation I thought you would complete a horizontal shift right one unit by adding 1 to all x-values and then a vertical shift up 2 units by adding 2 to the y-values -
our begining points are (0,1) (1,4) and (-1, 1/4) Im getting stuck transforming those points and my answers arent at all what they should be.... am I missing something?

thanks!
your transformation should be negative 2 shift down

$2=4^{x-1}$

$0 = 4^{x-1} -2$


text:
# Wydawnictwa / Banach Center Publications / Wszystkie tomy

## Almost periodic and strongly stable semigroups of operators

### Tom 38 / 1997

Banach Center Publications 38 (1997), 401-426 DOI: 10.4064/-38-1-401-426

#### Streszczenie

This paper is chiefly a survey of results obtained in recent years on the asymptotic behaviour of semigroups of bounded linear operators on a Banach space. From our general point of view, discrete families of operators ${T^{n}: n = 0,1,... }$ on a Banach space X (discrete one-parameter semigroups), one-parameter $C_0$-semigroups ${T(t): t ≥ 0}$ on X (strongly continuous one-parameter semigroups), are particular cases of representations of topological abelian semigroups. Namely, given a topological abelian semigroup S, a family of bounded linear operators {T(s): s ∈ S} is called a representation of S in B(X) if: (i) T(s+t) = T(s)T(t); (ii) For every x ∈ X, s ↦ T(s)x is a continuous mapping from S to X. The central result which will be discussed in this article is a spectral criterion for almost periodicity of semigroups, obtained by Lyubich and the author [40] for uniformly continuous representations of arbitrary topological abelian semigroups (thus including the case of single bounded operators and several commuting bounded operators), and for $C_0$-semigroups [41], and by Batty and the author [9] for arbitrary strongly continuous representations of suitable locally compact abelian semigroups. An immediate consequence of this result is a Stability Theorem, obtained, for single operators and $C_0$-semigroups, also by Arendt and Batty [1] independently. The proof in [1] uses a Tauberian theorem for the Laplace-Stieltjes transforms and transfinite induction. Methods of this type can also be used to prove the almost periodicity result for $C_0$-semigroups [8], but seem not suitable for commuting semigroups, and will not be discussed in this article. We also refer the reader to a recent survey article of Batty [6], where some developments are described which are not included here.

• Vũ Phóng

## Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Odśwież obrazek


text:
• # question_answer If the four sides of a quadrilateral ABCD are tangential to a circle, which of the following is true? A)  $\text{AC}+\text{AD}=\text{BD}+\text{CD}$ B)  $\text{AB}+\text{CD}=\text{BC}+\text{AD}$ C)  $\text{AB}+\text{CD}=\text{AC}+\text{BD}$ D)  $~\text{AC}+\text{AD}=\text{BC}+\text{AB}$

Given sides of a quadrilateral ABCD are tangential to a circle. $\therefore$ $\text{7}\times \text{13}+\text{13}$


text:
# How do you evaluate (- 159) \div ( + 53) ?

$- 3$ factor $- 159$ and divide out common factors with $+ 53$
$- 159 = - 1 \times 3 \times 53$
There is a common factor of $53$. Dividing out the common factor gives.
$- 1 \times 3 = - 3$


text:
• S Abraham John

Articles written in Journal of Chemical Sciences

• Electrochemical behaviour of Prussian Blue at Nation coated electrode

• Role of acidity on the electrochemistry of Prussian Blue at plain and Nation filmcoated electrodes

Prussian Blue (PB) coated on plain platinum (Pt) shows a redox wave at 0.44V vs SCE in addition to the two usual redox waves at 0.82 and 0.12 V vs SCE when the electrodes were dipped in acidic KC1 solution. PB incorporated into Nation film-coated on Pt electrode exhibited the same behaviour even in the presence of neutral KG solution. In acidic KC1, the additional redox wave observed for PB incorporated into Nation film shifted positively to 0.39V vs SCE and the peak separation was reduced to 30mV. The observed additional redox wave for PB coated on plain Pt electrode and incorporated into Nafion film-coated Pt electrodes was assigned to the partial reduction of PB occurring due to the insertion of protons into the film. The effect of various cations on the electrochemistry of PB incorporated into Nafion film-coated electrode was also studied.

• Selective determination of 3,4-dihydroxyphenylacetic acid in the presence of ascorbic and uric acids using polymer film modified electrode

We report here the highly sensitive and selective electrochemical determination of 3,4-dihydroxyphenylacetic acid (DOPAC), one of the dopamine metabolites in the presence of important interferents ascorbic acid (AA) and uric acid (UA) using an ultrathin electropolymerized film of 5-amino-1,3,4-thiadiazole-2-thiol (p-ATT) modified glassy carbon (GC) electrode in 0.20M phosphate buffer solution (pH 5.0). The bare GC electrode fails to resolve the oxidation peaks of AA, DOPAC and UA in a mixture. Further, the oxidation peak potentials of them were shifted to more positive potential with decreased peak currents in the subsequent cycles. On the other hand, the p-ATT modified electrode not only separated the voltammetric signals of AA, DOPAC and UA but also enhanced their peak currents. The amperometric current response was increased linearly with increasing DOPAC concentration in the range of $4.0 \times 10^{−8}$ to $1.0 \times 10^{−5}$ M and the detection limit was found to be 150pM ($S/N =3$).

• Fabrication of optochemical and electrochemical sensors using thin films of porphyrin and phthalocyanine derivatives

This paper describes the fabrication of thin films of porphyrin and metallophthalocyanine derivatives on different substrates for the optochemical detection of HCl gas and electrochemical determination of L-cysteine (CySH). Solid state gas sensor for HCl gas was fabricated by coating meso-substituted porphyrin derivatives on glass slide and examined optochemical sensing of HCl gas. The concentration of gaseous HCl was monitored from the changes in the absorbance of Soret band. Among the different porphyrin derivatives, meso-tetramesitylporphyrin (MTMP) coated film showed excellent sensitivity towards HCl and achieved a detection limit of 0.03 ppm HCl. Further, we have studied the self-assembly of 1,8,15,22-tetraaminometallophthalocyanine (4𝛼-MTAPc; M = Co and Ni) from DMF on GC electrode. The CVs for the self-assembled monolayers (SAMs) of 4𝛼-CoIITAPc and 4𝛼4-NiIITAPc show two pairs of well-defined redox couple corresponding to metal and ring. Using the 4𝛼-CoIITAPc SAM modified electrode, sensitive and selective detection of L-cysteine was demonstrated. Further, the SAM modified electrode also successfully separates the oxidation potentials of AA and CySH with a peak separation of 320mV.

• # Journal of Chemical Sciences

Volume 132, 2020
All articles
Continuous Article Publishing mode

• # Editorial Note on Continuous Article Publication

Posted on July 25, 2019


text:
Home » Six Sigma » PMP Mock Test-3

Subscribe

# PMP Mock Test-3

Welcome to your PMP Mock Test-3

Maslow ranked Human needs from the highest to lowest:
Hint

Pareto Analysis, cause and effect diagrams and flow charts are used in quality.
Hint

Which of the following is the most efficient means of product quality inspection:
Hint

Using the PMBOK definition of contingency reserve, which of the following statements about contingency reserves is false?
Hint

The two closing procedures are called:
Hint

During the develop schedule process, the Project Manager may have to go through several iterations of the schedule before establishing the schedule baseline. All of the following are tools and techniques that may be used during this process:
Hint

All of the following are communication methods EXCEPT:
Hint

The sending or conveying of information from one place to another is the process of:
Hint

A complex project will fit best in what type of organization?
Hint

The "rule of seven" as applied to process control charts means that :
Hint

A tool which links the project roles and responsibilities to the project scope definition is called:
Hint

Who should be involved in the project planning phase?
Hint

A contingency plan is:
Hint

System integration consists of:
Hint

In a multi-cultural environment, it is critical to establish a corporate culture that facilitates:
Hint

The critical element in a project's communication system is the:
Which of the following is NOT an example of a type of schedule report?
Which of the following models of conflict resolution allows a cooling off period, but seldom resolves the issue in the long term?
Hint

A narrative account of products, services or results to be achieved under a project comes in the form of
Hint

Examples of Projects include:
A type of organization in which the project manager has little formal authority and basically acts as a staff assistant to an executive who is ultimately responsible for the project is called:
Hint

There is project with CPI of 0.81 and TCPI=1.00001 this project is:
Hint

A cost-plus-incentive-fee (CPIF) contract has an estimated cost of $120,000 with an agreed profit of 10% of the costs. The actual cost of the project is$130,000. What is the total reimbursement to the seller?
Hint

Create WBS process belongs to:
Hint

A document or tool which describes when and how human resources will be brought onto and taken off the project team is called a:
Hint

In general a project charter covers:
Hint

In case of an external IT project, the project initiator or sponsor must have provided the following information excluding.
What are the best uses of PERT:
Hint

Which of the following is considered during the Procurement Planning Process?
From a buyer's standpoint, which of the following is true?
Hint

Performance reviews are held to:
Hint

Which of the following is correct order for stages in Tuckman ladder?
Hint

___________ must be measured regularly to identify variances from the plan.
Which of the following activities do not fall under the Closing Process Group?
Hint

Parametric estimating is a technique where
Hint

Projects are initiated in response of:
Hint

A project kick off meeting is usually conducted to:
Hint

Project scope is:
Hint

Deflection or transfer of a risk to another party is a type of?
Hint

Which of the following is true about a risk?
Projects are undertaken at all levels of the organization?
Hint

The party that needs the change resulting from the project, and who will be its custodian on completion is the:
Which of the following are examples of indirect costs?
Hint

Which of the following are outputs from the Plan Communications Management process?
Hint

Maninder, the project manager for a logistics project successfully undertook all the project activities and reached the final Close Project or Phase process that used the following inputs except for.
Cost Plus Incentive Fee (CPIF) contracts provide:
Hint

Project success depends on a number of interrelated factors, including time, cost and scope control. The success of any project depends primarily on:
Hint

Which of the following is a method for quantifying qualitative data in order to minimize the effect of personal prejudice on source selection?
Hint

In which of the following organizations is the project manager role likely to be that of staff assistant?
Hint

The delphi Method is best suited for:
Hint

You are responsible for ensuring that your seller's performance meets contractual requirements. For effective contract administration, you should:
Hint

Which of the following statements concerning contract type is correct?
Hint

Change requests can occur due to:
Hint

The unique identifiers assigned to each item of a WBS are often known collectively as:
Hint

A collection of generally sequential project phases whose name and number are determined by the control needs of the organization or organizations involved in the project, is called:
Hint

The sender of a message is responsible for:
Hint

A leadership style in which the project manager shares problems with team members and formulates solutions as a group is called:
Hint

In negotiations between the functional department managers and the project managers, which conflict management approach must be aimed at?
Hint

A complete set of concepts, terms and activities that make up a professional field, project management field or an area of specialization is known as:
Hint

Your project is in the final test stage, the user acceptance test. It meets all the product specs and is under planned costs. In term of schedule, this project is ahead. Your customer met you and requested that he will not accept the product unless you make several changes. What you should do is:
Hint

Three Point Statistical Estimating Formula Group. Expected Value =
Hint

In communication, the receiver decodes the messages based on all but the following:
Which of the following could be an appropriate WBS code for a work package at the fourth level in a WBS where the top level code is 1.0?
Which of the following is true about procurement documents?
Herzberg identified factors, which, if present, will lead to increased motivation. A typical factor would be:
Hint

Management reserves are used to handle which type of risk?
Hint

________ means that every project has a definite beginning and a definite end.
In which of the following contract types is the seller's profit limited?
Hint

The contemporary view of conflict is that:
Hint

You are in charge of developing a new product for an organization. Your quality metrics are based on the 80th percentile of each of the last three products developed. This is an example of:
Hint

Three major processes in Project Human Resource Management are:
Hint

In which type of organization is team building likely to be most difficult?
How much time does the typical project manager spend communicating both formally and informally?
Hint

According to PMBOK, project management processes are organized into following order of process groups:
Hint

Which of the following methods is least likely to be used for explaining project planning guidelines to the team?
Hint

What are the four parts of the communications model?
Hint

Which of the following is not an external-unpredictable risk?
Hint

Communication is the PRIME responsibility of a Project:
Hint

Which of the following contract types places the greatest risk on the seller?
Hint

A project is defined as:
Under what circumstances is it better for a contractor to subcontract?
Hint

What does TQM stand for?
Hint

Which of the following is not a General management technique?
A condition which will lead an organization towards conflict is:
Hint

The purpose of the review of deliverables and project performance at the conclusion of a project phase is to:
Hint

The review of key deliverables and project performance at the conclusion of a project phase is called:
Hint

The three major types of communication are:
Hint

The three major causes of change on a project are:
Hint

Group brainstorming encourages all of the following except:
Hint

The outputs of the Monitor and Control project work are utilized as inputs for the Performance of Integrated Change Control to give the following outputs, excluding.
Hint

Which of the following statement is correct?
Hint

A business case, which helps to determine whether a project is worth the investment, is created on the basis of the following except for
Project Risk Management includes all of the following processes except:
Hint

Who is not responsible for risk identification or reporting?
Hint

Which of the following demonstrates a good negotiation skill?
Hint

Your customer ask for a small change in the project, which was not budgeted in the project. It is a small effort as compared to the total project and you need the goodwill for a multimillion dollar on the pipeline. You will
Hint

A project management plan is:
Hint

The most important criteria in deciding to initiate a project selection method is:
Hint

Which of the following Project Scope Management processes involves subdividing the major project deliverables into smaller, more manageable components?
The successful project managers spend most of their time:
Hint

Be sure to click Submit Quiz to see your results!

This site uses Akismet to reduce spam. Learn how your comment data is processed.


text:
## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  734.11047
Autor:  Erdös, Paul; Pomerance, Carl; Schmutz, Eric
Title:  Carmichael's lambda function. (In English)
Source:  Acta Arith. 58, No.4, 363-385 (1991).
Review:  Let \lambda(.) be Carmichael's function, i.e. \lambda(n) equals the l.c.m of the orders of primitive residues mod n. Using a more explicit representation via Euler's function the authors investigate the average order, normal order, and minimal order of \lambda. For example they show that for x \geq 16

1/x sumn \leq x \lambda(n) = \frac{x}{log x}\exp {\frac{B log log x}{log log log x}(1+o(1))}

holds with some explicit constant B. Some other problems connected with Euler's function are discussed.
Reviewer:  T.Maxsein (Frankfurt / Main)
Classif.:  * 11N37 Asymptotic results on arithmetic functions
11A07 Congruences, etc.
11N45 Asymptotic results on counting functions for other structures
Keywords:  asymptotic formulas; universal exponent; Carmichael's function; orders of primitive residues; Euler's function; average order; normal order; minimal order

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag


text:
# Math Help - Geometry Question

1. ## Geometry Question

THe diagram opposite shows an equilateral triangle ABC whose sides are 2(x) units long.

a) show that the inscribed circle tangent to all three sides has area 1/3pi(x)^2

b) show that the circumscribed circle passing through all three vertices has four times the area of the inscribed circle

Thanks

2. The radius of the inscribed circle is $r=\frac{l\sqrt{3}}{6}$, where $l$ is the length of the side of the triangle.

The radius of the circumscribed circla is $R=\frac{l\sqrt{3}}{3}$, where $l$ is the length of the side of the triangle.

Then use the formula for the area of a circle: $A=\pi R^2$


text:
# What is the fastest algorithm to check if a number has only 3 divisors?

Which is the fastest way to check if a number has only 3 unique factors ? Any help will be highly appreciated?

-
check it's a square of another prime? – Patrick Li Oct 1 '12 at 16:12
@PatrickLi: another? – Marc van Leeuwen Oct 1 '12 at 16:41
@MarcvanLeeuwen check it's the square of a prime number. :) – Patrick Li Oct 1 '12 at 16:47

The fastest method will depend on the types of numbers you intend to check and how you are running the tests (pencil and paper, x86_64, etc.). But basically, check if the number has any small prime factors (say, the first 25: 2, 3, 5, ..., 97). If so, the number has exactly 3 divisors if and only if the number is the square of that prime. Otherwise you have a number with no tiny prime factors; now check if the number is a square. You can first test mod some promising moduli, like 63, 64, and 65. If it passes that test, take the integer square root $s$ and test if that, squared, gives the number. If not, the number has more than 3 divisors. If so, test if the remaining number is prime. The first step is using a probable-prime test, maybe checking if the number is a b-strong pseudoprime for some randomly-chosen $1 < b < s-1.$ If that fails the number is composite and so $s^2$ has more than three divisors. Otherwise apply a primality-proving test to $s$.
Supposing that by "only 3 divisors" you mean "exactly 3 divisors", the only such numbers are numbers of the form $p^2$, where $p$ is prime; they are divisible by $1, p,$ and $p^2$. So the first thing to try is to test if the number $n$ is a perfect square, which you can do efficiently by calculating the integer square root $i = \lfloor \sqrt n\rfloor$ and then checking to see if $i^2=n$. If not, $n$ fails. If so, $n$ has the desired property if and only if $i$ is prime, which you can check using any of the usual primality tests.