text:
## Introduction to quantum computing: Quantum gates.

Sources:

“Quantum computing for computer scientists”, N. Yanofsky and M. Mannucci, Cambridge Press, 2008.

This is part of a (probably) long list of posts regarding quantum computing. In this post, we will talk about the nuts and bolts of quantum computing: quantum gates. For the moment, we will just describe quantum gates in an abstract sense and not relate how these gates are connected to algorithms. But have in mind: even for classical computers, whatever algorithm we design, it needs to be translated to “hardware language”, that further is decomposed as a collection of classic gates.

Disclaimer I: while the material below might seem too simple for some scientists, I suggest not skimming over this post - personally, I always enjoy reading something that I believe I own, as επαναληψη μητηρ πασης μαθησεως (repetition is the mother of any knowledge)

### Classical bit

In the macroscopic world, we know that: $(i)$ electricity either passes or not through a circuit, $(ii)$ a proposition is true or false, etc. The above can be easily described through a bit: a bit represents an way to say that we are in a particular state among two states.

There are different ways to represent this information. In this post, we will use the following representation of a bit:

$| \text{state} \rangle = \begin{bmatrix} \text{state is 0} \\ \text{state is 1} \end{bmatrix}$

Observe that in our macroscopic world, the state cannot be in both situations. More rigorously, let us represent the state $0$ as:

$| \mathbf{0} \rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$

and the state $1$ as:

$| \mathbf{1} \rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$

We can see that these two representations are orthogonal: we cannot be in a situation where we are in a “bit of 0” and in a “bit of 1”.

### Quantum bit

As we will see shortly, a quantum bit is actually a generalization of the classical bit. Using the notation above, a quantum bit can be described as:

$\begin{bmatrix} c_0 \\ c_1 \end{bmatrix}$

where, as always, $|c_0|^2 + |c_1|^2 = 1$. Remember that while $|c_i|^2$ represents probability, when we measure the quantum bit, it “collapses” to a classical bit. We visualize this as:

Observe that, before measuring it, any qubit can be written as a linear combination of classical bits:

$\begin{bmatrix} c_0 \\ c_1 \end{bmatrix} = c_0 \cdot | \mathbf{0} \rangle + c_1 \cdot | \mathbf{1} \rangle$

Some examples are:

$\begin{bmatrix} \tfrac{1}{\sqrt{2}} \\ \tfrac{1}{\sqrt{2}} \end{bmatrix} = \frac{1}{\sqrt{2}} \cdot | \mathbf{0} \rangle + \frac{1}{\sqrt{2}} \cdot | \mathbf{1} \rangle = \frac{| \mathbf{0} \rangle + | \mathbf{1} \rangle}{\sqrt{2}}$

and

$\begin{bmatrix} \tfrac{1}{\sqrt{2}} \\ -\tfrac{1}{\sqrt{2}} \end{bmatrix} = \frac{1}{\sqrt{2}} \cdot | \mathbf{0} \rangle - \frac{1}{\sqrt{2}} \cdot | \mathbf{1} \rangle = \frac{| \mathbf{0} \rangle - | \mathbf{1} \rangle}{\sqrt{2}}$

How are qubits to be implemented? Think of electrons in different orbits, photons in one of two polarized states, particles in one of two spin directions.

What if we have many qubits? We define multi-particle qubits as:

$|\mathbf{0} \rangle \otimes | \mathbf{1} \rangle \otimes \cdots \otimes |\mathbf{1} \rangle$

Since each state is described by two complex numbers $c_i$, the total number numbers required to describe a $n$-qubit system is $\mathbb{C}^{2^n}$. There are different ways to denote multiparticle qubits; here, we will stick to $|\mathbf{0} \mathbf{1} \cdots \mathbf{1} \rangle$.

### Classical gates

We will not delve into the details of classical gates; we assume that the reader can have a look of definitions of classical gates here. What we will discuss is the ability to represent the action of a gate on a classical state as a matrix-vector multiplication over the binary field.

For example: consider the NOT gate. I.e., the input is a single classical bit; the output is its inverse. Using our notation, let us use as input $| \mathbf{0} \rangle$. Then, the NOT gate can be represented as:

$\underbrace{\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}}_{\text{NOT gate}} \cdot | \mathbf{0} \rangle = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} = | \mathbf{1} \rangle$

Similar logic applies for other gates such as AND, NOR, XOR, NAND. In all cases, we can represent the application of the gate on an input as a matrix-vector product. For the gates with input more than a single bit, we can represent the input as the vertical concatenation of bits. Finally, when we have more than one gate in sequence, we can represent the sequence of matrices as a sequence of matrix-matrix multiplications, before we apply the input. Also, gates in parallel can be represented as kronecker products of matrices.

As an example consider the following sequence of gates:

This can be described as OR(NOT, AND). Let us first compute the parallel set of gates NOT and AND.

$\text(NOT) \otimes \text{AND} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \otimes \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{bmatrix}$

Also, combining the gates in sequence:

$\text{OR(NOT, AND)} = \text{OR} \cdot (\text{NOT} \otimes \text{AND}) = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$

You can verify that this matrix actually corresponds to the gate OR(NOT, AND).

### Reversible classical (and quantum) gates

As we have seen so far, working in quantum systems provides also the notion of time that can move forward or backwards. I.e., we can apply unitary matrices that transform the current state, but also apply its inverse and go back to the initial state.

We can easily observe that not all classical gates can be applied in the quantum world, exactly due to this ineffiency to get back to the initial state. E.g., the AND gate with output 0 gives no information about which of the two input bits were 0 or whether both of them were 0.

In contast, there are classical gates that are reversible. E.g., the NOT gate. We can say that the NOT gate preserves the input information (=energy) while the AND gates fail to preserve the input information (=energy).

Note: an interesting topic to read is that of Landauer’s principle. We will skip this in this post.

Here, we will describe some gates that are both used in classical and quantum computing; purely quantum gates will be described later on.

A universal gate is a gate that can implement any Boolean function, without the need of any other gates. In classical computing, NAND and NOR are universal gates; fun fact is that AND and OR gates are constructed as NAND and NOR gates, followed but an inverter.

##### Controlled-NOT gate

The controlled-NOT gate takes two inputs and gives back two outputs. The schematic representation of it is as follows:

This gate operates as follows: the top input goes through the gate as it is, and we observe it at the output. However, the top signal controls the bottom signal: if the top signal is $|0\rangle$, then the input $|y\rangle$ will be output as it is; if the top signal is $|1\rangle$, then the gate reverses the bottom signal. We can see that the operation on the bottom signal is similar to an XOR gate, that’s why we use the symbol $\bigoplus$.

##### Toffoli gate

The Toffoli gate is similar to the controlled-NOT gate, but has three input signals, two of which “decide” about the output of the last input. Its schema is as follows:

Here, the bottom signal flips only if both the top two inputs are equal to $|1\rangle$. The Toffoli gate is a universal gate (it is interesting to show by yourself that Toffoli can generate both the AND and the OR gate, from which one implies that it can generate the NAND gate, which by itself is known to be an universal gate).

##### Fredkin gate

Another universal gate is the Fredkin gate. Similar to the Toffoli gate, this gate has three inputs and three outputs:

Only the top input operates as a controller: if it is $|0\rangle$, then the other two inputs output their values as they are; if it is $|1\rangle$, then the outputs of the two other signals are switched: we see $|y’\rangle = |z\rangle$ and $|z’\rangle = |y\rangle$. The Fredkin gate is also an universal gate.

### Quantum gates

What we have talked so far is about gates that apply abstractly on both classical bits and quantum qubits. Here, we will discuss about gates that have a meaning when applied only on qubits.

Three key gates-matrices, widely used in quantum computing, are the Pauli matrices:

$X \equiv \sigma_x = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, ~~ Y \equiv \sigma_y = \begin{bmatrix} 0 & -j \\ j & 0 \end{bmatrix}, ~~ Z \equiv \sigma_z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}.$

Each Pauli matrix is a hermitian matrix (we will see that all quantum gates are represented as hermitian and unitary, for energy preservation), and together with the identity matrix form a basis for the space of $2 \times 2$ Hermitian matrices.

Some other important quantum gates are:

• the S-gate: $S = \begin{bmatrix} 1 & 0 \ 0 & e^{j\pi/2} \end{bmatrix}$,
• the Hadamard gate: $H = \tfrac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \ 1 & -1 \end{bmatrix}$,
• the T-gate: $T = \begin{bmatrix} 1 & 0 \ 0 & e^{\pi/4} \end{bmatrix}$.

All the above gates can be easily extracted from the generator matrix $U_3(\theta, \phi, \lambda)$, where:

$U_3(\theta, \phi, \lambda) = \begin{bmatrix} \cos(\theta/2) & -e^{j\lambda} \sin(\theta/2) \\ e^{j\phi}\sin(\theta/2) & e^{j(\phi + \lambda)} cos(\theta/2) \end{bmatrix}$

Then, the Hadamard matrix is $H = U_3(\pi/2, 0, \pi)$, $S = U_3(0, 0, \pi/2)$, and $T = U_3(0, 0, \pi/4)$.

All the above operations are connected through the following properties:

• $X^2 = Y^2 = Z^2 = I$,
• $H = \tfrac{1}{\sqrt{2}} \left(X + Z\right)$,
• $X = HZH$,
• $Z = HXZ$,
• $S = T^2$.

Some other gates are the square root of NOT gate and the measurement gate, which is actually not reversible (and thus not unitary). The measurement gate is used usually at the end of quantum computations in order to obtain the answer from qubits (into bits).


text:
# Why is the salt used only once in PBKDF2, while the password is used often?

The purpose of PBKDF2 is to create a derived key (DK) from a master password (PW) and a salt, often using a function like HMAC-SHA256. I have read that the salt should be as random as possible. But if that's the case, why does it play such a minor role?

I'll let the equations speak for themselves, starting with HMAC-SHA256:

$$\def\op{\operatorname}\def\0#1#2#3{\text{0×#2#3}} \op{HMAC-SHA256}( PW, m ) = \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ m ) )$$ where \begin{align*} K &= \begin{cases} PW &\textrm{if } \op{bytes}( PW ) = 64 \newline \op{SHA256}( PW ) ∥ [\0x00]_{32} &\textrm{if } \op{bytes}( PW ) > 64 \quad \textrm{ (32 zero bytes)} \newline PW ∥ [\0x00]_{64-\op{bytes}(PW)} & \textrm{if } \op{bytes}( PW ) < 64 \end{cases} \newline K_i &= K ⊕ [\0x36]_{64} \newline K_o &= K ⊕ [\0x5c]_{64} \newline \end{align*}

Now PBKDF2:

\begin{align*} DK &= T_1 ∥ T_2 ∥ ... ∥ T_{\op{len}(DK)/\op{len}(T_i)} \newline T_i &= U_1^i ⊕ U_2^i ⊕ ... ⊕ U^i_{\text{iterations}} \newline U^i_1 &= \op{HMAC-SHA256}( PW, \op{salt} ∥ \op{INT32}( i ) ) \newline U^i_n &= \op{HMAC-SHA256}( PW, U^i_{n-1} ) \end{align*}

But watch what happens if the two are combined:

\begin{align*} U^i_1 &= \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{salt} ∥ \op{INT32}( i ) ) ) \newline U^i_2 &= \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{salt} ∥ \op{INT32}( i ) ) ) ) ) \newline & \dots \end{align*}

Or in pseudocode:

\begin{align*} &T[i] = 0 \newline &U = \op{salt} ∥ \op{INT32}(i) \newline &\text{for } n = 1 \text{ to }c: \newline &\qquad U = \op{SHA256}( K_i ∥ U ) \newline &\qquad U = \op{SHA256}( K_o ∥ U ) \newline &\qquad T[i] = T[i] ⊕ U \newline &\text{next }n \newline \end{align*}

So the salt is used only once per output block, while the master password is used twice per iteration (in the forms $K_o$ and $K_i$). I understand that the avalanche effect means a slight change in the initial hash input will have a significant impact on the hash output, but wouldn't it make sense to introduce as much entropy into the final result as possible?

-
Welcome to Cryptography Stack Exchange. We have some kind of TeX-like formatting here, which allows both easier and nicer formatting than what is possible in HTML. I edited your question to include this formatting, as well as a clearer title. Feel free to revert or edit again. –  Paŭlo Ebermann Sep 5 '12 at 20:12
Danke kind sir. –  ericball Sep 6 '12 at 13:44

Summary: I don't know of any good reason why it has to be this way. In practice, I don't think it is necessary to inject the password into every iteration. As far as I know, I think the construction would still be secure (in practice) if you used the salt and password only in the input to the first iteration, and then just repeatedly hashed the result many times without feeding in the password any further.

So why does PBKDF2 do it, if it is not strictly necessary for security? I don't know. I can only speculate -- and you should take my speculation with a large grain of salt. That said, my speculation is that, by using the key in every iteration, you can get some slightly better provable-security results.

Technical speculation: it has to do with the security proof. In particular, with PBKDF2, it is possible to prove a statement along the lines of: if HMAC-SHA256 is a secure PRF, and if the password is a full-entropy full-strength crypto key, then PBKDF2(password, salt) is a secure cryptographic key. No such statement would available if every iteration after the first used a bare hash instead of a HMAC PRF; you'd need to make stronger assumptions, such as work in the random oracle model (i.e., assume that the hash is perfect in every regard).

That said, the difference in provable security feels rather negligible to me. The security claim that you can prove about PBKDF2 (without the random oracle model) is not very exciting. PBKDF2 is primarily used to derive keys from a memorable password that is not full-entropy, and that situation is not covered by the security proof above. So, as far as I can see, I don't know of any compelling reason why PBKDF2 was designed to inject the password into every iteration of the algorithm.

Standard disclaimer: don't roll your own. Please don't take this post as a justification for modifying PBKDF2 and using your modified version of PBKDF2. That would be a pretty risky thing to do. Even if we can't think of any strong reason why PBKDF2 had to be designed the way it did, it's still safer to use the standard primitive. PBKDF2 has been well-vetted, and who knows, maybe there's some problem with the variant that hasn't occurred to me.

-
I agree - repeatedly injecting low entropy into a hash function just doesn't seem "right". In addition, the last 256 bits of the SHA256 input will be zero (as Ki/Ko are defined to be 512 bits and SHA256 has a 256 bit output and a 512 bit block size); again adding low entropy to the function. If I were to design a PBKDF I'd want to inject as much entropy as possible, but I also agree with the disclaimer. –  ericball Sep 7 '12 at 16:15

It's not really PBKDF2 that uses the key twice. PBKDF2 uses HMAC, and HMAC happens to work by using the key twice.

More specifically, PBKDF2 is actually a general construction that uses a cryptographic Pseudo-Random Function (PRF) to do some of the internal work. The PRF used here is keyed HMAC. The HMAC construction itself uses two keys derived separately from the original key. From the PBKDF2 description included in the question, the $K_o$ and $K_i$ values are the outer and inner HMAC keys, respectively.

This would then shift the question to: "Why does HMAC use two keys"? This is addressed in other questions:

Another closely related question with a relevant answer: Hash function in PBKDF2.

-
I think the main question was "why was the salt only used once (at the beginning), and not also in each iteration?" –  Paŭlo Ebermann Sep 6 '12 at 7:25
Correct. I understand the HMAC construction (which is really more of a workaround to address the length-extension attack weaknesses common to Merkle–Damgård construction hash functions), but the Un = PRF( PW, Un-1 ) construction is specific to PBKDF2. If just happens that if the PRF is an HMAC then the PW (which is typically short & low entropy) is used far more than the salt (which may have much better properties). –  ericball Sep 6 '12 at 14:05
OK, I mis-understood the question. Not sure if the answer is on-topic enough to leave. –  B-Con Sep 6 '12 at 16:44

format: plain


text:
## Co-linearity

If an experiment is designed incorrectly we may not be able to estimate the parameters of interest. Similarly, when analyzing data we may incorrectly decide to use a model that can’t be fit. If we are using linear models then we can detect these problems mathematically by looking for collinearity in the design matrix.

#### System of equations example

The following system of equations:

has more than one solution since there are an infinite number of triplets that satisfy $a=1-c, b=1+c$. Two examples are $a=1,b=1,c=0$ and $a=0,b=2,c=1$.

#### Matrix algebra approach

The system of equations above can be written like this:

Note that the third column is a linear combination of the first two:

We say that the third column is collinear with the first 2. This implies that the system of equations can be written like this:

The third column does not add a constraint and what we really have are three equations and two unknowns: $a+c$ and $b-c$. Once we have values for those two quantities, there are an infinity number of triplets that can be used.

#### Collinearity and least squares

Consider a design matrix $\mathbf{X}$ with two collinear columns. Here we create an extreme example in which one column is the opposite of another:

This means that we can rewrite the residuals like this:

and if $\hat{\beta}_1$, $\hat{\beta}_2$, $\hat{\beta}_3$ is a least squares solution, then, for example, $\hat{\beta}_1$, $\hat{\beta}_2+1$, $\hat{\beta}_3+1$ is also a solution.

#### Confounding as an example

Now we will demonstrate how collinearity helps us determine problems with our design using one of the most common errors made in current experimental design: confounding. To illustrate, let’s use an imagined experiment in which we are interested in the effect of four treatments A, B, C and D. We assign two mice to each treatment. After starting the experiment by giving A and B to female mice, we realize there might be a sex effect. We decide to give C and D to males with hopes of estimating this effect. But can we estimate the sex effect? The described design implies the following design matrix:

Here we can see that sex and treatment are confounded. Specifically, the sex column can be written as a linear combination of the C and D matrices.

This implies that a unique least squares estimate is not achievable.

## Rank

The rank of a matrix columns is the number of columns that are independent of all the others. If the rank is smaller than the number of columns, then the LSE are not unique. In R. we can obtain the rank of matrix with the function qr, which we will describe in more detail in a following section.

Sex <- c(0,0,0,0,1,1,1,1)
A <-   c(1,1,0,0,0,0,0,0)
B <-   c(0,0,1,1,0,0,0,0)
C <-   c(0,0,0,0,1,1,0,0)
D <-   c(0,0,0,0,0,0,1,1)
X <- model.matrix(~Sex+A+B+C+D-1)
cat("ncol=",ncol(X),"rank=", qr(X)$rank,"\n")  ## ncol= 5 rank= 4  Here we will not be able to estimate the effect of sex. ## Removing Confounding This particular experiment could have been designed better. Using the same number of male and female mice, we can easily design an experiment that allows us to compute the sex effect as well as all the treatment effects. Specifically, when we balance sex and treatments, the confounding is removed as demonstrated by the fact that the rank is now the same as the number of columns: Sex <- c(0,1,0,1,0,1,0,1) A <- c(1,1,0,0,0,0,0,0) B <- c(0,0,1,1,0,0,0,0) C <- c(0,0,0,0,1,1,0,0) D <- c(0,0,0,0,0,0,1,1) X <- model.matrix(~Sex+A+B+C+D-1) cat("ncol=",ncol(X),"rank=", qr(X)$rank,"\n")

## ncol= 5 rank= 5


text:
Open access peer-reviewed chapter

# Microbial Enhanced Oil Recovery

By Aliya Yernazarova, Gulzhan Kayirmanova, Almagul Baubekova and Azhar Zhubanova

Submitted: October 2nd 2015Reviewed: July 4th 2016Published: October 19th 2016

DOI: 10.5772/64805

## Abstract

The ever-rising global demand for energy and the issue of large volumes of unrecovered oil after primary and secondary oil production operations are driving the development and/or advancement of enhanced oil recovery (EOR) techniques. Conventional EOR processes include thermal, immiscible and miscible gas injection, chemical, and microbial enhanced oil recovery (MEOR), among others. This chapter provides an overview of MEOR including its history, strata microflora, mechanisms of MEOR for oil recovery, and a brief recount of field MEOR applications.

### Keywords

• microbial enhanced oil recovery
• MEOR
• microorganisms
• strata microflora
• biosurfactants
• oil reservoirs

## 1. Introduction

The necessity of improving and/or advancing the current enhanced oil recovery (EOR) processes to make them more efficient has attracted the attention of researchers and oil field operators. Thus, over the last few decades, this problem has received constant attention resulting in slow but steady growth of the average oil recovery factors. For instance, at present the worldwide average recovery rate is about 30%, whereas in the USA, the average oil recovery factor is 39%. However, many experts believe that in the foreseeable future the recovery factor may well reach 50–60% and even 70–80% [1].

The development of an oilfield refers to the process of displacing the accumulated liquid and gas hydrocarbons in the reservoir towards production wells. Oil is produced initially using the natural driving energy of the reservoir (i.e., primary recovery operations), or by introducing energy into the reservoir during secondary oil recovery (i.e., waterflooding or gas flooding), as soon as the natural reservoir energy is depleted.

Particularly, in Kazakhstan most of the hydrocarbon deposits have already been discovered and commercially produced. Currently, fewer and fewer drilling sites in those mature reservoirs are of interest from the commercial standpoint. In this regard, the residual oil left behind in these mature hydrocarbon deposits after primary and secondary oil recovery offers an opportunity for the implementation of EOR processes, including the application of microbial enhanced oil recovery (MEOR) technology.

## 2. Review on MEOR

### 2.1. History of MEOR

In 1926, J. W. Beckman [2] came to the conclusion that it was necessary to develop additional methods to augment oil recovery beyond primary and secondary oil recovery processes. Therefore, he proposed the utilization of microorganisms as one of the solutions to the oil recovery issue. Later on, the use of microorganisms for oil recovery enhancement was patented by C. E. ZoBell in 1946 [3], since then, the MEOR process has been validated by numerous studies and successful fields tests, the first of them carried out in Arkansas, USA, in 1954 [4].

Since the 1970s, intense research efforts on MEOR have been made in the USA, USSR, Czechoslovakia, Hungary, and Poland. The oil crisis in the 1970s further aroused the interest in MEOR research in more than 15 countries. For instance, in 1976, the Soviet Government enacted a special regulation “…concerning measures on achieving the most efficient oil recovery processes.” This regulation defined the target volumes of additional oil recovery that were required using tertiary enhancement methods and provided economic incentives to encourage oil-production enterprises [5].

Since year 1970 until the 2000s, microbial ecology and deposit characterization were the focus of MEOR research. By 1990, MEOR reached interdisciplinary technological status. In 2007, a review of 322 MEOR projects in USA showed that 78% of the total number of projects were successful in enhancing oil recovery; while no cases of lowered oil recovery were revealed [6]. At present, there is a grown interest in the application of MEOR to enhance oil production from depleted reservoirs, because its low capital cost and environmental friendliness.

MEOR mechanisms are the same mechanisms obtained from other chemical enhanced oil recovery (EOR) methods; however, MEOR presents the advantage that microbial metabolites are directly produced in the reservoir rock formation, which makes them more effective. Furthermore, microorganisms metabolize different hydrocarbons at different rates [6].

Figure 1 presents a breakdown of the worldwide recoverable petroleum reserves by type and region prepared by Meyer and Attanasi [7] and Schmitt [8].

Worldwide accumulations of heavy oil and bitumen are about five times higher than the reserves of light conventional oils. For instance, heavy oil resources are an essential part of the oil industry in Kazakhstan as well as in a number of other oil-producing countries.

The largest reserves of bitumen and heavy oil are located in Canada and Venezuela; while significant reserves are also found in Mexico, the United States, Russia, Kuwait, and China [9].

Kazakhstan is currently experiencing a period of late-stage development. Oil fields under waterflooding have reached a high water cut ranging from 80 to 90%, while a large volume of undeveloped oil reserves (up to 60–-70%) are located in deep oil reservoir formations. In addition, most deposits of Kazakhstan are characterized by high viscosity oils and complex geological structures [10].

### 2.2. MEOR: Challenges and Opportunities

Primary and secondary oil recovery processes achieve on a worldwide basis an average recovery of 33% of the original oil in place (OOIP); while the unrecovered oil (67%) might be retained in the reservoir by viscous and/or capillary forces. Conventional chemicals, such as solvents and surface-active compounds (surfactants) are used during chemical EOR applications. Solvents reduce the oil viscosity to improve the oil mobility by overcoming viscous forces; while surfactants reduce the interfacial tension between oil and rock or oil and water overcoming capillary forces. These chemicals are added to the injection water and transported within the reservoir during water flooding, however, the chemicals reach only the places where oil has already been displaced by water; furthermore, the chemicals could be partially consumed and/or retained within the rock formation before they reach the target area in the reservoir for their intended use [6].

The injection of solvents and surfactants into some reservoirs have yield unsatisfactory results because the chemicals failed to contact the residual oil for the required time period, which is needed to achieve a long-term effect. Another problem is the natural heterogeneity of the reservoirs; therefore, the injected chemicals inevitably flow along the paths of least resistance (i.e., high permeability zones, natural fractures, etc.) where the saturation of residual oil is usually the lowest.

It has been known for decades that specifically selected microorganisms are capable of metabolizing hydrocarbons producing organic solvents, such as alcohols, aldehydes, surface-active fatty acids, and other metabolites which can interact with the crude oil improving its fluidity. Other oil production issues such as the presence of paraffin, emulsions, and corrosion problems can also be controlled using microorganisms. For instance, extensive research has been conducted on the use of biosurfactants (BS) for enhanced oil recovery applications [1114].

Prior to the application of MEOR technologies, the projects are assessed to determine the compatibility of the crude oil and reservoir properties with MEOR taking into account the physicochemical properties of the crude oil, reservoir production performance, and reservoir properties (i.e., temperature). At the preliminary stage, reservoir fluid samples are collected and tested for compatibility with the MEOR systems. The first stage is the identification of the indigenous hydrocarbon-consuming bacteria, which is already adapted to the in situ reservoir conditions; after which the best action strategy for each project is designed and developed [4, 6].

MEOR can be applied on individual wells as follows: (1) from the well being treated or (2) from the target well and adjacent wells of the same reservoir. The MEOR solution is injected into adjacent wells in the same way as water is injected into the reservoir. The volume of the MEOR biomaterial to be injected is calculated based on the pore volume of the target reservoir. The solution is mixed and pumped through the injection well followed by the injection of water to drive the biological solution into the oil saturated zones. Then, the treated well is shut in for the required period of time (normally 24 h to 7 days) after which oil production is resumed. This procedure is repeated every 3–6 months to enable microorganisms to move deeper into the deposit to oil saturated zones [6].

Some of the general advantages of MEOR are outlined as follows:

• Increase of the productivity of the oil fields [9];

• Increase in the total oil produced and more efficient operation of wells and oil fields;

• Increase of the viscosity of the formation water due to the upsurge of biomass concentration and the microorganisms’ metabolic products, such as soluble biopolymers, which reduces the mobility of the formation water within the formation rock [9];

• The MEOR set up is less expensive, because the injected bacteria and nutrients are inexpensive [15, 16];

• Low energy input requirement for microbes to produce MEOR agents [16];

• Reduced of the operations downtime [9];

• MEOR is environmentally friendly, because microbial products are biodegradable [15, 16].

In terms of the quality of the oil produced, some benefits are [9]:

• An increase of light alkanes <C20;

• Reduction of the average content of C20–C40 alkanes;

• Biodegradation of high molecular heavy hydrocarbon components;

• Splitting of aromatic ring structures;

• Splitting of phenolic ring chemical structures;

• Transformation of sulfur-containing organic compounds;

• Emulsification of crude oil that can be easily mobilized to the production well.

MEOR methods can be divided into two main groups:

1. Ex-situ production of the MEOR metabolites such as biosurfactants, biopolymers, and emulsifiers using exogenous or indigenous bacteria. In this case, microorganisms are grown using industrial fermenters or mobile plants and then injected into the oil formation as aqueous solutions.

2. In-situ production of the MEOR metabolites. In this case, the formation of metabolites is the result of the microbiological activity that takes place directly in the reservoir. The MEOR metabolites are produced by indigenous bacteria or by exogenous bacteria that are injected into the reservoir.

In-situ MEOR can be divided into two categories depending upon the method of injection of microorganisms and nutritional media (e.g., molasses, whey, and other waste food or chemical products) into the reservoir [17]. The first category consists in the in-situ stimulation of the natural indigenous microflora of the reservoir by means of injecting nutrients into the reservoir. The alternative (second category) is the injection of microbial cultures (exogenous or indigenous) along with nutrients; which is the preferred mode of application in the field. In any case, the development of these methods is impossible without the knowledge of the physicochemical and microbiological conditions in the oil bed. Oil recovery by water flooding is characterized at later stages by the formation of a mature biocenosis. The growth of this integrated microorganism community depends on the availability of nutrients.

The in-situ production of metabolites is carried out in two stages. First, water and oxygen are pumped into the formation as a water-air mixture containing mineral salts, nitrogen, and phosphorous to activate the indigenous microflora. In the presence of water and air, aerobic bacteria oxidize hydrocarbons producing low molecular weight organic acids (acetic, propionic, butyric, etc.), alcohols (methanol and ethanol), biosurfactants, and carbon dioxide, which increase the pressure in the reservoir [1820].

In the second step, oxygen-free water is injected into the reservoir to activate anaerobic indigenous bacteria that metabolize crude oil to acids, and gas (i.e., methane, carbon dioxide). The accumulation of these biogases increases the reservoir pressure. If the pressure in the reservoir is high enough, methane could be dissolved into the liquid hydrocarbon phase reducing its viscosity. Similarly, carbon dioxide could also reduce the oil viscosity if the pressure in the formation allows the miscibility of CO2 into the bulk oil phase. A reduction of the oil viscosity improves the oil-displacing properties through the reservoir increasing oil production [14]. Furthermore, CO2 could react with the minerals in the rock and dissolve carbonate increasing the permeability of the formation rock.

In the oil industry, MEOR has been applied for several uses besides enhanced oil recovery, such as well stimulation; remediation of oil spills in soil and ground water; and to clean borehole, down hole equipment, and piping, among others.

### 2.3. MEOR process components

The MEOR process consists of two essential components: hydrocarbon-consuming microorganisms and a nutritional medium as the source of nitrogen and phosphorus. Hydrocarbon-consuming microorganisms can be exogenous or indigenous. Indigenous are isolated for characterization from the hydrocarbon deposit where they will be employed.

The use of industrial byproducts as nutritional media such as molasses [2124], corn steep liquor [25], and cheese whey [24] has been documented. The injection of nitrate aqueous solution at a concentration of 1.5 g/l of injected water has been recommended to suppress the activity of sulfate-reducing bacteria [22]. Reduction of the cost of nutrients during the application of MEOR processes can be achieved by injecting only nitrogen and phosphorous sources. Nitrogen is an essential nutrient for bacterial growth. Likewise, phosphorous is another key nutrient. If phosphorous nutrients are lacking, microbial cells cannot synthesize enough ATP for their metabolic activity [26].

### 2.4. Reservoir microflora

Microbial communities in oil rock formations are dated as the Earth’s most ancient biocenoses, which sank to great depths along with organic residues and biogenic sludge.

Numerous varieties of microorganisms have been isolated and detected from different oil reservoirs such as sulfate and sulfur reducers hydrogenotrophic and heterotrophic methanogens [2730], fermentative bacteria [31, 32], hydrocarbon and oil-oxidizing bacteria [19, 33], iron and manganese reducing microbes [34].

The presence of indigenous microflora and exogenous microorganisms in water and oil-bearing deposits has been demonstrated [3]. Exogenous microorganisms have been introduced into the reservoirs during drilling and flooding (i.e., secondary and tertiary oil recovery) operations. In the absence of molecular oxygen (i.e., absence of a terminal electron acceptor), microbial hydrocarbon decomposition is possible through anaerobic respiration using nitrate, iron oxide, carbon dioxide, or sulfate. Interspecific electron transfer is also possible with methanogenic or sulfate reducing bacteria as biological acceptors. In oil strata with temperatures between 20 and 80°C, there are complex microbial communities made up by fermentative bacteria and methanogens that can oxidize hydrocarbons and reduce sulfur, sulfate, and iron. The microbial count in high temperature oil reservoirs is low.

The studies of microbial communities conducted on samples of formation water from the Zhetybay and Kulsary oil fields located in Western Kazakhstan gave total aerobic counts of 1.8 106 and 25.1 106 cells/ml, respectively. The number of aerobic microorganisms present in the water samples from the Zhetybay field is lower than the bacterial count from the Kulsary field by an order of magnitude. While the count of anaerobes is 0.38 105 cells/ml for the Zhetybay field sample and 0.5 102 cells/ml for the Kulsary field. These observations correlate well with the respective depth of each reservoir; the water samples from the Kulsary field were collected at a depth of 250 m; while the water samples of the Zhetybay field were collected at a depth of 1900 m, therefore it is expected that at deeper reservoirs conditions (i.e., Zhetybay field) anaerobic microorganism would adjust better. It has been reported that in deep water and oil-bearing strata the total bacterial count is as high as 10 million cells/ml [35].

The effect of microorganisms is significant if they are numerous and physiologically active. An arbitrary threshold for bacteria is estimated at 1 million/1 g substrate since it is only in such quantities that they can have significant ecological impact. For each ecological factor (temperature, amount of nutrients, concentration of microcells, and trace elements), there are optimum values which favor the growth of an organism and the extreme values at which growth is suppressed. At values close to the extremes of the preferred range for a given organism, its survival is still possible though its growth is limited because the organism is under physical stress conditions. Microbiological studies on bacteria obtained from the Zhetybay and Kulsary hydrocarbon deposits show that aerobes play an important ecological role since they are found in large numbers and in physiologically active states [35].

Exogenous bacteria such as allochthonic bacteria are present in oil reservoirs, which were introduced during water injection creating a mixture of exogenous and indigenous microflora. At reservoir depths of 1–3 km, thermophilic microbial communities are found. These microbial communities are made up of microorganisms commonly found in deep reservoirs and bacteria normally encountered in shallow areas of the reservoirs (i.e., <1 km) but in lower numbers.

For instance, the Zhetybay and Kulsary oil reservoirs contain several groups of microorganisms including spore-forming bacteria, Micromycetes, Pseudomonas, Bacillus, Enterobacteriaceae, with the most prevalent being the spore-forming bacteria whose counts reach 0.12 105 cells/ml [35].

Total bacterial counts and the abundance of certain groups of aerobic and anaerobic bacteria are remarkably lower in oil reservoirs than the count of bacteria determined in the water used during waterflooding. The reason is that not all microorganisms survive extreme reservoir oil conditions. Some bacteria may be immobilized on the surface of the rocks lowering the number of bacteria in the liquid phase. Viable cells of methanogenic microorganisms have been found in reservoir fluids (i.e., formation brine) with salinity as high as 200 g/l, however, these and other microorganisms were also present in large numbers in substantially desalinated fluids [35].

Microbial community in oil reservoirs can be considered as closed and semiclosed systems, because they exist in an environment hindered from water exchange, which is characterized by a slow mass transfer at constant temperature in the absence of atmospheric air and sunlight. In this ecosystem, oil is the main source of energy for the microbial community. Molecular nitrogen and ammonium nitrogen are sufficient to meet the needs of the microflora. The phosphorus content is small, which limits the biogenic processes in this ecosystem. Therefore, microbiological processes proceed slowly due to low water exchange and lack of nutrients. The development of oil reservoirs by water injection introduces dissolved oxygen into the system that activates microbiological processes and as result oil biodegrades [36].

Aerobic microorganisms have been found in formations with temperatures ranging from 20 to 70°C and pH ranging from 6.0 to 8.4. Some of these aerobic bacteria have been identified as Rhodococcus ruber, Arthrobacter oxydans, Kocuria rosea, Gordonia rubropertincta, Cellulomonas cellulans, Bacillus subtilis, B. cereus, Pseudomonas fluorescens [14, 22, 3740]. Thermophilic microorganisms can grow at oil reservoir temperatures ranging from 40 to 70°C, at pH ranging from 6.0 to 7.8, and salinity concentrations from 0 to 5% NaCl. In high temperature oil reservoirs, hydrocarbon-oxidizing bacteria are a common component of the biocenoses in the bottom-hole areas of the water injection wells through which dissolved oxygen enters the stratum. Hydrocarbon-oxidizing bacteria found in these locations are often spore-forming, which allows survival in extreme environmental conditions [35].

Wang et al. isolated three thermophilic hydrocarbon-degrading species, such as Bacillus sp., Geobacillus sp., and Petrobacter sp. that could tolerate 55°C of temperature [41].

Thermophilic bacteria were isolated from a reservoir, located at Maracaibo Lake, Venezuela, which has temperatures ranging from 60 to 80°C and pressures ranging from 1200 to 1500 psi [42]. Moderately, thermophilic spore-forming sulfate-reducing bacteria (Desulfotomaculum and Bacillus) have been identified in the Zhetybay high temperature oil field in Kazakhstan [35].

The anaerobic microflora present in oil reservoirs are commonly bacteria of the genera Bacteroides, Clostridium, Thermoanaerobacter, Thermococcus, Thermotogales [43], Petrotoga [44], Thermotoga [45], Desulfotomaculum [46], Caminicella [47], Geosporobacter [48]. Screening for microbial consortia from some Omani oil wells by Al-Bahry et al. [49] showed a total of 30 genera and 69 species of microorganisms. In this study, most of the detected genera were found to be anaerobic, thermophilic, and halophilic and some of them were documented to be suitable candidates for MEOR.

### 2.5. MEOR oil recovery mechanisms

During the MEOR process, the components are mixed at surface facilities and injected into the oil reservoir. Inside the reservoir, MEOR-bacteria are transported by the injected water and accumulate in porous zones at the oil/rock and oil/water interfaces. Bacteria utilize very small amounts of oil and produce metabolites such as solvents, surfactants, acids, and carbon dioxide. These bioproducts interact with the oil in the reservoir to reduce the oil viscosity, interface tension at the oil/rock and oil/water interfaces, improve rock permeability by removing paraffin, mud, and other debris that plug the porous media [15, 50]. Microbial cells are continuously generated as well as the in-situ production of metabolites. The prolong interaction of metabolites with the oil in the reservoir, changes the oil properties in such a way that immobile unrecoverable oil is converted into movable oil that can flow to the production wells increasing oil output accordingly.

Microbial degradation of oil, which is a complex chemical compound, is the result of cometabolism of microorganisms where the metabolism’s products of the hydrocarbon-oxidizing bacteria serve as the substrate for other physiological groups in the reservoir. Hydrocarbons are decomposed to produce fatty acids that can be utilized by other microorganisms [51].

The main mechanisms acting on oil recovery by MEOR are summarized as follows:

1. Formation of bioacids that could dissolve some of the minerals (i.e., clays, carbonates, etc.) contained in the formation rocks. Rock dissolution increases the porosity and permeability of the reservoir [5254];

2. Production of solvents and biogases, leading to lower oil viscosity that facilitates oil displacement through the porous media [5558];

3. Formation of biosurfactants, biopolymers and other compounds, that could interact with the crude oil by emulsifying the oil, reducing its viscosity, and reducing the interfacial tension at the oil-water interface [5963];

4. Production of microbial biomass that could change the wettability of the oil rock [55, 64].

One of the most important functionalities of oil-oxidizing microorganisms is their capability of using hydrocarbons to produce biosurfactants, which emulsify hydrocarbons. The hydrocarbon-oxidizing microorganism’s strains that are very active in producing biosurfactants are: Pseudomonas aeruginosa, Bacillus subtilis, Mycobacterium rhodochrous, Rhodococcus erythropolis, Candida lipolytica, and Torulopsis gropengiesseri. Microorganisms belonging to different genera have the ability to metabolize hydrocarbons including more than 300 fungal, bacterial, yeast, and actinomycetes strains. The hydrocarbon-oxidizing ability is quite common in bacteria belonging to the genera Mycobacterium, Rhodococcus, Pseudomonas, Micrococcus, and Bacillus. In fungi and yeast-like organisms, this faculty is often found in nonsporogenic Candida, Trichosporon, and Exophialia. The vast majority of Rhodotorula species is also capable of oxidizing hydrocarbons [6569].

The implementation of MEOR requires low capital investment; while it offers high efficiency, and environmental friendliness. The initial phase of the MEOR process is the partial oxidation of residual oil in the bottom-hole area that yields bioproducts such as carbon dioxide, low-molecular-weight fatty acids, and other organic compounds. Further, when these bioproducts are transported by the injected water into the anaerobic zones of the reservoir, methanogenic microorganisms are activated. Production of methane is important because this is an easily extractible gas that can be dissolved into the oil phase (i.e., if the reservoir pressure is high enough) improving the oil mobility [70].

During waterflooding, dissolved oxygen in the water is delivered to the strata. This oxygen is rapidly consumed at the bottom-hole area during the microbial oxidation of residual oil, which causes the stimulation of anaerobic bacteria, particularly, methanogens, in the oxygen-free zone of the stratum [70]. The number of aerobic hydrocarbon-oxidizing and oligocarbophilic bacteria grows to a less extent, however, at the same time the content of anaerobic metabolism products in oil formation waters increases significantly. During this process, carbonate and sulfate content increases.

Foam-forming organic substances that reduce the interfacial tension at the oil/water interface by a factor of 100 have been identified to be caused by microbiological oil oxidation products in the bottom-hole area [71].

Oil recovery by waterflooding can be viewed as a natural fermenter, where continuous microbial cultures could be maintained. These microbial cultures could be activated by the injection of microorganisms and nutritional medium components. In this case, residual oil serves as the main substrate for microorganisms; while in the bottom-hole area, a specific microbial community is formed whose activity can be regulated [71].

The temperature of the oil reservoirs determines the types of microbial communities. In the bottom-hole areas of the injection wells, the temperature corresponds to the temperature of the injected water. In high temperature reservoirs, as is the case of the Zhetybay oil field, cold water is injected, therefore mesophilic bacteria prevail at these conditions compared to the thermophilic communities of the Uzen oil field in Kazakhstan, where hot water is injected [71].

The implementation of MEOR starts with the addition of biological materials to the injection water. Microorganisms enter the reservoir mixed with the injected water through the existing flooding system without affecting the injection rate or pressure. The implementation of MEOR process requires very small modifications, if any, to the existing water injection equipment, so that the flooding process is not interrupted [6].

After the implementation of the MEOR project, it is continuously monitored through bacteria population growth and the oil output rate within certain period of time. The hydrocarbon-oxidizing bacteria population is kept under continuous surveillance after the injection of MEOR fluids. The population size is compared to that of the indigenous hydrocarbon-oxidizing bacteria before the beginning of the process. Normally, such population starts to grow slowly. In addition, the fluids produced are also monitored for the presence of hydrocarbon-oxidizing bacteria in order to assess how far the microorganisms have moved into the reservoir after injection [6].

### 2.6. Field tests applications of MEOR

There is extensive MEOR published literature on laboratory research data and pilot field trials. Although at present widespread commercial use of the MEOR technology has not taken place yet.

Biotechnological methods for increasing oil recovery have to solve a number of practical problems [72], which are summarized as follows:

1. The preparation of suitable microorganisms and microbial associations highly active at the specific conditions of the reservoir, including the composition and properties of the crude oil. Most of the microorganisms that adapt to the conditions of the field could have little effect on the composition and properties of the crude oils. Industrial applications require new strains of microorganisms with the following qualities: tolerant to high temperatures and salinities concentration, as well as capable of synthesizing surfactants and polysaccharides.

2. The establishment of techniques to create appropriate reservoir conditions to favor the growth and activity of specific microorganisms. This requires further exploration of ways to introduce additional nutrients, primarily nitrogen and phosphorus compounds.

3. The development of cost-effective methods for sulfate reduction. Reservoir conditions are ecological niches for sulfate-reducing bacteria. It is necessary to control the generation of hydrogen sulfide because it creates the problem of a toxic aggressive environment, corrosion, higher sulfur content in the crude oil, toxic products, and other undesirable consequences.

Maudgalya et al. [73] reviewed 407 MEOR field trials worldwide. The field trials were classified according to the following parameters: reservoirs’ lithology and properties, microorganisms, nutrients, type of test, and type of recovery mechanism. From the total 407 field trials, 333 field trials were applied following the well stimulation method, 26 of the trials were conducted using the waterflooding and 44 field trials were conducted as single well (huff-puff scheme) applications; while details of the application method for the remaining four field trials were not provided. This survey indicated that the primary mechanisms for MEOR were permeability profile modification, increase of capillary number (i.e., biosurfactants, alcohols, biopolymers, and acids), biodegradation of heavy crude oil components making the oil less viscous, and the swelling of the oil due to the absorption of biogas (i.e., CO2 and CH4) within the bulk oil phase.

Careful review of the common characteristics and results observed from these 407 MEOR field trials indicate that successful field trials were obtained at the following conditions:

• Minimum reservoir permeability of 75 md to ensure propagation of bacteria and nutrients deep into the reservoir;

• Reservoir temperature <200°F;

• Brine salinity <100,000 ppm;

• Bacteria species commonly used: anaerobic bacteria (i.e., Clostridia). The bacterium Clostridium showed to be effective in both sandstone and carbonate reservoirs. Bacillus (i.e., aerobic) species were also used or combination of them. The use of indigenous bacteria is strongly recommended because they only need the supply of nutrients and have a greater chance of growing at reservoir conditions, making the process less costly;

• Nutrient: the most common organic nutrient used was molasses; while phosphorus and nitrogen fertilizers were the most common inorganic nutrients;

• Oil saturation: ranging between 45 and 70%;

• Candidate fields most suitable for MEOR are waterflooded fields with relatively high oil saturations [73].

The Activated Environment for Recovery Optimization (AERO) technology has been developed for improving waterflood performance. The AERO system is a microbial process designed to increase oil recovery during waterflooding by the following mechanisms: improved sweep efficiency due to microdiversion of fluid pathways at the pore level, interfacial tension reduction, and residual oil mobilization (i.e., biosurfactants). This technology has been successfully implemented by Statoil offshore Norway and in the Stirrup field in southwest Kansas, USA. Highlights of this technology are minimum to none capital investment with very low risk for implementation and high performance efficiency at low operational costs [74].

Research conducted to establish the potential for MEOR application at the heavy oil Schrader Bluff formation on the North Slope of Alaska indicated that the viable mechanisms for driving incremental heavy oil recovery are:

• Wettability alteration;

• Permeability modification causing improvement of reservoir conformance;

• Some reduction of the interfacial tension between oil and water.

This study also demonstrated that the most important criteria for selecting a reservoir for MEOR applications are the reservoir temperature and formation brine salinity, which must favor bacterial growth. Furthermore, an effective MEOR application depends on the optimal use of the appropriate microbes and nutrients and their proper application in the reservoir [75].

DuPont possesses a solid expertise in MEOR and considers it a low-risk and low-cost technology to produce incremental oil from mature fields. DuPont has established a set of reservoir criteria for its successful application as follows:

• Reservoir temperatures <160°F;

• Moderate salinity levels up to 100,000 ppm;

• Reservoir permeability above 30 md to ensure the propagation of the microbes and nutrients deep into the reservoir;

• The reservoir must be under a waterflooding recovery.

According to DuPont’s experience, the main mechanisms for oil recovery are permeability modification due to the formation of a biofilm on the rock surface and wettability modification. Successful field trials conducted by DuPont indicate that oil recovery from mature fields can be increased up to 25% with a cost of $10 per incremental barrel of oil. Furthermore, DuPont considers the MEOR technique to be more cost effective compared to other EOR processes, such as CO2 flooding or polymer flood [76]. A biopolymer, Schizophyllan, has been developed by Wintershall. The unique properties of this biopolymer are tolerance to high salinity (up to 19 wt%), tolerance to temperatures as high as 275°F, mechanical stability, and high viscosity. Therefore, the Schizophyllan biopolymer would make possible the application of polymer flooding in harsh reservoir environments. The main downside of this biopolymer is its susceptibility to bacterial degradation; however, this has been prevented by the addition of biocides. A pilot test has indicated that the performance of polymer flooding using this biopolymer has rendered oil recoveries ranging from 20 to 25 % higher than the oil recoveries expected from conventional waterflooding [77]. Successful MEOR application in a mature waterflooded reservoir in Saskatchewan, Canada has been reported [78]. This MEOR application consisted in the stimulation of indigenous bacteria through the injection of the appropriate nutrients. Production data obtained from this MEOR field application indicate higher oil production rates, incremental oil recovery, and decreased water cuts (up to 10%), which decreased operating costs due to reduced lifting and water treatment costs. In this field application, it was considered that the main MEOR mechanism was modification of the oil and water relative permeability driven by the interactions at the oil-water-microbes interface. Several benefits of this MEOR approach compare to other MEOR applications schemes and other EOR processes are as follows [78]: • Low application costs; • Low process cost per incremental oil production, on average it was US$ 6 per barrel of oil produced;

• No capital outlay required to implement the MEOR project;

• Low risk to implement;

• Environmentally friendly.

Numerical modeling has been used to attempt the quantitative prediction of the performance of the MEOR process [73]. A study conducted by Eduarda et al. [79] in which a finite difference method was applied, indicated that appropriate bacterial growth within the reservoir is the determining variable affecting the oil recovery factor.

## 3. Conclusion

MEOR technology makes use of special indigenous or exogenous microbial strains and nutrients that are injected into the reservoir to enhance oil production. The metabolic action of the injected exogenous microbial strains and the indigenous reservoir microflora produce metabolites such as gases, alcohols, and surface active compounds (biosurfactants) that interact with the crude oil. Biogases provide additional reservoir driving pressure; while bioalcohols and biosurfactants reduce oil viscosity and surface tension between oil-water and oil-rock, respectively. Under the effect of metabolites, the crude oil flowing properties are modified causing its release and mobilization toward the production wells enhancing the oil flow output.

The following metabolites interact with the crude oil changing its physicochemical properties:

• Organic acids (i.e., acetic, propionic, and butyric acids);

• Solvents (i.e., acetone, aldehydes, low-molecular-weight alcohols, ketones, etc.);

• Biomass (i.e., cell debris);

• Biopolymers (i.e., xanthan, scleroglucan, polysaccharides);

• Biosurfactants (i.e., rhamnolipid, surfactin);

• Biogases (i.e., methane, CO2, etc.).

MEOR is an easy-to-use process which requires minimum, if any, upgrade of the existing process equipment and facilities. This process has the potential to recover oil reserves that otherwise would remain immobile and unrecoverable. This process overcomes natural and chemical barriers in oil deposits that hinder microbial growth. MEOR is safe and environmentally friendly that does not cause any threat to plants, animals, and humans.

## How to cite and reference

### Cite this chapter Copy to clipboard

Aliya Yernazarova, Gulzhan Kayirmanova, Almagul Baubekova and Azhar Zhubanova (October 19th 2016). Microbial Enhanced Oil Recovery, Chemical Enhanced Oil Recovery (cEOR) - a Practical Overview, Laura Romero-Zeron, IntechOpen, DOI: 10.5772/64805. Available from:

### chapter statistics

2Crossref citations

### Related Content

Next chapter

By R. Tao

#### Introduction to Enhanced Oil Recovery (EOR) Processes and Bioremediation of Oil-Contaminated Sites

Edited by Laura Romero-Zerón

First chapter

#### Advances in Enhanced Oil Recovery Processes

By Laura Romero-Zerón

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

View all Books


text:
# Griffith's 3.33

I am "continuing this thread" in hopes of asking questions that deal with the meaning of the question. https://www.physicsforums.com/threads/griffiths-e-m-3-33-write-e-field-of-dipole-moment-in-coordinate-free-form.359973/
1. Homework Statement

Show that the electric field of a "pure" dipole can be written in the coordinate-free form
$$E_{dip}(r)=\frac{1}{4\pi\epsilon_0}\frac{1}{r^3}[3(\vec p\cdot \hat r)\hat r-\vec p].$$

## Homework Equations

$$E_{dip}(r)=\frac{p}{4\pi\epsilon_0r^3}(2\cos \hat r+\sin\theta \hat \theta)$$

## The Attempt at a Solution

I am trying to understand what "coordinate free" means. If the answer is in terms of r hat and theta hat, doesnt that contradict "coordinate free"? AND i would get $$p = pcos(\theta) \hat r - psin(\theta) \hat \theta$$. Why doesn't p depend on PHI? If it's coordinate free why are we restricting our coordinates to r and theta??

Last edited:

"Coordinate free" means you don't need to define the coordinate system to write your equation. $\hat{r}$ is a unit vector from the center of the dipole to the observation point, so given the orientation of $\mathbf{p}$ in space, the relative direction of $\hat{r}$ with respect to $\mathbf{p}$ will automatically follow.


text:
# The lengths of the sides in a right triangle form 3 consecutive terms of a geometric sequence. How do you find the common ratio of the sequence?

Nov 6, 2015

The ratio must be $r = \pm \sqrt{\frac{1 + \sqrt{5}}{2}}$

#### Explanation:

Three numbers are in a geometric series if they're of the form

$a , a \cdot r , a \cdot {r}^{2}$.

If they're sides of a right triangle, then we have

${a}^{2} + {\left(a r\right)}^{2} = {\left(a {r}^{2}\right)}^{2}$

which is

${a}^{2} + {a}^{2} {r}^{2} = {a}^{2} {r}^{4}$

Simplifying by ${a}^{2}$:

$1 + {r}^{2} = {r}^{4}$

To solve this equation (which of course you can rewrite as ${r}^{4} - {r}^{2} - 1 = 0$) you can use a variable $x = {r}^{2}$ to turn it to a quadratic:

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

And this equation is quite famous, since it is the one whose solution involve the golden ratio, so

${x}_{1 , 2} = \frac{1 \setminus \pm \setminus \sqrt{5}}{2}$

Now we have to remember that $x = {r}^{2}$, and thus it must be positive. Since $\frac{1 + \sqrt{5}}{2}$ is positive, and $\frac{1 - \sqrt{5}}{2}$ is negative, we can only choose $x = \frac{1 + \sqrt{5}}{2}$

Finally, we can solve for $r$:

${r}^{2} = x = \frac{1 + \sqrt{5}}{2} \setminus \implies r = \pm \sqrt{\frac{1 + \sqrt{5}}{2}}$


text:
## Monday, May 08, 2006

### Some Detailed Views on Norway's Oil Production

The other day on theoildrum, Roberto has produced some beautiful graphs on Norway production per field. I thought that was a bright idea and decided to repeat the same exercise but on different field characteristics. The gross wellhead production (Norwegian share) per field is available in ascii format on the NPD website. I used only the gross oil production figures (I excluded NGL and condensate) resulting in 64 oil fields.
Fig 3. Ratio of the current production (2005) to the maximum production (in %).
Fig 4. Field maximum output (mbpd).
Fig 5. Field peak year.
Fig 6. Number of production wells per fields.
Fig 7. Number of injection wells per fields.
Fig 8. Average wellbore depth (kilometers).
Fig 9. ratio of the number of wellbores to the peak production in mbpd.
Fig 10. Estimated logistic growth rate per fields.
Fig 11. Oil revenue per fields (inflation adjusted, US$). Fig 1. Cumulative production per field (2005, Gb). Fig 2. First year of production per field. Fig 3. Ratio of the current production (2005) to the maximum production (in %). Fig 4. Field maximum output (mbpd). Fig 5. Field peak year. Fig 6. Number of production wells per fields. Fig 7. Number of injection wells per fields. Fig 8. Average wellbore depth (kilometers). Fig 9. ratio of the number of wellbores to the peak production in mbpd. Fig 10. Estimated logistic growth rate per fields. Fig 11. Oil revenue per fields (inflation adjusted, US$).


text:
### Home > CCG > Chapter 11 > Lesson 11.1.4 > Problem11-58

11-58.

Find the volume and total surface area of each solid below. Show all work.

1. Use the Pythagorean Theorem to find the unknown side of the triangle.

Find the area of the top.

Multiply the area of the top by the height to find the volume.

Find the area of each of the sides and sum them.

$\text{Surface Area }= (2)(84) + (12)(7 + 24 + 25) = 840\text{ units}^2$
$\text{Volume = (area base)(height)} = (84)(12) = 1008\text{ units}^3$

1. The volume of a cone is $\frac{1}{3} \pi r^2h$

$\text{Volume}=\frac{1}{3}\pi(5)^2(12)$

$\text{Volume}=100\pi\ \text{un}^3$

Find the area of the base.
Then find the lateral surface areas and add them together.

$\text{base area}=\pi r^2=25\pi$
$\text{lateral surface area }= (π)(5)(13) = 65π$

$\text{Surface area} = 25π + 65π = 90π\text{ units}^2$


text:
# Chapter 14 Digital Signal Processing

In today’s technology age, signals are pervasive throughout most of the world. Humans and animals use audio signals to convey important information to conspecifics. Airplanes use signals in the air to obtain important information to ensure your safety on a flight. Cell phones are pretty much just one small digital signal processing device. They process our speech when we talk into the phone by removing background noise and echos that would distort the clearness of our sound. They obtain wifi signals to allow for us to search the web. They send text messages using signals. They use digital image processing to take really good pictures. They take a video of your dog when he’s doing something completely hilarious that you want to show your friend. The applications of digital signal processing (DSP) span numerous different fields, such as ecology, physics, communication, medicine, computer science, mathematics, and electrical engineering. Thus, having a basic understanding of DSP and it’s concepts can be very helpful, regardless of the field you decide to pursue.

In this chapter we will give a brief introduction to some central concepts in DSP and how we can explore these concepts using R. We will look at applications of DSP using some R packages designed for bioacoustic analysis. When doing digital signal processing, R is not typically the first computer language that comes to mind. Matlab, Octave, and C/C++ are often considered to be some of the best languages for DSP. But R provides numerous different packages (especially for working with audio data) that make it competitive with these languages for digital signal processing. We will use the signal package to do some simple digital signal processing, and then will use the tuneR, warbleR, and seewave packages to work with audio data to show you more specific examples of how R can be used in different fields of digital signal processing.

## 14.1 Introduction to Digital Signal Processing

First let’s go over some basics of DSP before we delve into working with signals in R. Digital Signal Processing is the use of digital tools to perform different signal processing operations, such as the analysis, synthesis, and modification of signals. But what exactly constitutes a signal? A signal is anything that carries information. In other words, it is a quantity that varies with time, temperature, pressure, or any other independent variable. As described above, signals pervade our everyday life, and thus the study of their behavior, how they work, how we can manipulate them, and how we can extract information from them is extremely important.

There are two main types of signals: continuous time signals and discrete time signals. Continuous Time Signals, as you might suspect, are continuous. They are defined at all instances of time over a given period. These types of signals are commonly referred to as analog signals. An example of an analog signal would be a simple sine curve plotted in 14.1. Notice that the sine curve is defined for every value on the interval from 0 to 2$$\pi$$. This is an analog signal.

Discrete Time Signals are not continuous. They are defined only at discrete times, and thus they are represented as a sequence of numbers (so by your experiences in R working with sequences of numbers you should already have an idea of how discrete signals are stored, how they can be manipulated, etc…). Figure 14.2 is an example of the exact same sine curve as in Figure 14.1, but in a discrete form. Notice how there are only values at specific points, and anywhere besides those points the signal is not defined. In a real-world application, these points would correspond to measurements of the signal.

Notice the differences between the two graphs. The second graph is not defined at every point and is only defined at the points where a data point exists. This type of sampling will become important later in the chapter and in the exercise when we begin to work with sound data (which by the way takes the form of these simple sine curves we are working with here). There are many other shapes and forms of signals, but since we will later be focusing on audio data, and the sine curve is fundamental to any sort of sound, we for now will focus on working with a sine curve.

Signals have a wide variety of properties and characteristics that give each signal distinct behavior. The sine curve has two important characteristics. First, a sine curve is said to be odd since it satisfies the condition sin$$(-t)$$ = -sin$$(t)$$. This is easy to recognize by looking at the graph of a sine curve as you see that it is symmetrical over the diagonal at the origin. In addition, a sine curve is a periodic signal. A periodic signal is a signal that repeats itself after a certain interval of time (called the Period). This is true of all real sine curves. Understanding the simple properties of signals like we have done with the sine curve is a useful tool in digital signal processing as it allows you to recognize simple patterns that may occur with the signal in which you are interested.

Now that we have a general understanding of what a signal is and how we can use it’s properties to learn about it’s behavior, let’s now focus on some of the most important concepts in digital signal processing, and how we can implement them in R. Here are three of the most central topics to DSP:

1. Fourier Transforms: signal processing involves looking at the frequency representation of signals for both insight and computations.
2. Noise: defined as any signal that is not desired. A huge part of signal processing is understanding how noise is affecting your data and how you can efficiently remove or manage it.
3. Filters: allow you to remove out specific portions of a signal at once, or allow you to remove noise from certain signals.

We will first briefly discuss working with noise and filters in R, and then we will work with Fourier Transforms in the context of audio data.

### 14.1.1 Sinusoidal Signals

As mentioned previously, sinusoidal signals are extremely important for signal processing. We saw an example of a continuous sinusoid and a discrete sinusoid. Here we will quickly discuss the mathematics behind coding a sinuosoid signal.

A sine wave typically takes the following form:

$f(\theta) = (\alpha) \text{sin}(b(\theta - c)) + d$

The translations that you see above from the standard sine wave (sin($$\theta$$)) have particular terms. Here we give a quick summary of the terms in the above equation and their definitions:

1. Period: the amount of time required to complete one full cycle of the sine wave. A standard sine wave has period $$2\pi$$. The sine wave described above has period $$\frac{2\pi}{|b|}$$
2. Frequency: the number of times a sine wave repeats itself within a single unit of time (which depends upon how the variable $$\theta$$ is defined). This is the reciprocal of the period so in our case this is $$\frac{|b|}{2\pi}$$.
3. Amplitude: the “height” of the sine wave, or more properly, the distance from the x-axis to the most positive point of the sine wave. The standard sine wave has an amplitude of 1. The amplitude is controlled by the $$\alpha$$ parameter, and thus our sine wave has amplitude $$\alpha$$.
4. Phase Shift: determines whether or not the sine wave passes through the point (0, 0). Our sine wave mentioned above is shifted to the right by the amount $$c$$ and shifted up by $$d$$.

Next we draw a few plots to show graphically how all these parameters influence the signal. We will graph these as digital signals.

library(dplyr)
x <- seq(0, 2 * pi, .1)
standard <- sin(x)
altered <- 2*sin(3 * (x - 1)) + 4
graphData <- tibble(x, standard, altered)
ggplot(data = graphData, mapping = aes(x = x)) +
geom_point(mapping = aes(y = standard, color = "sin(x)")) +
geom_point(mapping = aes(y = altered, color = "2*sin(3 * (x - 1)) + 4")) +
scale_color_manual("", breaks = c("sin(x)", "2*sin(3 * (x - 1)) + 4"),
values = c("blue", "red")) +
labs(x = "x", y ="")

Now that we understand the fundamentals of sinusoids, let’s see how we can work with noise and filters on sinusoids using R.

## 14.2 Noise and Filters

Using filters to remove noise and obtain only the desired portions of signals is a huge part of signal processing. Here we will give a couple examples of the many different functions available in the signal package for DSP. The signal package is a set of signal processing functions that was originally written for more “standard” signal processing languages, Matlab and Octave, but was later translated into R. It provides an extensive set of functions including filtering functions, resampling routines, and interpolation functions. To follow along yourself, install the package with install.packages("signal").

For a first example, consider the sinusoid generated below.

library(signal)
t <- seq(0, 1, len = 100)
sig <- sin(2 * pi * t)
ggplot(mapping = aes(t, sig)) +
geom_line()

This is a simple sinusoid that has an amplitude of 1 and a frequency of 1. It is not likely that when obtaining a real-world signal you would get a perfect sinusoid without any noise. Let’s take this graph and add some noise to it.

noisySig <- sin(2 * pi * t) + 0.25 * rnorm(length(t))
ggplot() +
geom_line(aes(t, noisySig), color = "red")

We add noise to the function by adding a random value (0.25*rnorm(length(t)) to each value in the signal. This is more typical of a real-world signal, as you can somewhat see the general shape (the signal you are interested in), but it is somewhat distorted as a result of noise. The signal package provides a long list of functions for filtering out noise. Here we will utilize the butter function to remove the noise from this signal in an attempt to obtain our original signal. This function generates a variable containing the Butterworth filter polynomial coefficients. The Butterworth filter is a good all-around filter that is often used in radio frequency filter applications. We then use the filter function from the signal package to apply the Butterworth filter to the data. Finally we produce a plot using ggplot2 that shows the original signal without noise, the noisy signal, and the recovered signal.

butterFilter <- butter(3, 0.1)
recoveredSig <- signal::filter(butterFilter, noisySig)
allSignals <- data.frame(t, sig, noisySig, recoveredSig)
ggplot(allSignals, aes(t)) +
geom_line(aes(y = sig, color = "Original")) +
geom_line(aes(y = noisySig, color = "Noisy")) +
geom_line(aes(y = recoveredSig, color = "Recovered")) +
labs(x = "Time", y = "Signal")

You can see that the recovered signal is not perfect, as there is still some noise in the signal, and the timing of the peaks in the signal is not exactly matched up with the original. But it is clear that we have nonetheless removed a large portion of the noise from the noisy signal. Mess around with the argument values in the butter() function in the above code. See what changing the parameters does to the recovered graph. You can also explore the wide variety of filter functions available in the signal package by exploring the package documentation here.

For a second example, suppose we are interested in not only the signal, but also the noise. We will extract the low and high frequencies from a sample signal. Let’s start with a noisy signal

t <- 1:500
cleanSignal <- 50 * sin(t * 4 * pi/length(t))
noise <- 50 * 1/12 * sin(t * 4 * pi/length(t) * 12)
originalSignal <- cleanSignal + noise
ggplot() +
geom_line(aes(t, originalSignal))

Again, you can easily recognize the pattern is sinusoidal, but there is noise in the signal that you want to extract. Perhaps you are interested in where the noise is coming from and want to analyze the structure of the noise to figure this out. Thus, unlike the previous example, we want to extract the noise from the signal and not simply eliminate it. To do this we can again use the Butterworth filter.

lowButter <- butter(2, 1/50, type = "low")
low <- signal::filter(lowButter, originalSignal)

highButter <- butter(2, 1/25, type = "high")
high <- signal::filter(highButter, originalSignal)

signals <- data.frame(originalSignal, low, high)

ggplot(signals, aes(t)) +
geom_line(aes(y = originalSignal, color = "Original")) +
geom_line(aes(y = low, color = "Signal")) +
geom_line(aes(y = high, color = "Noise")) +
labs(x = "Time", y = "Signal")

## 14.3 Fourier Transforms and Spectrograms

When working with signals you often have to consider whether or not you need to work in the time domain or the frequency domain. These two different domains can provide valuable information about a signal. The most popular way to explore signals in the frequency domain is to use Fourier Transforms. A Fourier Transform is a reversible mathematical transform developed by Joseph Fourier in the early 1800s. The transform breaks apart a time series into a sum of finite series of sine or cosine functions. This was a huge break through of it’s time, as Fourier argues that any signal can be broken down into a series of sine and cosine curves. This was a fantastic development and is still one of the most widely used tools in digital signal processing, which tells you how useful it truly is (and how brilliant Fourier was).

The Discrete Fourier Transform (DFT) is a specific form of the Fourier Transform applied to a time wave. The DFT allows you to switch from working in the time domain to the frequency domain by using the amplitude and the frequency of the signal to build the frequency spectrum of the original time wave.

To apply Fourier Transforms we use a window size. The length of the FT is controlled by the window length. Increasing the window size will increase frequency resolution, but this will also make the transform less accurate in terms of time as more signal will be selected for the transform. Thus there is a constant level of uncertainty between the time of the signal and the frequency of the signal64. Different windows can be used in a DFT depending on the application. There are numerous windows available within the seewave package (see Figure 14.3).

Computing a fourier transform on a whole sound or a single segment of the sound may not be enough information for what you desire. One great idea is to compute the DFT on successive sections along the entire sound signal. A window is “slided” along the signal and a DFT is computed at each of these slides. This process is called a Short-Time Fourier Transform. This method allows you to represent the signals in the frequency spectrum, while also maintaining most of the information from the time dimension (as Hannah Montana might say, it’s the best of both worlds).

We can plot the results of an STFT in what is called a spectrogram. The spectogram is useful in bioacoustics, acoustics, and ecoacoustics (among others) because it allows you to represent three variables in a 2D plot, which avoids using a 3D representation that is genereally not appealing. The successive DFT are plotted against time with the relative amplitude of each sine function of each DFT represented by some color scale. In other words, the spectrogram has an x-axis of time, a y-axis of frequency, and the amplitude represented by the color scheme used inside the plot (which is usually included in a scale).

Let’s use a sample audio file provided by the seewave package and produce a spectrogram of it using the spectro function. R provides multiple functions like spectro that make the creation of spectrograms and Fourier Transforms extremely easy and logical, which is one of the many reasons to perform digital signal processing within the R environment.

library(seewave)
data(tico)
spectro(tico)

Let’s explore more of the parameters for this function to get a better understanding of how it is working. Type in ?spectro in the R console. The spectro() function contains a lot of different arguments that allow you to control how the spectrogram is created. The f argument allows you to specify the sampling rate of your sound object. The wl option allows you to control the window length that is used when the successive DFTs are produced (aka the STFT). You can choose which window you want to use with the wn option. You can also specify the amount of ovlp between two successive windows with the ovlp argument. Let’s use some of these arguments and compare it to the standard spectrogram we previously produced.

spectro(tico, f = 22050, wl = 1024, wn = "bartlett", ovlp = 5)

You can immediately see that there are some slight differences between the spectrograms. The first spectrogram appears to be more precise than the second spectrogram. Explore these parameters yourself to get a better understanding of how these different properties impact the short-time fourier transform and the spectrogram.

One cool thing about the spectro() function is that it produces a graph, but it also stores the values along the three scales. If you save the call to a spectro() function, that variable will be a list containing the values along the time axis, values along the frequency axis, and the amplitude values of the FFT decompositions. These values can be accessed in familiar ways ($time, $frequency, $amp). Now that you have a visualization of the sound, we will use the tuneR package to play the sound so you can see exactly how it matches up with the spectrogram. First install the tuneR package, which is another package great for working with sound and signals in R. Then use the play function to play back the tico sound. Note that the second argument in the play function is the player argument, which may or may not need to be defined depending on your operating system and what audio players are installed on your system. In my case, I am playing the sound through the aplay player on a machine running Linux. library(tuneR) play(tico, "aplay") The audio matches up perfectly with the spectrogram. Pretty cool! ## 14.4 Analyzing Audio Data with warbleR Now that we’ve explored how we visualize audio signals with Fourier Transforms and spectrograms, let’s now explore some of the packages in R used explicitly for bioacoustic analysis of audio signals. The warbleR package was written to streamline bioacoustic research inside of R, and it provides numerous different functions for obtaining, manipulating, and visualizing bioacoustic data (and especially bioacoustic data of birds). We are going to go through an example to display some of the many useful functions in the warbleR package. Our goal is to analyze the recordings of Cedar Waxwings from the xeno-canto database to determine whether or not there is variation in these calls across large geographical distances. Along the way we will showcase many useful functions in the warbleR package, and will compute numerous meausures that give us useful information about the signal. Let’s get started! We will extract sounds from a large and very common database in the field of bioacoustics, xeno-canto. warbleR allows you to easily query the database and work with the sounds maintained in their library. We are interested in the sounds of Cedar Waxwings, which just so happen to be my favorite species of bird. They are small, beautiful, majestic birds that are fairly common in rural and suburban areas (Figure 14.4). They also have a very large geographical region, spanning across all three countries in North America. The warbleR package allows us to first query the database for the recordings of Cedar Waxwings (Bombycilla cedrorum) without downloading them. library(warbleR) cedarWax <- query_xc(qword = "Bombycilla cedrorum", download = FALSE, path = 'warbleR') ## 156 recording(s) found! names(cedarWax) ## [1] "Recording_ID" "Genus" ## [3] "Specific_epithet" "Subspecies" ## [5] "English_name" "Recordist" ## [7] "Country" "Locality" ## [9] "Latitude" "Longitude" ## [11] "Vocalization_type" "Audio_file" ## [13] "License" "Url" ## [15] "Quality" "Time" ## [17] "Date" "Altitude" ## [19] "file.name" "Spectrogram_small" ## [21] "Spectrogram_med" "Spectrogram_large" ## [23] "Spectrogram_full" "Length" ## [25] "Uploaded" "Other_species1" ## [27] "Other_species2" "Other_species3" ## [29] "Other_species4" "Remarks" ## [31] "Bird_seen" "Playback_used" ## [33] "Other_species" "Other_species5" ## [35] "Other_species6" "Other_species7" ## [37] "Other_species8" We use the query_xc function to query the database, and use the restriction of the scientific name for Cedar Waxwings so we only obtain recordings of our desired species. Notice the path = 'warbleR' argument, which indicates the directory (here called warbleR) where the audio files will be saved. We see the query_xc function returns a data frame with a lot of useful information, such as the latitude and longitude of the recording, the date, the quality of the recording, and the type of vocalization (since birds have multiple different types of vocalizations). Now we produce a map showing the locations of all of the recordings. The xcmaps function allows you to either save a map as an image to your hard drive, or you can simply load the image in the R environment. We will load the image in the R environment by setting the img argument to FALSE. xcmaps(X = cedarWax, img = FALSE) The recordings are mostly in the United States, but you can see there are recordings in Mexico and Canada as well. Now that we have an idea of where these recordings were taken, let’s look at what types of recordings we have. We will do this using the table function. table(cedarWax$Vocalization_type)
##
##          aberrant, adult, call, sex uncertain
##                                             1
##                                             1
##                                             1
##                                             5
##                                             1
##                                             1
##                                             2
##          adult, sex uncertain, song, tansgers
##                                             1
##                                             1
##                                    alarm call
##                                             2
## alarm call, call, flight call, juvenile, song
##                                             1
##                        begging call, juvenile
##                                             3
##         begging call, juvenile, sex uncertain
##                                             1
##                                          call
##                                            82
##                                          Call
##                                             2
##                                     call, dog
##                                             1
##                            call, female, male
##                                             1
##                             call, flight call
##                                             7
##              call, flight call, sex uncertain
##                                             1
##                       call, flight call, song
##                                             1
##                             call, flock calls
##                                            10
##     call, life stage uncertain, sex uncertain
##                                             1
##                                    call, song
##                                             5
##                       call, song, wing sounds
##                                             1
##                                Calls of flock
##                                             1
##                                 Feeding calls
##                                             1
##                                   flight call
##                                            11
##                                   Flight call
##                                             1
##                                   Flight Call
##                                             1
##                                juvenile calls
##                                             1
##   Seet, adult, and trill, call, sex uncertain
##                                             1
##                                          song
##                                             4
##                                     uncertain
##                                             2

Look closely at the output from this function. This is a great example of the messiness of real-world data. Users from around the world input their data into this website, and this results in many different ways of describing the vocalizations produced by the birds. You can see the users used many different ways to describe the calls of cedar waxwings. There are 82 recordings labeled as “call” so we will just focus on these recordings, but keep in mind that in a more serious study, we may want to manipulate the labels and combine vocalizations that are actually of the same type.

Now that we have the recordings we want to work with, we download them and convert them to wav files. Since this is only an example, we will look specifically at six of the calls within the cedarWax recordings to minimize downloading and computation time.65

newCedarWax <- subset(cedarWax, cedarWax$Recording_ID %in% c(313682, 313683, 313684, 321881, 329907, 361006)) query_xc(X = newCedarWax, path = 'warbleR') ## Downloading files... ## double-checking downloaded files warbleR and seewave are designed to work with wav files while the xeno-canto database stores its recordings as mp3 files. Luckily there is a very simple function mp32wav that converts all the mp3 files in the working directory to wav files. We then remove all the mp3 files from the current directory using the system function. mp32wav(path = 'warbleR') system("rm warbleR/*.mp3") warbleR gives us many easy ways to produce spectrograms for all of our desired sound files at once. To do this, we use the lspec function, which produces image files with spectrograms of whole sound files split into multiple rows. lspec(ovlp = 10, it = "tiff", rows = 5, path = 'warbleR') Now look in your warbleR directory and you should see .tiff files for all of the sound files. These files could be used to visually inspect sound files and eliminate undesired files as a result of noise, length, or other variables you are not interested in. But for this example we will use all six recordings. Remember that our ultimate goal is to determine whether or not Cedar Waxwing calls show some sort of variation across geographical distance. We need to produce some acoustic measures to compare the different recordings. First, we want to perform signal detection. In other words, we want to find the exact parts in the recordings where a cedar waxwing is performing its call. We only want to determine the acoustic parameters during these times, as this will eliminate noise from having any impact on the parameters. We can perform signal detection using the autodetec function. This function automatically detects the start and end of vocalizations based on amplitude, duration, and frequency range attributes. autodetec will output a data frame containing the recording name, selection, start time, and end time. auto_detec has a TON of parameters that you can use to help specify exactly what type of signal you are looking for in your data. To help us figure out what parameters we want to use, let’s first look at an example spectrogram of one of the recordings (Figure 14.5). The calls appear to be between 4-10 kHz in frequency. In this sample they are quite short, with none lasting longer than a second and most being less than half a second. Let’s try these two parameters along with a few others and see what we get. Let’s first do this on just one of the recordings so we don’t waste computing power if we have to change our parameters wavs <- list.files(path = 'warbleR', pattern = ".wav", ignore.case = TRUE) subset <- wavs[2] single.rec <- auto_detec(flist = subset, bp = c(4, 10), threshold = 10, mindur = 0.05, maxdur = 0.5, ssmooth = 800, path = 'warbleR')  ## Detecting signals in sound files: Here is a list of the parameters and what each means: • flist: character vector indicating the subset of files to be analyzed • bp: numeric vector of length two giving the lower and upper bounds of a frequency bandpass filter in kHz • threshold: specifies the amplitude threshold for detecting signals in percentage • mindur, maxdur: specify the minimum call length and maximum call length respectively • ssmooth: a numeric vector of length 1 to smooth the amplitude envelope with a sum smooth function • path: directory where sound recordings are stored. The auto_detec function itself does not generate a plot of the spectrogram and the identified calls. To generate a labelled spectogram saved in an image file, we use the full_spectrograms function on the output from auto_detec. full_spectrograms(single.rec, path = 'warbleR') Looking at Figure 14.6, it looks like we’ve done a pretty good job! There are a couple signals we are not detecting, but we are not getting any false positives (detecting signals that aren’t actually signals) so we will continue on with these parameters (feel free to refine them as much as you want). Let’s run the autodetec function for all the recordings and save it as a variable. We remove all null values as this would correspond to the rare situation in which the autodetec function does not detect a signal in a sound file waxwingSignals <- autodetec(flist = wavs, bp = c(4, 10), threshold = 10, mindur = 0.05, maxdur = 0.5,ssmooth = 800, path = 'warbleR') ## Detecting signals in sound files: waxwingSignals[is.na(waxwingSignals)] <- 0  Now that we have the locations of all the signals in the recordings, we can begin to compute acoustic parameters. The warbleR package provides the fantastic specan function that allows us to calculate 22 acoustic parameters at once through a batch process. This is much more efficient than computing all these parameters separately. specan uses the time coordinates from the autodetec function that we saved in our waxwingSignals variable. It then computes these acoustic parameters for the recordings, but only during the times when a signal is being performed. params <- specan(waxwingSignals, bp = c(1, 15), path = 'warbleR') names(params)  ## [1] "sound.files" "selec" "duration" ## [4] "meanfreq" "sd" "freq.median" ## [7] "freq.Q25" "freq.Q75" "freq.IQR" ## [10] "time.median" "time.Q25" "time.Q75" ## [13] "time.IQR" "skew" "kurt" ## [16] "sp.ent" "time.ent" "entropy" ## [19] "sfm" "meandom" "mindom" ## [22] "maxdom" "dfrange" "modindx" ## [25] "startdom" "enddom" "dfslope" ## [28] "meanpeakf" You can see from the names function that there are a wide variety of measures computed for each sound file. Now that we have all these measurements, let’s use them to determine whether there is any geographic variation in these cedar waxwing calls. The first step in doing this is joining the geographic location for each recording to the params data frame. The geographic location is contained within the cedarWax data frame. We will first join these tables based on the recording ID. params$Recording_ID <- gsub('.*-([0-9]+).*','\\1', params$sound.files) newCedarWax$Recording_ID <- as.character(newCedarWax$Recording_ID) finalData <- inner_join(params, newCedarWax)  ## Joining, by = "Recording_ID" We will do this using a process called Principal Components Analysis, a statistical dimension reduction technique that can be used to find latent variables that explain large amounts of variation in a data set. # Remove the non-numeric variables and then run the pca pca <- prcomp(x = finalData[, sapply(finalData, is.numeric)], scale. = TRUE) score <- as.data.frame(pca[[5]]) ID <- as.numeric(finalData$Recording_ID)
ggplot(data = score, mapping = aes(PC1, PC2)) +
geom_point(aes(color = finalData$Recording_ID, shape = finalData$Country)) +
scale_color_viridis_d() +
theme_bw()

From the graph, we see that two birds from the US form a group with a bird from Mexico, and a bird from the US forms a group with two birds from Canada. Depending on where exactly the birds from the US are located, this could potentially suggest some variation across geographical distance. We leave this to you to explore further if you so desire. But for now, we see that the warbleR package has some fantastic tools for manipulating and working with audio signals within the R environment.

## 14.5 Exercises

Exercise DSP Learning objectives: download, manipulate, and play sound files using R, produce spectrograms of audio files, use filters, use acoustic indices to analyze western New York soundscape data

1. this is a result of the common Heisenberg Uncertainty Principle↩

2. Sound files are pretty large so working with these files using the warbleR package can be time consuming.↩


text:
## Cryptology ePrint Archive: Report 2018/867

Poly-Logarithmic Side Channel Rank Estimation via Exponential Sampling

Liron David and Avishai Wool

Abstract: Rank estimation is an important tool for a side-channel evaluations laboratories. It allows estimating the remaining security after an attack has been performed, quantified as the time complexity and the memory consumption required to brute force the key given the leakages as probability distributions over $d$ subkeys (usually key bytes). These estimations are particularly useful where the key is not reachable with exhaustive search. We propose ESrank, the first rank estimation algorithm that enjoys provable poly-logarithmic time- and space-complexity, which also achieves excellent practical performance. Our main idea is to use exponential sampling to drastically reduce the algorithm's complexity. Importantly, ESrank is simple to build from scratch, and requires no algorithmic tools beyond a sorting function. After rigorously bounding the accuracy, time and space complexities, we evaluated the performance of ESrank on a real SCA data corpus, and compared it to the currently-best histogram-based algorithm. We show that ESrank gives excellent rank estimation (with roughly a 1-bit margin between lower and upper bounds), with a performance that is on-par with the Histogram algorithm: a run-time of under 1 second on a standard laptop using 6.5 MB RAM.

Category / Keywords: Side Channel, Rank Estimation, Key Enumeration

Original Publication (with major differences): RSA Conference Cryptographers' Track 2019 (CT-RSA 19)

Date: received 16 Sep 2018, last revised 9 Dec 2018

Contact author: lirondavid at gmail com

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2018/867

[ Cryptology ePrint archive ]